Sidorenko's conjecture

Let $H$ be a graph. Then $H$ is said to have Sidorenko's property if, for all graphons $W$, the inequality

: $t(H,W)\backslash geq\; t(K\_2,W)^$

is true, where $t(H,W)$ is the homomorphism density of $H$ in $W$.

Sidorenko's conjecture (1986) states that every bipartite graph has Sidorenko's property.{{citation

| last = Sidorenko | first = Alexander

| doi = 10.1007/BF02988307

| issue = 2–4

| journal = Graphs and Combinatorics

| pages = 201–204

| title = A correlation inequality for bipartite graphs

| volume = 9

| year = 1993| s2cid = 12233056

}}

If $W$ is a graph $G$, this means that the probability of a uniform random mapping from $V(H)$ to $V(G)$ being a homomorphism is at least the product over each edge in $H$ of the probability of that edge being mapped to an edge in $G$. This roughly means that a randomly chosen graph with fixed number of vertices and average degree has the minimum number of labeled copies of $H$. This is not a surprising conjecture because the right hand side of the inequality is the probability of the mapping being a homomorphism if each edge map is independent. So one should expect the two sides to be at least of the same order. The natural extension to graphons would follow from the fact that every graphon is the limit point of some sequence of graphs.

The requirement that $H$ is bipartite to have Sidorenko's property is necessary — if $W$ is a bipartite graph, then $t(K\_3,W)=0$ since $W$ is triangle-free. But $t(K\_2,W)$ is twice the number of edges in $W$, so Sidorenko's property does not hold for $K\_3$. A similar argument shows that no graph with an odd cycle has Sidorenko's property. Since a graph is bipartite if and only if it has no odd cycles, this implies that the only possible graphs that can have Sidorenko's property are bipartite graphs.

Sidorenko's property is equivalent to the following reformulation:

: For all graphs $G$, if $G$ has $n$ vertices and an average degree of $pn$, then $t(H,G)\backslash geq\; p^$

This is equivalent because the number of homomorphisms from $K\_2$ to $G$ is twice the number of edges in $G$, and the inequality only needs to be checked when $W$ is a graph as previously mentioned.

In this formulation, since the number of non-injective homomorphisms from $H$ to $G$ is at most a constant times $n^$

As previously noted, to prove Sidorenko's property it suffices to demonstrate the inequality for all graphs $G$. Throughout this section, $G$ is a graph on $n$ vertices with average degree $pn$. The quantity $\backslash operatorname\{hom\}(H,G)$ refers to the number of homomorphisms from $H$ to $G$. This quantity is the same as $n^$

Elementary proofs of Sidorenko's property for some graphs follow from the Cauchy–Schwarz inequality or Hölder's inequality. Others can be done by using spectral graph theory, especially noting the observation that the number of closed paths of length $\backslash ell$ from vertex $i$ to vertex $j$ in $G$ is the component in the $i$th row and $j$th column of the matrix $A^\backslash ell$, where $A$ is the adjacency matrix of $G$.

By fixing two vertices $u$ and $v$ of $G$, each copy of $C\_4$ that have $u$ and $v$ on opposite ends can be identified by choosing two (not necessarily distinct) common neighbors of $u$ and $v$. Letting $\backslash operatorname\{codeg\}(u,v)$ denote the codegree of $u$ and $v$ (i.e. the number of common neighbors), this implies:

: $\backslash operatorname\{hom\}(C\_4,G)=\backslash sum\_\{u,v\backslash in\; V(G)\}\backslash operatorname\{codeg\}(u,v)^2\backslash geq\backslash frac\{1\}\{n^2\}\backslash left(\backslash sum\_\{u,v\backslash in\; V(G)\}\backslash operatorname\{codeg\}(u,v)\backslash right)^2$

by the Cauchy–Schwarz inequality. The sum has now become a count of all pairs of vertices and their common neighbors, which is the same as the count of all vertices and pairs of their neighbors. So:

