The widest layer and the longest chain

Take the sixteen subsets of a four-element set and order them by inclusion. Some pairs are comparable — one contains the other — and most are not. How large can a collection of subsets be if no two of them are comparable?

There is an obvious candidate: take all six subsets of size two. No two-element set contains another, so nothing in that collection is comparable to anything else in it. Six.

The question is whether any less obvious collection does better — one taking some sets of size one, some of size three, and dodging the comparabilities. Sperner’s theorem says no, and the search says no for this case, and the two say it for different reasons.

The vocabulary, and one collision worth naming #

A partial order is a way of saying “at most” that need not compare everything: reflexive, transitive, and never saying both $a \le b$ and $b \le a$ unless $a$ and $b$ are the same. Subsets under inclusion, whole numbers under divisibility, and tasks under “must be done before” are the standard three.

A chain is a collection in which every two members are comparable. An antichain is one in which no two are.

A layer of the subset order is the collection of all subsets of one size, and every layer is an antichain — checked in the figure rather than argued, by testing every pair in the widest layer for comparability. That is the easy direction of Sperner’s theorem: the widest layer gives a lower bound of $\binom{n}{\lfloor n/2 \rfloor}$ on the largest antichain.

One collision, because it will otherwise mislead. Sperner’s lemma and Sperner’s theorem are different results by the same person. Three colours force a triangle is Sperner’s lemma, about a coloured triangulation, and it is the combinatorial engine behind Brouwer’s fixed-point theorem. This essay is Sperner’s theorem, about the widest layer of a lattice. Nothing about one is evidence for the other, and the site’s own vocabulary rule applies: a shared name is not a shared object.

The harder direction #

Sperner’s proof is a counting argument over maximal chains, and it is short enough to give in full.

A maximal chain in the subset order runs from the empty set to the whole set, adding one element at a time, so it is exactly an ordering of the $n$ elements: there are $n!$ of them. A subset of size $k$ lies on $k!(n-k)!$ of those chains — $k!$ ways to have added its elements, $(n-k)!$ ways to add the rest.

Now let $\mathcal{A}$ be an antichain. No maximal chain can contain two members of $\mathcal{A}$, because any two sets on a chain are comparable. So the chains through members of $\mathcal{A}$ are all distinct, and

$$\sum_{A \in \mathcal{A}} |A|!\,(n - |A|)! \;\le\; n!,$$

which rearranges to $\sum_{A} 1/\binom{n}{|A|} \le 1$. Every binomial coefficient is at most the middle one, so each term is at least $1/\binom{n}{\lfloor n/2\rfloor}$, and the number of terms is at most $\binom{n}{\lfloor n/2 \rfloor}$.

That inequality — the LYM inequality, after Lubell, Yamamoto and Meshalkin — is stronger than the theorem it proves, and it is the reason the equality case can be pinned down: equality forces every member of $\mathcal{A}$ to have the same size, so the only maximum antichains are the middle layers.

The other theorem, which gives the same number #

Now a different question about the same order. Instead of asking for the largest antichain, ask for the fewest chains needed to cover everything.

Every chain meets an antichain at most once, so the number of chains needed is at least the size of the largest antichain. That is the easy half, and it is the same easy half as everywhere else in this corner of the subject: a maximum is at most a minimum, for a reason that fits on one line.

Dilworth’s theorem, from 1950, is that the two are equal.

The proof of the hard half is a matching argument, and it is worth seeing what it converts the problem into. A cover by chains is the same thing as a choice of “next element” links, no two of which start at the same place or end at the same place — follow the links and the chains fall out. So the fewest chains is the number of elements minus the largest such set of links, which is a maximum matching in a bipartite graph whose two sides are both copies of the order.

That is one bottleneck and nothing else’s object, and by the bottleneck is the whole story it is a flow problem with a certifying cut. Dilworth’s theorem is the min-max theorem for flows, transported to orders — which is the standard modern way to prove it, and is not how Dilworth proved it.

Two theorems that are not the same theorem #

Sperner and Dilworth are easy to run together and they are different.

Sperner is about one specific order — the subsets of a set — and gives an exact number, $\binom{n}{\lfloor n/2\rfloor}$. It is false for orders in general: the divisors of 36 have a largest antichain of three, which is the widest layer, but the divisors of 60 have a largest antichain of four while their widest layer holds four as well — and it is easy to build orders where no layer is largest at all, because a general order has no layers.

Dilworth is about every finite order and gives no number; it says two quantities agree without computing either. Applied to the subsets it says that $\binom{n}{\lfloor n/2\rfloor}$ chains suffice to cover all $2^n$ subsets, which is a genuine theorem — the symmetric chain decomposition — and does not follow from Sperner alone.

So each supplies what the other lacks. Sperner names the number for one order; Dilworth says what that number means for any order.

What the equality is good for #

A min-max theorem earns its place by proving things that were not stated in its language, and Dilworth’s does so immediately.

Erdős and Szekeres, 1935. Any sequence of more than $(r-1)(s-1)$ distinct numbers contains an increasing subsequence of length $r$ or a decreasing one of length $s$. The usual proof labels each position with a pair of numbers and applies the pigeonhole principle. The Dilworth proof is shorter: order the positions by “$i$ comes before $j$ and $a_i < a_j$”. A chain in that order is an increasing subsequence; an antichain is a decreasing one. If the longest increasing subsequence has length at most $r - 1$, then every chain is short, so by Dilworth the whole sequence is covered by at most $s - 1$ antichains — and one of those must hold more than $r-1$ elements if there are more than $(r-1)(s-1)$ altogether. That is the decreasing subsequence.

