No graph is poorer in squares than chance

The fewest triangles an edge density allows asked how few triangles a graph can have once it has a given share of its possible edges, and the answer was a strange curve: nought up to density one half, then a scalloped boundary that Alexander Razborov pinned down in 2008. Triangles can be avoided entirely below a half, because a graph split into two sides with every edge crossing between them has no odd cycles at all. This essay asks the same question for patterns that cannot be avoided that way — patterns with no odd cycle, which a two-sided graph contains plenty of — and finds a much simpler and much more stubborn answer.

The answer is conjectural: a graph of a given edge density never contains fewer copies of a bipartite pattern than a random graph of that density does. Alexander Sidorenko made the conjecture in 1993, Paul Erdős and Miklós Simonovits had asked a version of it a decade earlier, and for most patterns it is proved. For the smallest pattern it has not been proved for, the figures below look for a counterexample and do not find one.

Counting a pattern by its density #

The right way to count copies of a small graph $H$ in a large graph $G$ is as a probability. Map the points of $H$ to points of $G$ at random, independently and with repetition allowed; the homomorphism density $t(H, G)$ is the chance that every edge of $H$ lands on an edge of $G$. For $H$ a single edge it is the edge density $p$ of $G$ itself (counting ordered pairs). For $H$ a four-cycle it is the chance that four random points $a, b, c, d$ have $ab$, $bc$, $cd$ and $da$ all edges — a ring of four, allowed to revisit points.

In a random graph, where each edge is present with chance $p$ independently, the edges of a copy of $H$ are present independently and $t(H, G) \approx p^{e(H)}$, where $e(H)$ counts the edges of $H$. Sidorenko’s conjecture is that this is the minimum: for every bipartite $H$ and every $G$,

$$t(H, G) \ge t(K_2, G)^{e(H)} = p^{e(H)}.$$

The figure tests it for the four-cycle on 31 graphs: random graphs at four densities, complete bipartite graphs with sides of various sizes, a Paley graph, a clique with isolated points added, and disjoint cliques. Each four-cycle density is counted exactly, as the trace of the fourth power of the adjacency matrix divided by $n^4$. Every graph lies on or above $p^4$. The random graphs hug the curve, a little above it because homomorphisms that revisit a point add a small excess; the graphs whose edges are bunched — a single clique, two-sided blocks — lie far above it. Bunching edges creates rings of four; spreading them as evenly as possible is the best a graph can do to avoid them, and the most even spreading is randomness.

A triangle is different #

For the triangle, which is not bipartite, the same comparison fails at once. Twenty-two of the 31 graphs have triangle density below $p^3$ — including many of the random ones, whose triangle counts scatter on both sides of the curve — and the complete bipartite graphs lie on the axis, with density close to one half and no triangles whatever. A pattern with an odd cycle can be avoided outright by a two-sided graph, as the edge that forces a triangle found when it proved Mantel’s theorem, and so no inequality of Sidorenko’s kind can hold for it.

That is why the conjecture is about bipartite patterns and only those: a pattern can be forced to appear at least at the random rate only if no clever arrangement of edges can avoid it entirely, and the patterns no arrangement avoids are precisely the bipartite ones. For non-bipartite patterns the right question is Razborov’s — how few copies, as a function of density — and the answer is a curve with nought on it.

Two lines for the four-cycle #

For the four-cycle the conjecture is a theorem with a two-line proof, and the figure evaluates both lines on one graph. The density of paths with two edges is the average, over points $v$, of $(\deg v / n)^2$ — the chance that two random points are both neighbours of $v$. An average of squares is at least the square of the average, by the Cauchy–Schwarz inequality, and the average of $\deg v/n$ is $p$, so the path density is at least $p^2$. The four-cycle density is the average, over ordered pairs of points $u, w$, of $(\operatorname{codeg}(u, w)/n)^2$, where the codegree counts common neighbours; by Cauchy–Schwarz again it is at least the square of the average codegree density, which is the path density. So

$$t(C_4, G) \ge t(P_2, G)^2 \ge p^4.$$

On the graph in the figure the chain reads $0.01395 \ge 0.00765 \ge 0.00666$. Equality throughout needs every degree equal and every codegree equal — which a random graph nearly achieves, and which is why random graphs sit on the curve. The same two uses of Cauchy–Schwarz drive the densest graph without a square, where they bound how many edges a graph can have before a four-cycle is forced; the extremal problem and the counting problem are two readings of one inequality.

Every even ring, by eigenvalues #

