Sidorenko’s conjecture

Does the overall chance of a connection put a minimum on how often every two-group connection pattern appears? The pattern’s dots can be divided into two groups, with all its links across the split; this is bipartite. Both networks are finite and the host has at least one dot. Place each pattern dot independently onto a dot of the host network and ask whether every pattern link lands on a host connection. Nonjoined pattern dots may land on the same host dot. For a three-dot path placed onto a host consisting of one connection, only two of the eight placements work: both endpoints land together and the middle lands at the other end. The conjecture compares the fraction of working placements with a benchmark obtained by multiplying the single-connection chance once per pattern link.[1] [2]

Can an overall connection density guarantee a minimum frequency for every pattern whose vertices split into two parts with edges only across? Such patterns are bipartite. The proposed minimum is a product-of-densities benchmark. Count every edge-preserving map from the pattern to the host, allowing nonadjacent pattern vertices to coincide. Such a map is a graph homomorphism. For the three-vertex path mapped to a host with two vertices and one edge, two maps work out of eight: both endpoints go to one vertex and the middle to the other. Let $H$ be a finite bipartite pattern with $v$ vertices and $e$ edges, and let $G$ be a finite simple host with $n>0$ vertices. Set $t(H,G)=\operatorname{hom}(H,G)/n^v$ and write the edge density as $p=2|E(G)|/n^2$. The conjecture is $t(H,G)\ge p^e$. The denominator $n^2$ counts ordered independent choices, including choices of the same vertex; a simple host has no loop, so adjacent pattern vertices cannot coincide. The path example has $t=1/4=p^2$.[1] [2]

The inequality is known for many patterns, but not for every bipartite pattern. Results for selected patterns and equivalent formulations leave that universal question open. Counterexamples for patterns whose links join three or more dots concern hypergraphs, a different setting from ordinary two-dot connections.[1] [2]

The reviewed 2026 preprint’s spectral equivalence is a reformulation, not a general proof.[1]

A network’s overall connection density ignores where its connections are concentrated. Counts of larger patterns detect that arrangement. The conjecture proposes that rearranging a fixed amount of connection density cannot push any bipartite pattern below its random-like benchmark. This connects a single average quantity with the correlations visible in larger structures.[1] [2]

The density $p$ records only the average chance that two independent host choices form an edge. The probability $t(H,G)$ tests several such requirements together and is sensitive to how edges are arranged. The benchmark $p^e$ describes independent edge requirements; it is not an exact expectation for distinct-copy counts in every finite random graph. The conjecture would constrain these correlations for every bipartite pattern and supply lower bounds on larger configurations from density alone. The cited spectral reformulation links this counting principle with adjacency-matrix information, but does not resolve the universal inequality.[1] [2]