The largest family that always meets

The two rungs below ask the same question twice: how large can a collection of subsets be if no two of its members are comparable? The answer is a layer, and both the counting proof and the partition proof arrive at it.

Change one word. How large can a collection of $k$-element subsets be if every two of its members share an element?

The answer is not a layer. It is a star: fix one element and take every $k$-set containing it, which gives $\binom{n-1}{k-1}$ sets, every two of which share the fixed element. Erdős, Ko and Rado proved in 1961 that nothing beats it, provided $n \ge 2k$.

Why the hypothesis is needed #

Before anything is proved, the statement needs a condition, and the condition is where the whole shape of the answer is decided.

The condition $n \ge 2k$ is not a technicality and the failure is instant.

If $n < 2k$ then any two $k$-sets must overlap, because there is not room for two disjoint ones. So every collection of $k$-sets is intersecting, the largest is all $\binom{n}{k}$ of them, and the star is nowhere near best. At $n = 2k$ exactly, the sets come in complementary pairs and an intersecting family takes at most one from each pair — so the maximum is $\tfrac12\binom{2k}{k} = \binom{2k-1}{k-1}$, which is the star’s size, and there are enormously many families achieving it besides stars.

Above $n = 2k$ the star is not merely optimal but unique, which is the sharp form of the theorem. So the shape of the answer changes twice as $n$ grows past $2k$, and the interesting regime is the one where a $k$-set has room to miss another.

Katona’s circle #

The original proof was an induction and it is not short. Katona’s, from 1972, is a page and it is the one worth knowing, because the whole argument is a change of what is being counted.

Lay the $n$ elements round a circle, in some cyclic order. Of the $\binom{n}{k}$ possible $k$-sets, exactly $n$ are arcs of that circle — $k$ consecutive positions, starting anywhere.

At most $k$ of those $n$ arcs can pairwise meet. That is a fact about intervals on a cycle: if two arcs of length $k$ intersect, one of them starts inside the other, and a moment’s counting shows a pairwise-intersecting collection of arcs can have at most $k$ members. It is the pigeonhole principle doing its usual work — the starts of the arcs are $k$ positions and the arcs are intervals of length $k$, so more than $k$ of them forces a disjoint pair. The figure checks it by trying every collection of arcs rather than by the counting.

Now average. Let $\mathcal{F}$ be an intersecting family. Count the pairs (cyclic order, member of $\mathcal{F}$ that is an arc of it) in two ways. By orders: each cyclic order contributes at most $k$. By members: each $k$-set is an arc of the same number of cyclic orders, by symmetry. Dividing gives

$$|\mathcal{F}| \le \frac{k}{n}\binom{n}{k} = \binom{n-1}{k-1},$$

which is the star’s size. For $n = 7$ and $k = 3$ that is $\tfrac37 \times 35 = 15$, and the figure reports fifteen from an independent search.

The whole proof is one bound applied to one object — arcs on a cycle — and then averaged. Nothing about subsets is used except the symmetry that makes the averaging legitimate.

Double counting, twice #

Put the three proofs of the two theorems side by side and the family resemblance is the point.

LYM, two rungs below, counts pairs (maximal chain, member of the antichain on it). Each chain contributes at most one; each member is on a known number of chains.

Katona counts pairs (cyclic order, member of the family that is an arc). Each order contributes at most $k$; each member is an arc of a known number of orders.

Both arguments are: find an auxiliary family of objects, bound the interaction with each one, and average. The auxiliary family for antichains is the maximal chains; for intersecting families it is the cyclic orders. Choosing it is the entire art, and the choice is guided by which auxiliary object makes the local bound easy. A maximal chain meets an antichain at most once because a chain is totally ordered; a cyclic order’s arcs are limited because arcs are intervals. Neither bound needed any work, and that is the test of a good auxiliary family — the same test a well-chosen weighting passes, where the whole argument is deciding what to count.

There is a third member of the family worth naming, because it shows the method is not about orders at all. To bound the number of edges in a triangle-free graph, count pairs (vertex, edge not touching it); to bound a code’s size, count pairs (codeword, ball around it). Every one of them is: pick an auxiliary object, bound one interaction, and divide.

What the extremal object looks like #

The two answers are worth comparing directly, because the difference in shape says something about the two conditions.

The largest antichain is a layer — defined by a property every member has, with no distinguished element anywhere. It is as symmetric as the problem is: permuting the ground set permutes the layer to itself.

The largest intersecting family is a star — defined by a distinguished element that every member contains. It is not symmetric: permuting the ground set carries a star to a different star. There are $n$ stars, all of the same size, and the theorem says the maximum is achieved by each of them and by nothing else.

That difference is not decoration. A problem whose extremal answers are symmetric can often be attacked by symmetrisation — shift everything toward the middle and show nothing gets worse. A problem whose answers break the symmetry cannot, because the operation that would symmetrise a star destroys it. It is the reason Erdős–Ko–Rado is harder than Sperner, and the reason the proof had to find its symmetry somewhere else — in the cyclic orders, which are symmetric even though the answers are not.

Where the bound is checked #

Two computations appear in the figures and they are checking different things.

The local bound — at most $k$ of the $n$ arcs pairwise meet — is verified by generating every collection of arcs and keeping the intersecting ones. That is $2^n$ collections, trivial at these sizes, and it settles the step the averaging rests on.

