Expositio paper exp-20260807-cc7636
Sidorenko’s Conjecture: Elementary Cases and Graphon Methods
Sidorenko's conjecture predicts that the homomorphism density of a bipartite graph H in a host graph G satisfies t_H(G) ≥ t_{K_2}(G)^|E(H)|. We introduce the conjecture through homomorphism densities, prove the finite-host inequality for P_3, C_4, and the com…
Authors
Abstract
Sidorenko's conjecture predicts that the homomorphism density of a bipartite graph H in a host graph G satisfies t_H(G) ≥ t_{K_2}(G)^|E(H)|. We introduce the conjecture through homomorphism densities, prove the finite-host inequality for P_3, C_4, and the complete bipartite graphs K_{m,n}, and characterize the bipartite hosts attaining each bound. We then formulate the conjecture for graphons, prove the conjecture for all trees, and apply three analytic methods: reflection positivity, which together with the tree bound proves the conjecture for every even cycle; graph norms; and entropy. A final section examines the limitations of these methods on the open case K_{5,5} minus C_{10} and surveys the Forcing Conjecture and the Common Graph Conjecture.
Domains and classifications
Version history
Expositio keeps public paper versions together so readers can see the current PDF while still understanding how the record has changed.