The two lines extend to every even cycle, through the eigenvalues of the graph. The number of closed walks of length $k$ in a graph is the trace of the $k$-th power of its adjacency matrix — a matrix that counts the returns used exactly this — and the trace is the sum of the $k$-th powers of the eigenvalues. Because the adjacency matrix is symmetric its eigenvalues are real, by the spectral theorem, and for an even $k$ every one of their powers is non-negative. So the closed-walk count is at least the largest eigenvalue to the $k$-th power. And the largest eigenvalue is at least the average degree, since the matrix applied to the all-ones vector returns the degrees, whose average is $pn$. Dividing by $n^k$,

$$t(C_{2m}, G) = \frac{1}{n^{2m}}\sum_i \lambda_i^{2m} \ge \left(\frac{\lambda_{\max}}{n}\right)^{2m} \ge p^{2m}.$$

For odd cycles the argument fails at exactly one step: an odd power of a negative eigenvalue is negative, and a two-sided graph has a negative eigenvalue as large as its largest, so the sum can cancel to nought — which is the triangle figure seen through the spectrum. The bipartite patterns are the ones whose counts are sums of squares, and a sum of squares cannot be smaller than its largest term.

Every pattern tested #

The figure takes nine patterns and, for each, the smallest ratio $t(H, G)/p^{e(H)}$ over the graphs. Each count is exact. Paths and cycles come from powers of the adjacency matrix; $K_{2,3}$ and $K_{3,3}$, complete bipartite patterns, come from summing powers of common-neighbourhood sizes over pairs and triples of points; and $K_{5,5}$ with a ten-cycle removed — five points on each side, each joined to three on the other — comes from summing over every image of one side of the product, over the other side’s points, of the sizes of the common neighbourhoods they need.

Every bipartite pattern stays at or above 1. The two paths reach exactly 1, on the regular graphs — Paley’s graph and the disjoint cliques — because for a path the inequality is an equality whenever all degrees are equal, which is the content of the first line of the four-cycle proof. The cycles and complete bipartite patterns stay strictly above it on these graphs, and the last bipartite pattern stays at 1.58. The triangle and the five-cycle, odd cycles both, fall to nought on the complete bipartite graphs.

Which bipartite patterns the conjecture is proved for is a long list with a short gap. It holds for trees and even cycles by arguments like the one above; for complete bipartite graphs; for every pattern with a point joined to everything on the other side, by David Conlon, Jacob Fox and Benny Sudakov in 2010; for the hypercubes, by Hamed Hatami in 2010; and for large families built by gluing proven cases together. The smallest bipartite graph for which it is not known is $K_{5,5}$ with a ten-cycle removed, the 15-edge pattern in the figure.

Random graphs sit on the line #

If randomness is the minimiser, random graphs should approach equality, and they do. On ten points the four-cycle ratio is 3.5, because so many of the “rings” counted are degenerate walks that go to a neighbour and back; on 320 points it is 1.06, and the six-cycle ratio falls the same way. The excess is the share of degenerate walks, which shrinks like $1/n$.

The converse is the forcing conjecture: a graph whose density of some bipartite pattern with a cycle is close to the random value must itself be close to random, in every sense that matters for counting. For the four-cycle it is a theorem of Fan Chung, Ronald Graham and Richard Wilson from 1989, and the foundation of the theory of quasirandom graphs: a single count — the number of four-cycles — certifies that a graph behaves like a random one in a long list of other ways, from the spread of its eigenvalues to the number of every other small pattern. The general forcing conjecture, for every bipartite pattern with a cycle, implies Sidorenko’s and is open with it.

Looking for a counterexample #

A counterexample would be a graph with fewer copies of a bipartite pattern than chance, and the last figure tries to build one. Starting from a random graph on eight points, it repeatedly toggles one pair, keeping the change whenever the ratio $t(H, G)/p^{15}$ for $H = K_{5,5}$ minus a ten-cycle does not rise. Twelve searches start from different densities and run three hundred flips each. The ratios fall quickly from millions — a sparse random graph on eight points has almost no room for a 15-edge pattern — and every search levels off above 1. The lowest is 1.015, at a nearly complete graph of density 0.875, where everything is close to regular and the pattern is close to its random rate.

That is how the conjecture has been tested in earnest, with far larger graphs and far longer searches, and by more sophisticated methods: semidefinite programming over the flag algebras Razborov developed for the triangle problem, which can prove inequalities between pattern densities by sums of squares. No counterexample has been found for any bipartite pattern, and the flag-algebra method has proved several cases that resisted other arguments.

An inequality about integrals #