The global bound — the largest intersecting family is $\binom{n-1}{k-1}$ — is verified by a different method entirely: build the graph whose vertices are the $k$-sets and whose edges join the pairs that meet, and find its largest clique. At $n = 7$, $k = 3$ that is a graph on thirty-five vertices, and the search finds fifteen.

The two agree, and they were computed by unrelated routes: one is a fact about intervals on a cycle, the other a clique search over subsets with no circle in it. That is the pattern this collection runs on — the argument and the exhaustion are two witnesses, and neither is evidence for the other.

What a clique search is doing #

The second computation in the figures deserves a paragraph, because it recasts the problem as one from a different subject.

Build a graph: one vertex per $k$-set, an edge between two whenever they share an element. An intersecting family is then a set of vertices every two of which are joined — a clique — and the question is the size of the largest one. So Erdős–Ko–Rado is a statement about the clique number of a particular family of graphs, known as Kneser graphs by way of their complements.

That translation is not merely a change of vocabulary. The complements — where two $k$-sets are joined when they are disjoint — are the Kneser graphs, and their chromatic number is a celebrated theorem of Lovász, proved with topology rather than combinatorics. The intersecting-family question and the colouring question are the same graph asked about twice, and the two answers came from completely different places.

Finding a maximum clique is hard in general, and it is easy here only because the graphs are small: thirty-five vertices at $n = 7$, $k = 3$, and fifty-six at $n = 8$. The search prunes with the obvious bound — stop when what remains cannot beat the best found — and finishes in milliseconds. At $n = 12$ it would not — the cost of an exhaustive search is the thing that decides which cases a figure can settle and which must be left to the argument.

What else the method reaches #

Katona’s argument is short enough to be adapted, and the adaptations are where the subject went.

Hilton–Milner. If the intersecting family is not a star — if no single element is in every member — the maximum drops sharply, to roughly $\binom{n-1}{k-1} - \binom{n-k-1}{k-1} + 1$. So a star is not merely the best; being anything else is expensive.

$t$-intersecting families. Require every two members to share at least $t$ elements and the answer is a “$t$-star” for $n$ large, and something else for $n$ small; the complete answer took until 1997 and is due to Ahlswede and Khachatrian. The pattern there — one answer for large $n$, a family of answers for small $n$, and a threshold between them — is the shape of nearly every extremal question about graphs too.

Cross-intersecting and beyond. Two families where every member of one meets every member of the other; families of permutations that agree somewhere; families of vector subspaces that intersect nontrivially — the last of which replaces subsets of a set by subspaces of a space over a field with finitely many elements, and produces the same answer with binomial coefficients replaced by their $q$-analogues.

What they share is that the answer is nearly always the obvious construction, and the work is the proof that nothing beats it — which is the same situation the Ramsey arguments are in, where the construction is easy and showing nothing does better is the work.

What the pictures cannot show #

Two small cases. The figures verify the theorem at $n = 7$, $k = 3$ and at $n = 6$, $k = 2$. A clique search over thirty-five vertices is quick and over a few hundred is not, so the exhaustion is available for the smallest cases and the theorem covers the rest.

The averaging is not drawn. One cyclic order is drawn; the argument averages over all $(n-1)!$ of them, and a picture of 720 circles would show nothing at all.

The star is described and not marked. The clique search finds a largest intersecting family and its size is asserted against the star’s; that every maximum family is a star, for $n > 2k$, is the sharp form of the theorem and no figure here establishes it.

The Hilton–Milner drop is quoted. Nothing here searches for the largest non-star intersecting family, which would need the clique search re-run with a constraint the search has no way to express.

And the failure below $n = 2k$ is not shown. A figure of a case where every two $k$-sets meet automatically would be a picture of a hypothesis rather than of a result.

Where the question comes from #

The theorem was proved in 1938 and published in 1961, and the twenty-three-year gap is part of its reputation.

Erdős, Ko and Rado found it while working on something else and did not think it worth publishing; the delay is variously attributed to the war and to nobody caring about the problem at the time. By 1961 the subject it belongs to — extremal set theory — existed, largely because Erdős had spent the intervening years inventing it, and the result had somewhere to be published into.

That is worth knowing because it explains the theorem’s position. It is not a hard result about a natural object that was pursued for years; it is an easy result about an object nobody had thought to ask about, which became foundational once a subject grew around it. The same is true of the question about how many people force a triangle: the answer is small, the argument is a page, and its importance is that it started something.

Where the ladder goes next #

The rung above stops asking extremal questions and asks a counting one. Given an order, how many ways are there to sort it — how many total orders are consistent with it?

That number is easy to define, hard to compute, and the hardest known thing about orders: counting linear extensions is complete for a counting class, so no efficient method is expected. And a conjecture about it has been open since the 1960s: that some pair of incomparable elements is always split between a third and two thirds of the extensions, so a comparison always exists that eliminates a good fraction of the possibilities.

What is worth carrying away #

Two extremal problems differing by one word can have answers of completely different shapes, and the shape of the answer determines what a proof can look like.

No two comparable has a symmetric answer, and its proofs use symmetric auxiliary objects — chains, or a chain decomposition. Every two intersecting has an answer with a distinguished element, and no symmetrisation argument can reach it; the proof instead finds symmetry in the auxiliary family, averaging over cyclic orders that are symmetric even though the extremal families are not. When the answer breaks a symmetry, the argument has to put the symmetry somewhere else — and finding where is what the proof is.