The densest graph without a square

Turán’s theorem settles what happens when a complete graph is forbidden: the extremal graph splits the points into equal parts, and it keeps a fixed fraction of all possible edges. The same idea fails completely for a forbidden graph that can itself be split into two parts. A graph with two parts contains no triangle, but it does contain four-cycles by the thousand, and forbidding the four-cycle — four points $a, b, c, d$ with $a$ joined to $b$, $b$ to $c$, $c$ to $d$ and $d$ to $a$ — forbids something every dense two-part graph has.

The edge that forces a triangle stated the answer in one sentence: for the four-cycle the truth is about $\tfrac12 n^{3/2}$ edges. That is a different kind of answer from Turán’s. It is not a fraction of $\binom{n}{2}$ at all but a smaller power of $n$, so a graph without a four-cycle keeps a vanishing share of the possible edges as $n$ grows. Where the $3/2$ comes from, and what kind of graph comes close to it, are the two halves of this essay, and the second half is a surprise.

Two common neighbours is a square #

The first step is to restate the forbidden shape in a form that can be counted. A four-cycle $a\,b\,c\,d$ is exactly a pair of points, $a$ and $c$, with two common neighbours, $b$ and $d$. So a graph has no four-cycle precisely when every pair of points has at most one common neighbour.

That is how the search in the first figure works. It tries the possible edges one at a time, and whenever adding an edge would give some pair of points a second common neighbour it refuses the edge and backtracks; a branch that could not possibly beat the best found so far is abandoned. The whole search for nine points takes a few seconds and finds $13$; the numbers for smaller $n$ agree with the values in the published tables for this problem.

The numbers grow more slowly than anything in the triangle problem. Nine points can carry twenty triangle-free edges — the complete bipartite graph with parts of four and five — but only thirteen edges with no four-cycle. And the gap widens: the triangle-free maximum grows like $n^2/4$ and this one, as the figure’s curves suggest, like a constant times $n^{3/2}$.

The ceiling, by counting pairs of neighbours #

The upper bound is one of the most economical arguments in the subject: count one collection in two ways.

Call a pair of edges sharing an endpoint a cherry — a point together with two of its neighbours. A point with $d$ neighbours is the middle of $\binom{d}{2}$ cherries. Every cherry picks out a pair of points, its two ends, together with a common neighbour of theirs, its middle. And since no pair of points has two common neighbours, no pair of points is picked out by two different cherries. So the cherries are at most the pairs:

$$\sum_{v} \binom{d_v}{2} \le \binom{n}{2}.$$

The figure lays the count out literally. Each cell is a pair of points; each filled cell is a cherry, marked with its middle point; and the rule that every pair has at most one common neighbour is the rule that no cell is filled twice. The cherries can only fill the cells there are.

To turn that into a bound on edges, notice that $\binom{d}{2}$ is a convex function of $d$, so the sum is smallest, for a given total degree $2e$, when every degree is the average $2e/n$ — which is the curve of the average lying below the average of the curve, Jensen’s inequality, in its simplest form. So

$$n\binom{2e/n}{2} \le \binom{n}{2},$$

and solving the quadratic in $e$ gives

$$e \le \frac{n}{4}\left(1 + \sqrt{4n - 3}\right) \approx \frac12 n^{3/2}.$$

That is the upper curve in the first figure, and every exhaustive maximum sits under it. The argument is due to Kővári, Sós and Turán in 1954, in a form covering every complete bipartite graph, and to Reiman in 1958 for this sharp version.

A geometry in which every two points have one common neighbour #

The bound is tight only if almost every pair of points has exactly one common neighbour — the cherries must nearly fill the cells. That is a very rigid requirement, and there is a well-known structure satisfying something close to it: a finite projective plane, in which every two points lie on exactly one common line.

The plane over the field with two elements is the Fano plane, seven points and seven lines. Its points can be written as the seven non-zero triples of zeros and ones. Erdős and Rényi, in 1962, turned such a plane into a graph by a single rule: join two points when their coordinates are orthogonal — when the sum of the products of corresponding coordinates is zero in the field.

The reason there is no four-cycle is linear algebra. The points orthogonal to both $u$ and $v$ are the solutions of two independent linear equations in three unknowns, and those form a single line through the origin — a single point of the projective plane. So two points have exactly one common orthogonal point. A pair can lose even that as a neighbour only if the common point is one of $u$ and $v$ themselves, which happens when one of them is orthogonal to itself; those self-orthogonal points, $q + 1$ of them in the plane over a field with $q$ elements, are shaded, and they are the only reason the graph falls short of the bound at all.

