Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2010 | Submitted + Published
Journal Article Open

An Approximate Version of Sidorenko's Conjecture


A beautiful conjecture of Erdős-Simonovits and Sidorenko states that, if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness. Here we prove the conjecture if H has a vertex complete to the other part, and deduce an approximate version of the conjecture for all H. Furthermore, for a large class of bipartite graphs, we prove a stronger stability result which answers a question of Chung, Graham, and Wilson on quasirandomness for these graphs.

Additional Information

© 2010 The Author(s). This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited. Received: April 26, 2010. Accepted: June 3, 2010. D.C.'s research supported by a Junior Research Fellowship at St John's College. J.F.'s research supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. B.S.'s research supported in part by NSF CAREER award DMS-0812005 and by a USA-Israeli BSF grant.

Attached Files

Published - Conlon2010_Article_AnApproximateVersionOfSidorenk.pdf

Submitted - 1004.4236.pdf


Files (441.4 kB)
Name Size Download all
258.0 kB Preview Download
183.4 kB Preview Download

Additional details

August 22, 2023
October 18, 2023