: $\backslash operatorname\{hom\}(C\_4,G)\backslash geq\backslash frac\{1\}\{n^2\}\backslash left(\backslash sum\_\{x\backslash in\; V(G)\}\backslash deg(x)^2\backslash right)^2\backslash geq\backslash frac\{1\}\{n^2\}\backslash left(\backslash frac\{1\}\{n\}\backslash left(\backslash sum\_\{x\backslash in\; V(G)\}\; \backslash deg(x)\; \backslash right)^2\backslash right)^2=\backslash frac\{1\}\{n^2\}\backslash left(\backslash frac\{1\}\{n\}(n\backslash cdot\; pn)^2\backslash right)^2=p^4n^4$

by Cauchy–Schwarz again. So:

: $t(C\_4,G)=\backslash frac\{\backslash operatorname\{hom\}(C\_4,G)\}\{n^4\}\backslash geq\; p^4$

as desired.

Although the Cauchy–Schwarz approach for $C\_4$ is elegant and elementary, it does not immediately generalize to all even cycles. However, one can apply spectral graph theory to prove that all even cycles have Sidorenko's property. Note that odd cycles are not accounted for in Sidorenko's conjecture because they are not bipartite.

Using the observation about closed paths, it follows that $\backslash operatorname\{hom\}(C\_\{2k\},G)$ is the sum of the diagonal entries in $A^\{2k\}$. This is equal to the trace of $A^\{2k\}$, which in turn is equal to the sum of the $2k$th powers of the eigenvalues of $A$. If $\backslash lambda\_1\backslash geq\backslash lambda\_2\backslash geq\backslash dots\backslash geq\backslash lambda\_n$ are the eigenvalues of $A$, then the min-max theorem implies that:

: $\backslash lambda\_1\backslash geq\backslash frac\{\backslash mathbf\{1\}^\backslash intercal\; A\backslash mathbf\{1\}\}\{\backslash mathbf\{1\}^\backslash intercal\backslash mathbf\{1\}\}=\backslash frac\{1\}\{n\}\; \backslash sum\_\{x\backslash in\; V(G)\}\backslash deg(x)=pn,$

where $\backslash mathbf\{1\}$ is the vector with $n$ components, all of which are $1$. But then:

: $\backslash operatorname\{hom\}(C\_\{2k\},G)=\backslash sum\_\{i=1\}^n\backslash lambda\_i^\{2k\}\backslash geq\backslash lambda\_1^\{2k\}\backslash geq\; p^\{2k\}n^\{2k\}$

because the eigenvalues of a real symmetric matrix are real. So:

: $t(C\_\{2k\},G)=\backslash frac\{\backslash operatorname\{hom\}(C\_\{2k\},G)\}\{n^\{2k\}\}\backslash geq\; p^\{2k\}$

as desired.

J.L. Xiang Li and Balázs Szegedy (2011) introduced the idea of using entropy to prove some cases of Sidorenko's conjecture. Szegedy (2015) later applied the ideas further to prove that an even wider class of bipartite graphs have Sidorenko's property.{{citation

| last = Szegedy | first = Balázs | author-link = Balázs Szegedy

| arxiv = 1406.6738

| title = An information theoretic approach to Sidorenko's conjecture

| year = 2015}} While Szegedy's proof wound up being abstract and technical, Tim Gowers and Jason Long reduced the argument to a simpler one for specific cases such as paths of length $3$.{{cite web

| last1 = Gowers | first1 = Tim | author-link = Timothy Gowers

| title = Entropy and Sidorenko's conjecture — after Szegedy

| url = https://gowers.wordpress.com/2015/11/18/entropy-and-sidorenkos-conjecture-after-szegedy/

| website = Gowers's Weblog

| date = 18 November 2015 |access-date = 1 December 2019}} In essence, the proof chooses a nice probability distribution of choosing the vertices in the path and applies Jensen's inequality (i.e. convexity) to deduce the inequality.