On seven points the construction is not merely good but best: nine edges is exactly the exhaustive maximum. On thirteen, from the plane over the field with three elements, it is within two edges of the counting bound.

The edge count is exact in general. The plane over a field with $q$ elements has $q^2 + q + 1$ points; each point is orthogonal to the $q + 1$ points of a line, one fewer if it lies on its own line; so the graph has $\tfrac12 q(q+1)^2$ edges. With $n = q^2 + q + 1$ that is $\tfrac12 n^{3/2}$ to leading order — the counting bound’s own constant. The ceiling and the construction agree, and Füredi proved that for every $q$ above thirteen the polarity graph is exactly extremal, not just close.

The second count shows how close to tight the construction is. Of $78$ pairs, $66$ have a common neighbour; the counting bound would need all $78$. The empty cells are exactly the pairs where the unique common orthogonal point is one of the pair itself, and they are the price of the loops a self-orthogonal point would need. A structure in which every pair had exactly one common neighbour would have no such losses — and a theorem of Erdős, Rényi and Sós, the friendship theorem, says the only finite graphs with that property are windmills of triangles sharing one point, which have very few edges. So the losses cannot be avoided, and the projective plane loses as few as a graph can.

Why three halves #

The exponent can be seen without any algebra, by asking what the counting bound forces on a typical point.

If a graph on $n$ points is to have about $n^{3/2}$ edges, its average point has about $\sqrt n$ neighbours. Those neighbours make about $n/2$ cherries at that point, each using up one pair of points; across all $n$ points that is about $n^2/2$ pairs used, which is all the pairs there are. So $\sqrt n$ neighbours each is exactly the degree at which the cherries run out of cells. A larger typical degree would need more pairs than exist; a smaller one leaves pairs unused and the graph could be denser.

Read geometrically, each point’s neighbourhood is a set of about $\sqrt n$ points, and any two such neighbourhoods may overlap in at most one point — otherwise their two centres would share two neighbours. So the graph is, in effect, a family of $n$ sets of size $\sqrt n$, any two meeting at most once. That is precisely the shape of the lines of a projective plane: $n$ lines of about $\sqrt n$ points each, any two meeting in exactly one point. The counting bound does not merely permit a projective plane; it describes one, and the construction is the only thing that fits the description so closely. The geometry is not an ingenious way round the problem but the shape the problem was asking for, which is why planes that no field builds would serve equally well wherever they carry the right symmetry.

A plane beats chance #

The construction is algebraic, and it is worth comparing with the method that usually wins such contests: choose edges at random and repair the damage.

Put each edge in with probability $p$, then delete one edge from every four-cycle that appears. With $p$ chosen well, what survives has about $n^{4/3}$ edges — a real graph with no four-cycle, obtained with no cleverness at all. For many extremal problems this method gives the right order of magnitude, and for some the random graph is the best construction anyone has.

Not here. The random construction reaches $n^{4/3}$, the plane reaches $\tfrac12 n^{3/2}$, and the gap is a power of $n$. On the figure’s logarithmic axes the polarity graph runs parallel to the bound and the random graph runs on a shallower slope, so its share of the bound must eventually fall like $n^{-1/6}$ — slowly, which is why at these sizes it hovers near a fifth, but without limit.

That is the surprise the problem holds. The densest graph without a square is not the most disordered graph but a highly structured one, and the structure is the incidence geometry of a finite field. It is the same geometry that the Latin squares turned out to hide, and the reason is the same: the property wanted — any two points share exactly one thing — is the defining axiom of a projective plane, and a finite field builds one.

The same count for points and lines #

The cherry argument is not really about graphs, and it reappears wherever the rule “two things share at most one thing” holds. The most important instance is the counting of incidences between points and lines.

Take $n$ points and $n$ lines in a plane and ask how many of the $n^2$ point-line pairs can be incidences — a point lying on a line. Build a graph with the points on one side and the lines on the other, joining a point to each line through it. Two points lie on at most one common line, so no two points have two common neighbours: the graph has no four-cycle. The cherry count applies word for word and caps the incidences at about $n^{3/2}$.

In a finite projective plane that bound is met exactly: $q^2 + q + 1$ points, as many lines, each line through $q + 1$ points, for $(q^2 + q + 1)(q + 1)$ incidences — the order of $n^{3/2}$. The plane is simply the structure in which the cherries fill every cell. This is the same arrangement that gave the polarity graph, read as a two-sided graph rather than folded onto one side.

