Triangle-free, and two-sided eventually

Half of all possible edges can be drawn without a triangle, and one more forces one: Mantel’s theorem says a triangle-free graph on $n$ points has at most $n^2/4$ edges, and the graphs that reach the maximum are the complete bipartite graphs with equal sides. Near the maximum the shape is forced too — a triangle-free graph with nearly $n^2/4$ edges is nearly bipartite. Both statements are about the densest graphs.

A different question asks about all of them. Of the triangle-free graphs on $n$ labelled points, how many are bipartite — their points split into two sides with every edge crossing between them? Paul Erdős, Daniel Kleitman and Bruce Rothschild proved in 1976 that the answer is almost all: the share tends to one as $n$ grows. Counted exactly for small $n$, the share does the opposite. Every triangle-free graph on four points is bipartite; on nine, fewer than half are.

The first exceptions are easy to name. On five labelled vertices there are 388 triangle-free graphs and 376 bipartite ones, and the twelve that are not bipartite are exactly the twelve ways of labelling a five-cycle — the only triangle-free graph on five vertices with an odd cycle. From six vertices on, the odd cycles can carry extra edges and extra vertices, and their number grows faster than the bipartite count does for a while.

The theorem is not wrong and the counts are not wrong. They describe different ranges, and the gap between them is one of the clearest examples there is of a limit that small cases point away from.

Counting them one vertex at a time #

Counting triangle-free graphs exactly is a matter of building them. Add vertices one at a time; the new vertex may be joined to any set of earlier vertices provided no two of them are already joined, since two joined neighbours and the new vertex would make a triangle. So the new vertex’s neighbourhood must be an independent set of the graph so far, and every triangle-free graph on $n + 1$ labelled vertices arises exactly once from a triangle-free graph on the first $n$ and an independent set of it.

That gives the counts by enumeration: 1, 2, 7, 41, 388, 5,789, 133,501 and 4,682,270 triangle-free graphs on one to eight labelled vertices. The ninth count does not need the nine-vertex graphs themselves: it is the total number of independent sets over all 4,682,270 graphs on eight vertices, which is 246,348,115.

Bipartite graphs can be counted without enumeration. Colouring the vertices with two colours and allowing any edges between the colours gives $\sum_k \binom nk 2^{k(n-k)}$ coloured graphs, and each bipartite graph with $c$ connected pieces is counted $2^c$ times, once for each way of colouring its pieces. In the language of generating functions, the coloured count is the square of the bipartite count, and taking a square root of a power series gives exact bipartite counts for as many vertices as wanted: 376 on five vertices, 2,922,446 on eight, 116,011,231 on nine. The square is an instance of the rule that exponential generating functions multiply when labelled structures are dealt out among parts: a two-coloured graph is a set of coloured connected pieces, each piece can be coloured in two ways, and so the coloured count is the exponential of twice the connected count while the bipartite count is the exponential of the connected count once. Halving an exponent is taking a square root. For eight vertices and fewer the enumeration finds the same numbers by testing every triangle-free graph for an odd cycle, which is a check on both.

Two counts with the same leading exponent #

The numbers grow like a power of two whose exponent is close to $n^2/4$. That is natural: a complete bipartite graph with equal sides has $n^2/4$ edges, and every one of its $2^{n^2/4}$ subgraphs is triangle-free and bipartite.

Both ratios approach one, so to first order the two families are equally large: $2^{n^2/4 + o(n^2)}$ each. The bipartite ratio approaches one from above, slowly, because a bipartite graph also needs a choice of how to split the vertices, and there are about $2^n$ ways to do that — a correction that matters at forty vertices and vanishes against $n^2/4$ only in the limit. The theorem of Erdős, Kleitman and Rothschild is about the next terms: it says the triangle-free count is the bipartite count times a factor that tends to one, so that the non-bipartite graphs, numerous as they are at nine vertices, are eventually a vanishing fraction.

Where the odd cycles live #

All 4,682,270 triangle-free graphs on eight vertices can be sorted by how many edges they have, and the sorting shows where the non-bipartite ones come from.

Below five edges every triangle-free graph is bipartite, since a graph is bipartite exactly when it has no odd cycle and the shortest odd cycle without a triangle has five edges. The non-bipartite graphs appear at five edges, are a minority at first, outnumber the bipartite ones at ten and eleven edges, and thin out again towards the maximum. At sixteen edges the only triangle-free graphs are the 35 complete bipartite graphs with four vertices on each side, one for each way of splitting eight labelled vertices into two fours. Mantel’s theorem and its uniqueness are visible as the last bar.

