Math 2.0

Combinatorics Extremal combinatorics Conjecture

Sidorenko's conjecture

Builds on GraphBipartite graphGraph homomorphism

Statement

Let HH and GG be finite simple graphs, with GG having at least one vertex. Let hom⁡(H,G)\hom(H, G) be the number of graph homomorphisms from HH to GG, and let t(H,G)=hom⁡(H,G)∣V(G)∣∣V(H)∣t(H, G) = \frac{\hom(H, G)}{|V(G)|^{|V(H)|}} be the homomorphism density. Let K2K_2 be the graph with one edge, so that t(K2,G)=2∣E(G)∣/∣V(G)∣2t(K_2, G) = 2 |E(G)| / |V(G)|^2. Let HH be a bipartite graph with e(H)e(H) edges. Then for every graph GG, t(H,G)≥t(K2,G)e(H).t(H, G) \ge t(K_2, G)^{e(H)}.

Remarks

The conjecture is open. It is known for trees, for even cycles, for complete bipartite graphs and for hypercube graphs. It is also known for every bipartite graph that has a vertex adjacent to all vertices of the other part.

The right side is the density of HH in a random graph with the same edge density. So the conjecture says that random graphs minimise the density of HH among graphs of a given edge density. Bipartiteness is necessary. If HH has an odd cycle and GG is the complete bipartite graph Kn,nK_{n,n}, then t(H,G)=0t(H, G) = 0, while t(K2,G)=1/2t(K_2, G) = 1/2. For HH a path with two edges, the conjecture is the inequality 1n∑vd(v)2≥(1n∑vd(v))2\frac{1}{n} \sum_v d(v)^2 \ge \left(\frac{1}{n}\sum_v d(v)\right)^2 for the degrees d(v)d(v) of GG, which holds by the Cauchy–Schwarz inequality.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Bipartite graph, concept, no evidence levelBipartite graphconceptGraph, concept, no evidence levelGraphconceptGraph homomorphism, concept, no evidence levelGraph homomorphismconceptSidorenko's conjecture, conjecture, no evidence levelSidorenko's conjectureconjecture
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Bipartite graph concept
  2. Graph concept
  3. Graph homomorphism concept
  4. Sidorenko's conjecture conjecture

Further reading

  1. Web https://en.wikipedia.org/wiki/Sidorenko's_conjecture
About this page
TagKN2PXSCT9J
URIm2://KN2PXSCT9J
Kindconjecture
WritingW0 stub
MSC05C35
StatusThis copy of the site has no build data. Run m2 status KN2PXSCT9J.
AboutExtremal graph theory, Graph homomorphism
UsesGraph, Bipartite graph, Graph homomorphism
Same as
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.