OP-00715 Solution claimed

Sidorenko's lower bound for bipartite homomorphism counts

Let $H$ be a finite simple bipartite graph with $v$ vertices and $e \ge 1$ edges, and $G$ a finite simple graph on $n \ge 1$ vertices. Let $\operatorname{hom}(H,G)$ count all maps $V(H) \to V(G)$ that preserve adjacency, injective or not, and let $p = 2|E(G)|/n^2$ be the edge density of $G$. The inequality below is known when $H$ is a tree or an even cycle (Simonovits; Sidorenko), for hypercubes (Hatami), and when $H$ has a vertex adjacent to every vertex of the other part (Conlon, Fox and Sudakov).

Problem. Prove or disprove that, for every such pair of graphs, $$\frac{\operatorname{hom}(H,G)}{n^v} \ge p^e.$$

Source: Simonovits (1984) and Sidorenko (1991, 1993); stated by AIM — Open Applied Problems as the unweighted form of Csikvári, Ruozzi and Shams (2022), Conjecture I.1.

Imported from github.com/MColbrook/AIM.

Classification

Primary: CO — Combinatorics
Secondary: IT
Keywords: AIM Open Applied Problems, graph homomorphisms, Sidorenko's conjecture

References

@article{sidorenko1993,
  author  = {Sidorenko, Alexander},
  title   = {A correlation inequality for bipartite graphs},
  journal = {Graphs Combin.},
  volume  = {9},
  number  = {2-4},
  year    = {1993},
  pages   = {201--204},
  doi     = {10.1007/BF02988307},
}
@article{csikvari2022,
  author  = {Csikv{\'a}ri, P{\'e}ter and Ruozzi, Nicholas and Shams, Shahab},
  title   = {Markov random fields, homomorphism counting, and {S}idorenko's conjecture},
  journal = {IEEE Trans. Inform. Theory},
  volume  = {68},
  number  = {9},
  year    = {2022},
  pages   = {6052--6062},
  doi     = {10.1109/TIT.2022.3169487},
}
@article{hatami2010,
  author        = {Hatami, Hamed},
  title         = {Graph norms and {S}idorenko's conjecture},
  journal       = {Israel J. Math.},
  volume        = {175},
  number        = {1},
  year          = {2010},
  pages         = {125--150},
  doi           = {10.1007/s11856-010-0005-1},
  eprint        = {0806.0047},
  archivePrefix = {arXiv},
}
@article{conlon2010,
  author        = {Conlon, David and Fox, Jacob and Sudakov, Benny},
  title         = {An approximate version of {S}idorenko's conjecture},
  journal       = {Geom. Funct. Anal.},
  volume        = {20},
  number        = {6},
  year          = {2010},
  pages         = {1354--1366},
  doi           = {10.1007/s00039-010-0097-0},
  eprint        = {1004.4236},
  archivePrefix = {arXiv},
}
@misc{aim-sidorenko,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Sidorenko's lower bound for bipartite homomorphism counts}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/1b7c7fd251c1643bb41f0e3cef38704bcef410fd/problems/585-sidorenko.md},
  note         = {Entry 585 at commit 1b7c7fd, 2026-10-13},
}

Resolution claims

A counterexample to Sidorenko's conjecture v1 GitHub ↗

OpenAI

We disprove Sidorenko's conjecture with a bipartite graph on $35$ vertices and $66$ edges: its homomorphism density in some finite simple graph is smaller than the conjectured lower bound. The same connected graph also disproves the forcing conjecture: at one fixed density, asymptotically matching the edge and pattern densities does not imply quasirandomness.

Counterexample · not verified · fidelity not established · posted on GitHub 6 Oct 2026

Status history

When	Change	By	Reason
2026-10-16	Needs verification → Solution claimed	—	Recorded here: math @ 1581d4c, build/main.tex.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00715, "Sidorenko's lower bound for bipartite homomorphism counts", clopen.solutions.