The fewest triangles an edge density allows

The edge that forces a triangle found the threshold. A graph on $n$ points can carry $\lfloor n^2/4 \rfloor$ edges without a triangle — split the points into two halves and join every point of one half to every point of the other — and not one edge more. That is Mantel’s theorem, from 1907, and it answers the question “how many edges before a triangle is forced?”

A threshold is only the first point of a curve. Once past it, a graph must contain triangles, and the natural next question is how many. Not whether a triangle is forced, but how many triangles are forced, at each number of edges. The question is simple to state for any graph, and for large graphs its answer is a curve that took eighty years to find.

The figure measures both quantities as proportions. The edge density $\rho$ is the share of all pairs of points that are joined; the triangle density is the share of all triples of points that form triangles. Below $\rho = \tfrac12$, the minimum is nought — that is Mantel’s theorem, in the limit. Above it, the minimum rises along a curve that is almost, but not quite, a parabola. The lower panel magnifies the difference: a row of scallops, each touching zero at a special density and bulging above it between.

One edge past the threshold #

The smallest cases can be settled by examining every graph, and they show that the curve starts with a jump.

On seven points there are twenty-one possible edges and $2^{21}$ graphs, few enough to check every one. With twelve edges — the complete bipartite graph with parts of three and four — there can still be no triangle. With thirteen, every graph has at least three triangles.

That is Hans Rademacher’s theorem from the 1940s: one edge past Mantel’s threshold forces $\lfloor n/2 \rfloor$ triangles, not one. The reason is that the extra edge must go inside one of the two halves of the bipartite graph, and every point of the other half, joined to both ends of the new edge, completes a triangle with it — about $n/2$ of them at once. The minimum does not creep up from nought; it jumps.

The same exhaustive search keeps going. Fourteen edges force six triangles, fifteen force nine, sixteen force twelve; the minimum climbs in steps of three for a while and then faster. Each value is the fewest triangles among all the graphs with that many edges, and the graphs achieving them are not random: they are complete multipartite graphs, or nearly so.

The steps of three have a reason that can be seen on the extremal graph. Start from the complete bipartite graph with parts of three and four, twelve edges and no triangle, and add edges inside the part of four. Each such edge has both ends joined to all three points of the other part, so it completes exactly three triangles. The first four additions cost three triangles each — three, six, nine, twelve — because four edges fit inside a part of four points without forming a triangle among themselves: they make a four-cycle. The fifth addition cannot avoid closing a triangle inside the part, and so it costs four, which is where the staircase steepens from twelve to sixteen. Adding edges inside the part of three would cost four each from the start, since each would see all four points opposite, which is why the minimum puts them in the larger part.

The exhaustive search agrees with this bookkeeping at every step, and the bookkeeping is the whole idea of the large-graph answer in miniature: the cheapest way to add edges past the threshold is to add them inside the largest part, and the cheapest structure overall is a multipartite graph whose parts are as nearly equal as the edge count allows.

Goodman’s parabola #

For large graphs, the first general lower bound came from a counting argument.

A. W. Goodman showed in 1959 that a graph with edge density $\rho$ has triangle density at least $\rho(2\rho - 1)$. The argument counts, for every edge, how many points are joined to both its ends: two points of degree $d_1$ and $d_2$ in a graph on $n$ points have at least $d_1 + d_2 - n$ common neighbours, because there are only $n$ points to go round. Summing over edges, and using the fact that a sum of squares of degrees is at least what it would be if all degrees were equal — the Cauchy–Schwarz inequality that how far from the average a thing can be also turns on — gives Goodman’s bound.

The computation is short enough to give. Write $d(v)$ for the degree of a point $v$ in a graph with $n$ points and $e$ edges. An edge $uv$ lies in at least $d(u) + d(v) - n$ triangles, since the neighbourhoods of $u$ and $v$ are two sets of sizes $d(u)$ and $d(v)$ inside a set of $n$ points, and so overlap in at least that many. Every triangle has three edges, so the number of triangles $T$ satisfies

$$3T \ge \sum_{uv} \big(d(u) + d(v) - n\big) = \sum_v d(v)^2 - ne,$$

because each point $v$ contributes $d(v)$ to the sum once for each of its $d(v)$ edges. The sum of squares of the degrees is smallest, for a fixed total $2e$, when all degrees are equal, which gives $\sum d(v)^2 \ge 4e^2/n$. Putting these together, $3T \ge e(4e - n^2)/n$ — and in densities, as $n$ grows, that is Goodman’s $\rho(2\rho - 1)$.