Here is a list of some bipartite graphs $H$ which have been shown to have Sidorenko's property. Let $H$ have bipartition $A\backslash sqcup\; B$.

• Paths have Sidorenko's property, as shown by Mulholland and Smith in 1959 (before Sidorenko formulated the conjecture).{{citation

| last1 = Mulholland | first1 = H.P.

| last2 = Smith | first2 = Cedric | author2-link = Cedric Smith (statistician)

| doi = 10.1080/00029890.1959.11989387

| issue = 8

| journal = American Mathematical Monthly

| pages = 673–683

| title = An inequality arising in genetical theory

| year = 1959| volume = 66

}}

• Trees have Sidorenko's property, generalizing paths. This was shown by Sidorenko in a 1991 paper.{{citation

| last = Sidorenko | first = Alexander

| doi = 10.1515/dma.1992.2.5.489

| issue = 3

| journal = Diskretnaya Matematika

| pages = 50–65

| title = Inequalities for functionals generated by bipartite graphs

| year = 1991| volume = 2

| s2cid = 117471984

}}

• Cycles of even length have Sidorenko's property as previously shown. Sidorenko also demonstrated this in his 1991 paper.
• Complete bipartite graphs have Sidorenko's property. This was also shown in Sidorenko's 1991 paper.
• Bipartite graphs with $\backslash min\backslash \{|A|,|B|\backslash \}\backslash leq4$ have Sidorenko's property. This was also shown in Sidorenko's 1991 paper.
• Hypercube graphs (generalizations of $Q\_3$) have Sidorenko's property, as shown by Hatami in 2008.{{citation

| last = Hatami | first = Hamed

| arxiv = 0806.0047

| doi=10.1007/s11856-010-0005-1 | doi-access=free

| volume = 175

| journal = Israel Journal of Mathematics

| pages = 125–150

| title = Graph norms and Sidorenko's conjecture

| year = 2010}}

• More generally, norming graphs (as introduced by Hatami) have Sidorenko's property.
• If there is a vertex in $A$ that is neighbors with every vertex in $B$ (or vice versa), then $H$ has Sidorenko's property as shown by Conlon, Fox, and Sudakov in 2010.{{citation

| last1 = Conlon | first1 = David | author1-link = David Conlon

| last2 = Fox | first2 = Jacob | author2-link = Jacob Fox

| last3 = Sudakov | first3 = Benny | author3-link = Benny Sudakov

| arxiv = 1004.4236

| issue = 6

| journal = Geometric and Functional Analysis

| pages = 1354–1366

| title = An approximate version of Sidorenko's conjecture

| year = 2010| volume = 20 | doi = 10.1007/s00039-010-0097-0 | s2cid = 1872674 }} This proof used the dependent random choice method.

• For all bipartite graphs $H$, there is some positive integer $p$ such that the $p$-blow-up of $B$ has Sidorenko's property. Here, the $p$-blow-up of $H$ is formed by replacing each vertex in $B$ with $p$ copies of itself, each connected with its original neighbors in $A$. This was shown by Conlon and Lee in 2018.{{citation

| last1 = Conlon | first1 = David | author1-link = David Conlon

| last2 = Lee | first2 = Joonkyung

| arxiv = 1809.01259

| title = Sidorenko's conjecture for blow-ups

| year = 2018}}

• Some recursive approaches have been attempted, which take a collection of graphs that have Sidorenko's property to create a new graph that has Sidorenko's property. The main progress in this manner was done by Sidorenko in his 1991 paper, Li and Szegedy in 2011,{{citation

| last1 = Li | first1 = J.L. Xiang

| last2 = Szegedy | first2 = Balázs | author2-link = Balázs Szegedy

| arxiv = 1107.1153

| title = On the logarithimic calculus and Sidorenko's conjecture

| year = 2011}} and Kim, Lee, and Lee in 2013.{{citation

| last1 = Kim | first1 = Jeong Han | author1-link = Jeong Han Kim

| last2 = Lee | first2 = Choongbum

| last3 = Lee | first3 = Joonkyung

| arxiv = 1310.4383

| title = Two Approaches to Sidorenko's Conjecture

| journal = Transactions of the American Mathematical Society

| volume = 368

| issue = 7

| pages = 5057–5074

| year = 2016

| doi = 10.1090/tran/6487 | doi-access = free}}