The conversion is the whole proof, and it is a conversion of vocabulary rather than an argument. Something that reads as a statement about sequences turns out to be the statement that a certain order cannot have both short chains and few antichains.

Mirsky’s theorem is the dual and is much easier: the fewest antichains covering an order equals the length of the longest chain. The proof is one paragraph — label each element by the length of the longest chain ending at it, and the labels partition the order into antichains. That asymmetry between the two directions is characteristic: covering by chains is hard because chains are long and thin and can be assembled in many ways, while covering by antichains has a canonical answer nobody has to search for.

Where the divisor order comes from #

The divisors of $36 = 2^2 3^2$ under divisibility form a three-by-three grid: a divisor is $2^a 3^b$ with $a$ and $b$ each between 0 and 2, and one divides another exactly when both exponents do. The shape of a number’s divisors draws that grid and reads the divisor count off it.

That is why the picture for 36 looks so much like the picture for a set of two elements repeated: it is the product of two chains of length three, and products of chains are the best-behaved orders there are. The widest layer is the largest antichain, the symmetric chain decomposition exists, and everything Sperner says about subsets has an analogue.

The divisors of 60 break the pattern gently — $60 = 2^2 \cdot 3 \cdot 5$ is a product of three chains of lengths 3, 2 and 2, which is still a product but no longer a square one, and the antichain sizes stop being symmetric about a middle. Divisors of a squarefree number, like $30 = 2 \cdot 3 \cdot 5$, reproduce the subset order exactly, because choosing a divisor is choosing a subset of the primes.

Why this is the same shape as everything else in the corner #

Four theorems on this site now have the form “a largest something equals a smallest something else”:

One bottleneck and nothing else — largest matching equals smallest deficiency. The bottleneck is the whole story — largest flow equals smallest cut. Two numbers that have to meet — a linear programme’s optimum equals its dual’s. And Dilworth — largest antichain equals fewest chains.

They are not analogies. Each can be derived from any of the others by a construction, and the constructions are short. What that means in practice is that a new min-max statement is usually proved by exhibiting the network rather than by inventing an argument, and the work is in seeing which network.

The reason to keep them as separate essays anyway is that the objects differ, and the certificate is different in each. A cut is a set of roads; a deficient set is a set of jobs; an antichain is a set of incomparable elements. Knowing that they are the same theorem does not tell anybody what to look for in a particular problem.

What an order is missing #

It is worth saying what a partial order does not have, because both theorems here are about coping with the absence.

A total order — the whole numbers, say — has no interesting antichains at all: any two elements are comparable, so every antichain has one member, and Dilworth’s theorem says the order is one chain, which it is. Everything in this essay is trivial for a total order.

What makes an order partial is the pairs it declines to compare, and the two theorems measure that declining in opposite directions. The largest antichain counts how many things can be mutually incomparable at once — how wide the order is. The longest chain counts how deep it goes. Mirsky’s theorem says depth controls the antichain cover; Dilworth’s says width controls the chain cover; and a total order is the case where width is 1 and depth is everything.

The subset order on $n$ elements is the standard example of an order that is wide and shallow: depth $n + 1$, width $\binom{n}{\lfloor n/2\rfloor}$, which grows like $2^n/\sqrt{n}$. Almost all of the order sits in a narrow band of layers near the middle — a fact that shows up again wherever binomial coefficients do, and is the same concentration a bell curve assembled out of coin flips draws for its own reasons.

Where they came from #

Sperner proved his theorem in 1928, as a lemma. He wanted it for a question about set systems and the theorem is stated in the paper as a step.

Dilworth’s paper is 1950 and its motivation was lattice theory rather than combinatorics — he was studying the structure of certain algebraic lattices and needed the chain decomposition. The combinatorial reading came afterwards, and Mirsky’s dual theorem — fewest antichains equals longest chain, which is much easier — came in 1971.

The LYM inequality was found three times independently, in 1954, 1963 and 1963, which is a familiar pattern for a statement that is easy once the right sum is written down and invisible before.

What the pictures cannot show #

The exhaustive antichain search examines every subset of the order, which at sixteen elements is 65,536 tests and at thirty-two would be four billion. So the figures are honest for the orders drawn and the method does not extend; Sperner’s theorem is what covers the rest, and it covers only the subset order.

The chain decompositions drawn are the ones a particular matching produced. Others exist — the divisors of 36 can be cut into three chains in more than one way — and nothing in the picture indicates that the decomposition is a choice while its size is not.

And every order here is finite. Dilworth’s theorem holds for infinite orders with a largest antichain of finite size, and fails without that hypothesis in ways that need the axiom of choice to discuss; none of that is visible in a diagram with nine nodes.

The ladder from here #

Below: the shape of a number’s divisors, which builds the divisor order, and two injections make a bijection, where chains are used to cut a different structure apart. Sideways: one bottleneck and nothing else and the bottleneck is the whole story, the matching and flow members of the same family, and three colours force a triangle, which is Sperner’s other theorem. Above: the LYM inequality and its equality case, symmetric chain decompositions, Mirsky’s dual theorem, and the Erdős–Ko–Rado theorem, which asks the same question of intersecting families.

What is worth carrying away #

The largest antichain in the subset order is a layer, and the surprise is that it is only a layer — that no combination of sizes beats the best single size. The LYM inequality explains why: each member of an antichain uses up a fixed share of the maximal chains, the share is smallest for middle-sized sets, and the shares must add to at most one.

Dilworth’s theorem says the number so obtained is not merely a bound but a description: the order can actually be cut into exactly that many chains, so the antichain is not just large, it is a complete obstruction. That upgrade from bound to structure is what these min-max theorems are for, and it is why the certificate matters more than the number.