An Approximate Version of Sidorenko’s Conjecture

By David Conlon, Jacob Fox, Benny Sudakov. 2010

132 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/1d97d7901c992a94ecdebbaf9eb2b8459815360e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Finite reflection groups and graph norms (2016, background): “We refer the interested reader to [4] for further information about this conjecture and its relationship with graph norms.”
The History of Degenerate (Bipartite) Extremal Graph Problems (2013, background): “with some coincidences. As to the Sidorenko Conjecture, the ﬁrst unknown case (as Sidorenko mentions) is when we delete the edges of a Hamiltonian cycle from K 5,5. Theorem 11.7 (Conlon, Fox, Sudakov [52] [53]). The Sidorenko Conjecture holds if L= L[A,B] is a bipartite graph with a vertex x∈ Acompl”
On the KŁR conjecture in random graphs (2013, background): “However, the function g H ( ρ ) is only well understood for cliques and certain classes of bipartite graph (see, for example, [15, 61]).”
Sidorenko's conjecture for blow-ups (2018, methodology): “The first significant breakthrough on the conjecture was made by Conlon, Fox and Sudakov [1], who used the dependent random choice technique [6] to show that if H is a bipartite graph with a vertex which is complete to the other side then Sidorenko’s conjecture holds for H.”
Large Networks and Graph Limits (2012, methodology): “This construction was introduced independently by Diaconis and Freedman [1981], Boguñá and Pastor-Satorras [2003], Lovász and Szegedy [2006], and Bollobás, Janson and Riordan [2007], and quite probably implicitly by others.”