The argument loses in two places: common neighbourhoods need not be as small as possible, and degrees need not be equal. Both losses vanish on the Turán graphs, where every point has the same degree and every edge’s ends have exactly the forced common neighbours.

The bound is exact at special densities. The balanced complete $t$-partite graph — the Turán graph, which moves that only ever add edges found to be the densest graph with no complete graph on $t + 1$ points — has edge density $1 - 1/t$ and triangle density $(t-1)(t-2)/t^2$, and these satisfy Goodman’s inequality with equality. So the minimum touches the parabola at $\rho = \tfrac12, \tfrac23, \tfrac34, \tfrac45, \ldots$, the dots on the curve.

Between those densities Goodman’s bound is not attained. No graph has an edge density strictly between $\tfrac23$ and $\tfrac34$ and as few triangles as the parabola allows.

The scallops, and the graphs that make them #

Between two Turán densities, the graphs with fewest triangles turn out to be complete multipartite graphs with $t$ equal parts and one smaller part: a Turán graph on $t$ parts with an extra part growing from nothing. As the extra part grows from empty to equal size, the edge density runs from $1 - 1/t$ to $1 - 1/(t + 1)$ and the triangle density traces one scallop.

László Lovász and Miklós Simonovits conjectured in 1983 that these graphs are best possible, and gave the curve they trace. For $\rho$ between $1 - 1/t$ and $1 - 1/(t+1)$ it is

$$g_3(\rho) = \frac{(t-1)\big(t - 2\sqrt{t(t - \rho(t+1))}\big)\big(t + \sqrt{t(t - \rho(t+1))}\big)^2}{t^2 (t+1)^2}.$$

The figure checks the formula against the family: for several numbers of parts and several sizes of the extra part, the triangle density of the complete multipartite graph with those part sizes is computed directly and agrees with the formula to nine decimal places. At the ends of each interval the square root becomes an integer and the formula collapses to the Turán values. In between it bulges above Goodman’s parabola, by at most about two hundredths in the first scallop and by less in each later one.

One scallop, in numbers #

At edge density $0.7$, between the Turán densities $\tfrac23$ and $\tfrac34$, Goodman’s parabola allows a triangle density of $0.7 \times 0.4 = 0.28$. The scalloped curve says the true minimum is $0.2871$, higher by seven thousandths, and it is achieved by a complete multipartite graph with three equal parts and a fourth, smaller one, sized so that the edge density comes out at $0.7$.

Seven thousandths of all triples, on a graph with a thousand points, is more than a million triangles that Goodman’s argument allows and no graph can actually avoid. The gap is small as a proportion and large as a count, and it is exactly the gap between an averaging argument and the truth: Goodman’s bound would be attained only by a graph in which every point has the same degree and every edge’s ends share the fewest possible neighbours, and at density $0.7$ no such graph exists, because the degrees and the common neighbourhoods cannot both be as small as the averaging wants.

Proving the scallops are the floor #

Showing that no graph does better was the hard part, and it waited twenty-five years. Alexander Razborov proved it in 2008, using a method he had introduced the year before and called flag algebras.

The method treats the densities of small subgraphs — edges, triangles, paths of length two, graphs on four points — as numbers attached to a large graph, and looks for inequalities among them that hold for every graph. Some inequalities are obvious: densities are between nought and one, and the densities of all graphs on $k$ points add to one. The non-obvious ones come from a single observation: for any collection of small “labelled” pictures inside the graph, a certain matrix built from their densities is positive semidefinite, because it is an average of squares. Finding the right combination of such matrices is a semidefinite program, which a computer solves; the combination then certifies the bound, and the certificate can be checked by hand or by a second computer.

For triangles, Razborov carried out the argument in full and proved that $g_3$ is exactly the minimum. The scallops are the floor. The method has since settled dozens of problems of the same kind, and it is one of the main reasons extremal combinatorics became partly a computational subject, as four colours, and a proof nobody can read described for a different theorem.

Triangles in two colours #

The same density question has a Ramsey form. Colour every pair of points red or blue. A triangle all of one colour must exist once there are six points, as three colours force a triangle and its predecessors found; but how many such monochromatic triangles must there be, as a share of all triples?