The counts are dominated by graphs with eight to eleven edges, in the middle of the range, where odd cycles of length five fit easily. That is the reason the share falls: small graphs are sparse, and sparse triangle-free graphs have room for odd cycles. The theorem says that as $n$ grows the counts become dominated by much denser graphs — with about $n^2/8$ edges, half of the maximum — and dense triangle-free graphs have no room for odd cycles. At eight or nine vertices that domination has not begun.

What spoils a triangle-free graph #

The non-bipartite triangle-free graphs that do exist are close to bipartite.

On seven vertices, every one of the 30,264 non-bipartite triangle-free graphs becomes bipartite when a single edge is deleted, which the figure finds by computing, for each graph, the largest number of edges crossing some split of its vertices. On eight vertices the shortest odd cycle has five edges in 98.1 per cent of the non-bipartite ones and seven in the rest. A typical non-bipartite triangle-free graph is a bipartite graph with an edge or two placed inside one side.

That picture is the engine of the proof. Take a bipartite graph with sides of about $n/2$, and add one edge inside a side, joining $u$ and $v$. To stay triangle-free, no vertex on the other side may be joined to both $u$ and $v$. Each of the $n/2$ vertices over there had four options for its edges to $u$ and $v$ — neither, one, the other, both — and now has three. So one extra edge costs a factor of about $(3/4)^{n/2}$ in the number of compatible graphs, against a gain of a factor of two for having the edge or not. For small $n$ the gain wins, and adding odd cycles is cheap. For large $n$ the cost is exponential and the gain is constant, and graphs with edges inside the sides become rare: the counting turns in favour of the bipartite graphs, exactly as the theorem says, and only after $n$ is large enough for $(3/4)^{n/2}$ to be small.

A threshold in the number of edges #

The theorem can be made sharper by fixing the number of edges. Among triangle-free graphs on $n$ vertices with exactly $m$ edges, chosen uniformly at random, is a typical one bipartite? Deryk Osthus, Hans Jürgen Prömel and Anusch Taraz answered in 2003: there is a threshold near $\tfrac{\sqrt3}4\, n^{3/2}\sqrt{\ln n}$ edges. Below it — but above about $n/2$ edges, where a sparse graph is mostly a forest and bipartite for that reason — a random triangle-free graph with $m$ edges is almost surely not bipartite; above it, almost surely bipartite.

That threshold explains the falling share. The total count is dominated by graphs with about $n^2/8$ edges, which is far above the threshold once $n$ is large, so almost every triangle-free graph is bipartite. But at nine vertices, $n^{3/2}\sqrt{\ln n}$ and $n^2/8$ are comparable — $\tfrac{\sqrt3}4 \cdot 27 \cdot 1.48 \approx 17$ against about ten — and the typical edge count still sits below the threshold, where odd cycles are the rule. The turn in the share happens when $n^2/8$ overtakes the threshold by a wide margin, and at the threshold’s scale that takes far more vertices than any exhaustive count can reach.

Thresholds of this kind are the standard behaviour of random graphs: a property switches from almost never to almost always across a narrow range of edge counts, the way a giant component appears, and locating the switch is usually two moment calculations. What is unusual here is that the random object is not a random graph but a random triangle-free graph — a uniformly chosen member of a family defined by what it avoids — and the analysis has to count that family, not merely sample from a simple distribution.

The densest and the typical #

Two different questions about triangle-free graphs have the same answer, and it is worth keeping them apart. The extremal question asks what the densest triangle-free graph looks like, and the answer — complete bipartite — is exact and holds for every $n$. The typical question asks what most triangle-free graphs look like, and the answer — bipartite — holds only in the limit. The extremal answer is about one graph; the typical answer is about a count of $2^{n^2/4}$ of them.

They connect through stability. A triangle-free graph with nearly the maximum number of edges is close to bipartite, and the counting proof uses exactly that: almost all triangle-free graphs have nearly $n^2/8$ edges, which is half the maximum, not nearly the maximum, so stability does not apply to them directly. What applies is a statement about how many graphs of each structure there are, and for that the $(3/4)^{n/2}$ cost of each misplaced edge is the decisive calculation. The extremal theory says what can be packed in; the typical theory says what the count is dominated by.