• Li and Szegedy's paper also used entropy methods to prove the property for a class of graphs called "reflection trees."
• Kim, Lee, and Lee's paper extended this idea to a class of graphs with a tree-like substructure called "tree-arrangeable graphs."

However, there are graphs for which Sidorenko's conjecture is still open. An example is the "Möbius strip" graph $K\_\{5,5\}\backslash setminus\; C\_\{10\}$, formed by removing a $10$-cycle from the complete bipartite graph with parts of size $5$.

László Lovász proved a local version of Sidorenko's conjecture, i.e. for graphs that are "close" to random graphs in a sense of cut norm.{{citation

| last1 = Lovász | first1 = László | author-link = László Lovász

| arxiv = 1004.3026

| title = Subgraph densities in signed graphons and the local Sidorenko conjecture

| year = 2010}}

A sequence of graphs $\backslash \{G\_n\backslash \}\_\{n=1\}^\{\backslash infty\}$ is called quasi-random with density $p$ for some density

: $t(H,G\_n)=(1+o(1))p^$

The sequence of graphs would thus have properties of the Erdős–Rényi random graph $G(n,p)$.

If the edge density $t(K\_2,G\_n)$ is fixed at $(1+o(1))p$, then the condition implies that the sequence of graphs is near the equality case in Sidorenko's property for every graph $H$.

From Chung, Graham, and Wilson's 1989 paper about quasi-random graphs, it suffices for the $C\_4$ count to match what would be expected of a random graph (i.e. the condition holds for $H=C\_4$).{{citation

| last1 = Chung | first1 = Fan | author1-link = Fan Chung

| last2 = Graham | first2 = Ronald | author2-link = Ronald Graham

| last3 = Wilson | first3 = Richard | author3-link = R. M. Wilson

| doi = 10.1007/BF02125347

| issue = 4

| journal = Combinatorica

| pages = 345–362

| title = Quasi-random graphs

| volume = 9

| year = 1989}} The paper also asks which graphs $H$ have this property besides $C\_4$. Such graphs are called forcing graphs as their count controls the quasi-randomness of a sequence of graphs.

The forcing conjecture states the following:

: A graph $H$ is forcing if and only if it is bipartite and not a tree.

It is straightforward to see that if $H$ is forcing, then it is bipartite and not a tree. Some examples of forcing graphs are even cycles (shown by Chung, Graham, and Wilson). Skokan and Thoma showed that all complete bipartite graphs that are not trees are forcing.{{citation

| last1 = Skokan | first1 = Jozef

| last2 = Thoma | first2 = Lubos

| doi = 10.1007/s00373-004-0556-1

| issue = 2

| journal = Graphs and Combinatorics

| pages = 255–262

| title = Bipartite Subgraphs and Quasi-Randomness

| volume = 20

| year = 2004| s2cid = 2154492

}}

Sidorenko's conjecture for graphs of density $p$ follows from the forcing conjecture. Furthermore, the forcing conjecture would show that graphs that are close to equality in Sidorenko's property must satisfy quasi-randomness conditions.{{citation

| last1 = Conlon | first1 = David | author1-link = David Conlon

| last2 = Fox | first2 = Jacob | author2-link = Jacob Fox

| last3 = Sudakov | first3 = Benny | author3-link = Benny Sudakov

| arxiv = 1004.4236

| issue = 6

| journal = Geometric and Functional Analysis

| pages = 1354–1366

| title = An approximate version of Sidorenko's conjecture

| year = 2010| volume = 20 | doi = 10.1007/s00039-010-0097-0 | s2cid = 1872674 }}

• Common graph

{{reflist}}

Category:Statements in graph theory

Category:Conjectures