Stated for graphs, the conjecture is about counting; stated in the limit, it is an inequality between integrals, and that is the form most proofs use. A very large graph can be summarised by a symmetric function $W(x, y)$ on the unit square with values between 0 and 1 — its graphon, in the language László Lovász and Balázs Szegedy introduced around 2006 — that gives the chance of an edge between points at positions $x$ and $y$. The homomorphism density of $H$ becomes an integral of a product of copies of $W$, one for each edge of $H$, over one variable for each point of $H$:

$$t(H, W) = \int \prod_{ij \in E(H)} W(x_i, x_j)\, dx.$$

Sidorenko’s conjecture says this is at least $\left(\int W\right)^{e(H)}$ whenever $H$ is bipartite: an integral of a product is at least the product of the integrals, the reverse of what independence would give for random variables that are positively related. For a single edge it is an identity, for a path it is the Blakley–Roy inequality, a relative of Hölder’s, and for a four-cycle it is Cauchy–Schwarz applied twice, as above. For $K_{5,5}$ minus a ten-cycle it is an inequality about a fifteen-fold product in ten variables that no known combination of the classical inequalities produces.

Why the conjecture matters #

The inequality is a statement about information: a graph that has a given number of edges cannot hide its bipartite structure — the counts of paths, even cycles and grids are forced up by the edges whether the graph is organised or not. It has the same shape as entropy inequalities in information theory — the kind that set the rate a noisy channel allows — and several of the proofs of special cases are entropy arguments: a random copy of the pattern is built step by step, and the entropy of its distribution is compared with that of independent edges. It also governs Ramsey multiplicity, the minimum number of monochromatic copies of a pattern in a two-colouring of a large complete graph, since a colouring is two graphs whose densities add to one, and Sidorenko’s inequality for each colour bounds the total from below by the random colouring’s count.

Common and uncommon patterns #

There is a two-colour version of the question with a longer history. Colour every edge of a large complete graph red or blue; how few monochromatic copies of a pattern can there be? Six people at a party found that a monochromatic triangle cannot be avoided once there are six points, and A. W. Goodman proved in 1959 that the number of monochromatic triangles is always at least about a quarter of all triangles — exactly what a random colouring gives. A pattern for which the random colouring minimises the monochromatic count is called common. Every pattern that satisfies Sidorenko’s inequality is common, by applying it to each colour separately and adding: the red density $p$ and the blue density $1 - p$ give at least $p^e + (1 - p)^e \ge 2^{1-e}$, the random count.

The triangle is common although it fails Sidorenko’s inequality, because the two colours compensate each other: a colouring that starves one colour of triangles floods the other with them. Paul Erdős conjectured in 1962 that every complete graph is common, and Andrew Thomason disproved it in 1989 for the complete graph on four points, with an explicit colouring that has fewer monochromatic copies of $K_4$ than a random one. Which patterns are common is a question much like Sidorenko’s and, outside the bipartite ones, much less understood.

What the figures show and assume #

Every count is exact: homomorphism densities, not samples. The graphs are small — 13 and 14 points for the collection, 8 for the search — because counting homomorphisms of a 15-edge pattern means summing over $n^5$ images of one side, and that is what keeps the search to eight points. Small graphs are where degenerate homomorphisms inflate the counts most, which makes the inequality easier to satisfy there, not harder; a counterexample, if one exists, may need to be large. The figures are therefore evidence of the most modest kind for the open case: the inequality holds everywhere it was looked for, and it was looked for in small places.

Still open: $K_{5,5}$ minus a ten-cycle #

Is $t(H, G) \ge p^{15}$ for $H$ the graph $K_{5,5}$ with a ten-cycle removed, and every $G$? It is the smallest bipartite graph for which Sidorenko’s conjecture is open, and its difficulty is structural: each point is joined to three of the five on the other side, in a cyclic pattern with no point joined to everything, so neither the dominating-vertex argument of Conlon, Fox and Sudakov nor the gluing constructions apply. A proof for it would very likely come with a new method; a counterexample would be the first evidence that randomness is not always the minimiser, and would make the general picture — that the bipartite patterns are exactly those forced at the random rate — false in a way nobody expects.

Spread evenly, and still not fewer #

A graph with a fixed share of its edges contains at least as many four-cycles, paths, even rings and complete bipartite patterns as a random graph of the same density — every one of 31 graphs tested lies above the random curve — while a triangle can be avoided altogether. For the four-cycle two applications of Cauchy–Schwarz prove it; random graphs approach equality as they grow, and Chung, Graham and Wilson showed that near-equality forces a graph to look random. Sidorenko conjectured that the same lower bound holds for every bipartite pattern, it is proved for most, and for the smallest open case, $K_{5,5}$ with a ten-cycle removed, a search for a counterexample stalls above chance.