The red edges form a graph and the blue edges its complement, and a monochromatic triangle is a triangle in one or the other. Goodman’s counting, applied to both at once, shows that at least a quarter of all triples must be monochromatic in the limit, whatever the colouring, and a random colouring achieves exactly a quarter: each triple is all red with probability $\tfrac18$ and all blue with probability $\tfrac18$. So for two colours the answer is the random one, and the averaging argument is exact — in contrast with the one-colour problem, where the structured multipartite graphs beat the averaging and produce the scallops.

Where every graph lies #

The minimum is one boundary of a region. The other is the maximum: the most triangles a graph of given edge density can have.

The maximum is simpler: put all the edges into one clique and leave the other points isolated. Then the triangle density is about $\rho^{3/2}$, and the Kruskal–Katona theorem shows that no graph does better. Every graph therefore sits in the band between $\rho^{3/2}$ above and $g_3(\rho)$ below. The figure places seventy random graphs on forty points, the balanced multipartite graphs, and a family of cliques, and every one falls inside the band, the multipartite graphs along the bottom edge and the cliques along the top.

Random graphs run up the middle, close to $\rho^3$: each triple is a triangle when all three of its pairs are joined, which happens with probability $\rho^3$ when edges are independent. Finding a threshold with two moments used that count to locate when triangles first appear in a random graph. A random graph has neither too few triangles nor too many; the extremes are reached only by the most structured graphs there are.

Few triangles means nearly none #

The minimum curve says how many triangles a dense graph must have. A companion result says what a graph with very few triangles must look like, and it is one of the most useful statements in the subject.

The triangle removal lemma, from the work of Imre Ruzsa and Endre Szemerédi in 1976, says that a graph on $n$ points with only a vanishing share of triples forming triangles can be made triangle-free by deleting a vanishing share of its edges. A graph cannot have few triangles spread thinly across many edges: if the triangles are rare, a few deletions remove them all. The lemma’s proof uses Szemerédi’s regularity lemma, and its bounds are notoriously weak, but its consequences are strong.

The most famous is a proof of Roth’s theorem — that a set of whole numbers with positive density contains three terms in arithmetic progression — which three in a row on the number line approached from the colouring side. A set without progressions is turned into a graph in which every triangle is degenerate, few in number and disjoint; the removal lemma then says the graph is nearly triangle-free after few deletions, and counting shows that is impossible if the set is dense. Counting triangles in graphs and finding progressions in sets of numbers turn out to be the same problem in different clothing.

What the pictures cannot show #

The exhaustive minima are exact only on seven points. The search over all $2^{21}$ graphs is complete, and Rademacher’s jump is visible in it; for large graphs the curve is a statement about limits of densities, which no finite search can reach.

The formula is checked against its extremal family, not against all graphs. The figure confirms that the multipartite graphs trace the curve; that nothing goes below it is Razborov’s theorem, whose certificate is a semidefinite computation not reproduced here.

Densities are limits. For a graph with $n$ points the densities differ from their limiting values by terms of order $1/n$, which is why the forty-point graphs in the region figure sit slightly off the curves, and why the checks allow a small tolerance for them.

Still open: every complete graph at once #

Replace the triangle by a complete graph on $r$ points, and ask for the fewest copies of it at each edge density. The Lovász–Simonovits construction — equal parts and one smaller part — gives a scalloped curve for every $r$, and the natural conjecture is that it is always the minimum.

For $r = 4$ it was proved by Vladimir Nikiforov in 2011, and in 2016 Christian Reiher proved it for every $r$, by an argument that avoids flag algebras altogether. What remains open is the structure of the extremal graphs themselves: at a given edge density there turn out to be many graphs, not just the multipartite ones, that come within a vanishing amount of the minimum, and a description of all of them — the stability question — is still being worked out. The same questions for cycles are what the densest graph without a square began for the four-cycle’s threshold. The analogous question for counting a non-complete graph, such as a cycle of length four or a path, is open in general, and for most small graphs the minimum-count curve is not known at all.

A threshold is the first point of a curve #

The habit worth keeping is to turn a yes-or-no threshold into a count.

Mantel’s theorem says when triangles must appear. Asking how many must appear, at every density, turns one number into a curve, and the curve turns out to carry much more structure than the threshold: a jump just past it, a parabola that bounds it, and scallops between the points where the parabola is exact. Every scallop is a family of graphs being optimal in turn, and proving that no other graph does better needed a method that did not exist when the curve was first guessed.