A Caltech Library Service

An Approximate Version of Sidorenko’s Conjecture

Conlon, David and Fox, Jacob and Sudakov, Benny (2010) An Approximate Version of Sidorenko’s Conjecture. Geometric and Functional Analysis, 20 (6). pp. 1354-1366. ISSN 1016-443X.

[img] PDF - Published Version
Creative Commons Attribution Non-commercial.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
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.
Funding AgencyGrant Number
St. John's College, CambridgeUNSPECIFIED
Princeton UniversityUNSPECIFIED
Binational Science Foundation (USA-Israel)UNSPECIFIED
Subject Keywords:Sidorenko’s conjecture; graph homomorphism; subgraph density
Issue or Number:6
Classification Code:05D40, 05C35, 26D15
Record Number:CaltechAUTHORS:20190812-162958544
Persistent URL:
Official Citation:Conlon, D., Fox, J. & Sudakov, B. Geom. Funct. Anal. (2010) 20: 1354.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97819
Deposited By: Melissa Ray
Deposited On:13 Aug 2019 21:50
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page