The same split runs through extremal graph theory. The fewest triangles a graph of given density can have is an extremal question with a hard answer, and the densest graph with no four-cycle has about $n^{3/2}/2$ edges — a power of $n$ curiously close to where the greedy triangle-free process stops. For four-cycles the typical question is harder than the extremal one: Daniel Kleitman and Kenneth Winston showed in 1982 that the number of graphs with no four-cycle is $2^{O(n^{3/2})}$, but the constant in that exponent is still not known. The container methods developed after 2010, which reduce counting problems of this kind to a small number of near-extremal configurations, reproved the triangle-free theorem in a far more general form and settled many such counts — though not that one.

The greedy process builds something else #

There is another natural way to make a random triangle-free graph, and it lands below the threshold. List all pairs of vertices in random order and add each one as an edge unless it would close a triangle. The process ends with a maximal triangle-free graph — no edge can be added — but nothing like the densest ones.

Tom Bohman and Peter Keevash, and independently Gonzalo Fiz Pontiveros, Simon Griffiths and Robert Morris, proved in 2013 that the process ends with about $\frac{1}{2\sqrt2}\, n^{3/2}\sqrt{\ln n}$ edges — below the bipartite threshold — and its graphs look random rather than bipartite: no split of the vertices puts much more than half of the edges across. The simulations sit about a fifth above the formula, a ratio falling only slowly over the sizes drawn, and the best split found takes 62 per cent of the edges at 800 vertices. The process’s graphs have no triangle and no large set of mutually unjoined vertices either, which made their analysis the route to the best lower bound on the Ramsey numbers $R(3, t)$ — the smallest number of people at a party guaranteeing three mutual acquaintances or $t$ mutual strangers, the question whose smallest case is six.

Triangle-free yet far from two-sided #

Some triangle-free graphs are as far from bipartite as possible, and the small ones are worth seeing.

The five-cycle is the smallest. The Wagner graph on eight vertices is an eight-cycle with its four long diagonals added, and each diagonal closes a five-cycle. The Petersen graph has ten vertices and fifteen edges, every vertex on three of them, and it already appeared as the extreme case of graphs where every point is two steps from every other. Each needs three colours, where a bipartite graph needs two — and triangle-free graphs can need as many colours as anyone likes, as Mycielski’s construction shows, starting from the five-cycle. So the absence of triangles says nothing, in general, about how far a graph is from two-sided. It is only for typical graphs, counted all together, that it says almost everything.

What exhaustive counting cannot show #

The counts are exact for every $n$ up to nine and say nothing directly about larger $n$; the theorem is about the limit and says nothing about any particular $n$. Between the two lies the question of where the share turns, and neither instrument reaches it. The enumeration grows by a factor of about fifty for each additional vertex — 246 million graphs at nine vertices means well over ten billion at ten — and the turn is plausibly at a size where exact counting is out of the question.

The heuristic in the proof, the factor $(3/4)^{n/2}$, suggests the scale: it falls below $\tfrac1{10}$ only around $n = 16$, and the non-bipartite graphs have many more ways to place their extra edges than the one-edge picture counts. So the turn is probably well beyond sixteen vertices. That is a plausibility argument, not a computation, and the figures cannot test it.

The greedy process’s simulations are averages over a handful of runs at each size, and the cut fractions are found by a local search that may miss the best split; they show the process’s graphs are far from bipartite, which is all the comparison needs, but they are not the exact maximum cuts.

Still open: the constant in the Ramsey number R(3, t) #

The triangle-free process and its analysis give $R(3, t) \ge (\tfrac14 - o(1))\, t^2/\ln t$, and James Shearer proved in 1983 an upper bound of $(1 + o(1))\, t^2/\ln t$. The true constant is not known. Recent work has raised the lower end of the range, and the question of whether any random construction can match the upper bound, or whether the upper bound can be improved, is open. It is a question about the same objects — triangle-free graphs with few independent points — that the counting theorem says are rare among triangle-free graphs in general, and the contrast is the point: the graphs that matter for Ramsey theory are exactly the non-typical ones. Typical graphs are easy to count and useless for building parties without triangles; the useful ones are rare, and finding the best of them is the open problem.

Typical, eventually #

Almost every triangle-free graph is bipartite, in the limit; among small ones the bipartite share falls, to 47 per cent at nine vertices, because small graphs are sparse and sparse triangle-free graphs have room for odd cycles. Exact counts — by adding vertices whose neighbourhoods are independent sets, and by the square root of a generating function — show the fall; the theorem’s mechanism, an edge inside a side costing $(3/4)^{n/2}$ in compatible graphs, explains why it must eventually reverse; and the greedy triangle-free process, which stops below the density where bipartiteness takes over, shows a random triangle-free graph that never does.