Math Conjectures

Sidorenko's Conjecture

OPENLandmarkConjectureProposed 1986–1991 · Standard version

Canonical statement

For every finite bipartite graph HH and every symmetric measurable W:[0,1]2→[0,1]W:[0,1]^2\to[0,1],
t(H,W):=∫[0,1]V(H)∏uv∈E(H)W(xu,xv) ∏v∈V(H)dxv ≥ (∫[0,1]2W(x,y) dx dy)∣E(H)∣. t(H,W):= \int_{[0,1]^{V(H)}}\prod_{uv\in E(H)} W(x_u,x_v)\,\prod_{v\in V(H)}dx_v \ \geq\ \left(\int_{[0,1]^2}W(x,y)\,dx\,dy\right)^{|E(H)|}.
View source LaTeX
For every finite bipartite graph \(H\) and every symmetric
measurable \(W:[0,1]^2\to[0,1]\),
\[
  t(H,W):=
  \int_{[0,1]^{V(H)}}\prod_{uv\in E(H)}
    W(x_u,x_v)\,\prod_{v\in V(H)}dx_v
  \ \geq\
  \left(\int_{[0,1]^2}W(x,y)\,dx\,dy\right)^{|E(H)|}.
\]
GRAPH-010:[Sidorenko1993][ConlonFoxSudakov2010Sidorenko]
Graph theoryCombinatorics

Notes

Sidorenko's conjecture is a correlation inequality for bipartite graphs, formulated in Sidorenko's work of the late 1980s and early 1990s [Sidorenko1993]. In graphon language it asserts that for every finite bipartite graph HH and every symmetric measurable W:[0,1]2→[0,1]W:[0,1]^2\to[0,1], the homomorphism density satisfies t(H,W)≥p∣E(H)∣t(H,W)\ge p^{|E(H)|}, where pp is the edge density of WW. Informally, among graphs of a given edge density, quasirandom graphs asymptotically minimize the number of copies of any fixed bipartite graph.

The inequality is classical for trees, even cycles, and complete bipartite graphs, and it has been verified for many further bipartite families under additional structural hypotheses. Conlon, Fox, and Sudakov proved an approximate version of the conjecture [ConlonFoxSudakov2010Sidorenko].

No argument is known that covers every bipartite HH, and the conjecture remains open in general.

References (2)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.