In the ordinary plane of real numbers the bound is not met, and the reason is geometric. Szemerédi and Trotter proved in 1983 that $n$ real points and $n$ real lines have at most a constant times $n^{4/3}$ incidences, a smaller power, and that bound is achieved by grids. The difference between $n^{3/2}$ and $n^{4/3}$ is exactly the difference between a finite field and the real line: the real plane has an order and a notion of betweenness that forbid the perfectly balanced configurations a finite plane allows, which is the same property Kelly’s proof of the ordinary-line theorem exploits and that fails over other fields. So the four-cycle problem and the incidence problem are one count, and whether it is tight depends on which field the geometry lives over — a finite field for the extremal graphs, a real one for the geometry of drawings.

Sets whose sums never repeat #

There is a third reading, in arithmetic, and it produced the first constructions of this kind decades before the graphs did.

A set of whole numbers is a Sidon set if all its pairwise sums are different: $a + b = c + d$ only when $\{a, b\} = \{c, d\}$. How large can a Sidon set inside $\{1, \dots, n\}$ be? The sums $a + b$ lie below $2n$ and must all be distinct, so a set of size $k$ needs about $k^2/2$ different sums below $2n$, which caps $k$ near $2\sqrt n$. Refining that count by the same pigeonhole reasoning as the cherries gives a cap of about $\sqrt n$.

The reason it is the same problem is a four-cycle in disguise. A repeated sum $a + b = c + d$ is the same as a repeated difference $a - c = d - b$, and a repeated difference is a quadrilateral in the graph joining numbers that differ by an element of the set. And the construction that reaches the cap is the same geometry again: Singer showed in 1938 that the $q + 1$ points on a line of the plane over a field with $q$ elements, numbered cyclically by a generator of a larger field, form a set whose differences are all distinct modulo $q^2 + q + 1$. The largest Sidon sets known come from projective planes, just as the densest square-free graphs do.

What the pictures cannot show #

The asymptotic constant. The search stops at nine points, and the planes drawn stop at $133$. That $\tfrac12 n^{3/2}$ is the right leading term for every large $n$ — not only for $n$ of the form $q^2 + q + 1$ — needs the fact that primes are dense enough that some $q^2 + q + 1$ lies close below any $n$, and a construction for the points in between. Neither is drawn.

That the search is exhaustive. The exhaustive maxima are the output of a search that prunes; a pruning search is exhaustive only if every pruned branch genuinely could not win, and that is an argument about the search rather than a picture. The values agree with those long established in the literature, which is a check and not a proof.

The general field. The planes drawn are over fields with a prime number of elements. The construction works equally over any finite field — four, eight, nine elements — and those planes exist and give the same edge counts; they are omitted only because the arithmetic of a field whose size is not prime needs more than remainders, as the field with four elements shows.

Still open: longer even cycles #

The four-cycle is the one bipartite cycle whose extremal number is understood completely. For a cycle of length $2k$, Bondy and Simonovits proved in 1974 that the extremal number is at most a constant times $n^{1 + 1/k}$, by an argument that generalises counting cherries to counting paths. Matching constructions, with that exponent, are known only for $k = 2$, $3$ and $5$ — the four-, six- and ten-cycles — and each comes from a finite geometry: projective planes, generalised quadrangles and generalised hexagons. For the eight-cycle, the question of whether $n^{5/4}$ is the true order is open, and it is open because no geometry of the right kind is known to exist for that length.

The same pattern holds for complete bipartite graphs. Forbidding $K_{3,3}$ gives an extremal number of order $n^{5/3}$, matched by Brown’s construction from spheres over finite fields; forbidding $K_{4,4}$, the upper bound is of order $n^{7/4}$ and no construction is known that reaches it. The frontier of the subject is exactly the frontier of known algebraic structures, which is an unusual thing to be able to say about a question that begins by counting edges.

The ceiling set by a count, reached by a geometry #

A graph without a four-cycle is one in which no two points share two neighbours, and counting the pairs of neighbours against the pairs of points caps the edges at about $\tfrac12 n^{3/2}$. The argument is two lines and a convexity inequality.

The graphs that meet that cap are not found by search or by chance. They are the orthogonality graphs of finite projective planes, in which any two points have exactly one common orthogonal point, and the only edges they lose are the handful at points orthogonal to themselves. A problem about avoiding one small shape in a graph is solved by the geometry of a finite field, and the unsolved cases beyond it are unsolved because the geometry they would need has not been found.