Series

Extremal graphs — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. The most triangle-free edges on 6 points. A graph on 6 points carrying 9 edges and no triangle, found by examining every graph on those points, with the two sides its edges cross between drawn apart.

    The edge that forces a triangle

    A graph on six points can carry nine edges with no three of them closing a triangle. It cannot carry ten. The bound is n²/4, the graphs that achieve it are all the same shape, and both facts fall out of examining every graph there is.

    part 1 · discrete
  2. Zykov's moves, from 10 edges to 16. 6 panels showing a graph on 7 points with no complete graph on 4, changed one move at a time; the edge count rises 10, 11, 12, 13, 14, 16 and ends at Turán's graph.

    Moves that only ever add edges

    Turán's theorem says the densest graph avoiding a complete graph on r + 1 points is the balanced r-part graph. Zykov's proof finds it by a sequence of moves — turn a point into a copy of a better-connected one it is not joined to — each of which adds edges and none of which can create the forbidden clique. A second proof spreads a unit of weight over the points and gets the same bound from a maximum.

    part 2 · discrete
  3. The most edges with no four-cycle. Points for n = 2 to 9: the largest number of edges with no four-cycle, 1, 3, 4, 6, 7, 9, 11, 13, between the counting bound above and ½n^(3/2) below, far under the complete graph's count.

    The densest graph without a square

    Forbid four points joined in a cycle and a graph can keep only about ½n^(3/2) of its edges — far fewer than the quarter of all pairs a triangle-free graph keeps. Counting pairs of neighbours proves the ceiling in two lines. What reaches it is not a random graph but a finite geometry: the points of a projective plane, joined when they are orthogonal.

    part 3 · discrete
  4. The fewest triangles a graph can have at each edge density. Razborov's minimum triangle density: 0.55: 0.0730, 0.6: 0.1415, 0.7: 0.2871, 0.75: 0.3750, 0.8: 0.4800, 0.9: 0.7200; it equals Goodman's bound at 1 − 1/t.

    The fewest triangles an edge density allows

    Half of all possible edges can be drawn without a single triangle. One more, and triangles appear — not one but several at once. Push the density further and the question becomes a curve: for every share of edges, the fewest triangles a large graph can hold. The answer is a string of scallops, touching a simple parabola at the densities of the balanced multipartite graphs and bulging above it between them. It was guessed in the 1980s and proved in 2008 by a method that turns counting into positive-definite matrices.

    part 4 · discrete
  5. The Hoffman–Singleton graph: five pentagons, five pentagrams. Fifty vertices of degree seven and girth five, built from five pentagons and five pentagrams joined by the rule j of pentagon h to h·i + j of pentagram i.

    As many points as two steps allow

    In a graph where every point has d neighbours and every point is within two steps of every other, there can be at most d² + 1 points — one, its d neighbours, and d(d − 1) more reached through them. Graphs that meet the bound exactly are rare to the point of absurdity. The pentagon does it for d = 2, the Petersen graph for d = 3, a fifty-point graph found in 1960 for d = 7, and an eigenvalue argument proves there is nothing else — except possibly one graph with 3,250 points and 57 neighbours each, which nobody has found or ruled out.

    part 5 · discrete
  6. The bipartite share falls before it rises. n=1: 1 of 1 (100.00%); n=2: 2 of 2 (100.00%); n=3: 7 of 7 (100.00%); n=4: 41 of 41 (100.00%); n=5: 376 of 388 (96.91%); n=6: 5177 of 5789 (89.43%); n=7: 103237 of 133501 (77.33%); n=8: 2922446 of 4682270 (62.42%); n=9: 116011231 of 246348115 (47.09%).

    Triangle-free, and two-sided eventually

    Every graph with no triangle and the most edges possible is bipartite. Erdős, Kleitman and Rothschild proved that almost every triangle-free graph is bipartite too — and yet among the 246,348,115 triangle-free graphs on nine labelled vertices, fewer than half are. The share falls before it rises, and the reason is that small graphs are sparse.

    part 6 · discrete
  7. No graph has fewer four-cycles than chance. random p=0.092 t(C4)=0.00141 p^4=0.00007; random p=0.143 t(C4)=0.00344 p^4=0.00042; random p=0.112 t(C4)=0.00203 p^4=0.00016; random p=0.112 t(C4)=0.00276 p^4=0.00016; random p=0.112 t(C4)=0.00266 p^4=0.00016; random p=0.112 t(C4)=0.00266 p^4=0.00016; random p=0.306 t(C4)=0.01739 p^4=0.00878; random p=0.378 t(C4)=0.03223 p^4=0.02032; random p=0.316 t(C4)=0.02140 p^4=0.01001; random p=0.276 t(C4)=0.01400 p^4=0.00576; random p=0.245 t(C4)=0.01249 p^4=0.00360; random p=0.235 t(C4)=0.01182 p^4=0.00303; random p=0.490 t(C4)=0.07476 p^4=0.05755; random p=0.469 t(C4)=0.06862 p^4=0.04854; random p=0.449 t(C4)=0.05685 p^4=0.04064; random p=0.520 t(C4)=0.09126 p^4=0.07335; random p=0.480 t(C4)=0.07648 p^4=0.05290; random p=0.490 t(C4)=0.08080 p^4=0.05755; random p=0.673 t(C4)=0.23074 p^4=0.20572; random p=0.724 t(C4)=0.29628 p^4=0.27550; random p=0.673 t(C4)=0.23511 p^4=0.20572; random p=0.612 t(C4)=0.16150 p^4=0.14051; random p=0.633 t(C4)=0.19013 p^4=0.16020; random p=0.694 t(C4)=0.25750 p^4=0.23181; bipartite p=0.500 t(C4)=0.12500 p^4=0.06250; bipartite p=0.408 t(C4)=0.08330 p^4=0.02775; bipartite p=0.337 t(C4)=0.05670 p^4=0.01286; structured p=0.462 t(C4)=0.05189 p^4=0.04538; structured p=0.214 t(C4)=0.03389 p^4=0.00211; structured p=0.429 t(C4)=0.06778 p^4=0.03374; structured p=0.071 t(C4)=0.00036 p^4=0.00003

    No graph is poorer in squares than chance

    Take any graph with a fixed share of its possible edges and count how often four points chosen in order close up into a ring. However the edges are arranged — in cliques, in two-sided blocks, at random — the count never falls below what a random graph of the same density gives. Sidorenko conjectured that the same holds for every pattern without an odd cycle. For a triangle it is false; for a path or a ring of four it takes two lines; for K₅,₅ with a ten-cycle removed nobody knows.

    part 7 · discrete

All series