Everybody's share of the chains

Sperner’s theorem says the largest collection of subsets of an $n$-set with no two comparable is the widest layer, and the previous rung established it by looking at every collection. That settles the case at hand and explains nothing: it does not say why a layer wins, and it does not survive a change of $n$.

The explanation is one sentence and it is about chains. A maximal chain is a way of building the whole set one element at a time; there are $n!$ of them; each subset lies on a definite fraction of them; and two subsets on the same maximal chain are comparable. So an antichain’s members use up disjoint fractions of the chains, and disjoint fractions of one whole add to at most one.

The share #

Everything turns on one quantity, and it has a formula so tidy that it looks like it was arranged.

A subset of size $k$ lies on $k!\,(n-k)!$ maximal chains: $k!$ orders in which its own elements were added, and $(n-k)!$ orders for the rest. Out of $n!$ chains in total, that is a fraction

$$\frac{k!\,(n-k)!}{n!} = \frac{1}{\binom{n}{k}}.$$

The share is one over the size of the subset’s own layer, which is exactly what one would want it to be: a layer’s members split the chains evenly between them, and a layer’s shares add to one.

It is worth checking that against the extremes, because they are where a formula of this shape usually goes wrong. The empty set has $k = 0$ and share $1/\binom{n}{0} = 1$: it is on every chain, which is right, since every chain starts there. The whole set has share 1 for the same reason at the other end. A singleton has share $1/n$: a chain passes through a given singleton exactly when it adds that element first, which happens in one order out of $n$. Every case comes out, and the arithmetic is asserted in the figure rather than trusted — each element’s factorial count is compared against the reciprocal binomial coefficient.

The figure prints those shares. The empty set and the whole set are on every chain, share 1. The four singletons are on a quarter each. The six pairs are on a sixth each. Every row’s shares add to one, which the figure prints beside each row: $1 \times 1$, $4 \times \tfrac14$, $6 \times \tfrac16$, and back down.

The inequality #

Now the argument. Let $\mathcal{A}$ be an antichain. Two members of it are incomparable, so no maximal chain contains both — a chain is totally ordered and would make them comparable. Their shares are therefore disjoint sets of chains, and

$$\sum_{A \in \mathcal{A}} \frac{1}{\binom{n}{|A|}} \le 1.$$

That is the LYM inequality — Lubell, Yamamoto and Meshalkin, who found it independently in the 1950s and 60s. It is one line given the share, and it says something much sharper than Sperner’s theorem.

Sperner’s theorem follows immediately. Every term is at least $1/\max_k \binom{n}{k}$, so

$$\frac{|\mathcal{A}|}{\max_k \binom{n}{k}} \le \sum_{A \in \mathcal{A}} \frac{1}{\binom{n}{|A|}} \le 1,$$

and the antichain has at most $\max_k \binom{n}{k}$ members. The whole of the previous rung’s exhaustive search is replaced by a fraction.

The counting is inclusion-free double counting in its purest form: count the pairs (chain, member of the antichain on it) two ways, once by chains and once by members.

Why the inequality is stronger #

The bound and the inequality that produced it are not the same statement, and the gap between them is worth collecting.

LYM says more than Sperner, and the extra is worth extracting because it is the reason the inequality has a name of its own.

Sperner bounds the number of members. LYM bounds a weighted count, in which a member near the top or bottom of the order costs more than a member in the middle. An antichain consisting of the empty set alone has one member and uses up the entire budget; an antichain of six pairs has six members and uses the same budget. So LYM says that antichains far from the middle are severely limited in a way a count cannot express.

That has consequences a count cannot reach. Take an antichain with no members of size $\lfloor n/2 \rfloor$: every term is at least $1/\binom{n}{\lfloor n/2\rfloor - 1}$, so it has at most $\binom{n}{\lfloor n/2\rfloor - 1}$ members, which is strictly fewer than the Sperner bound. The middle layer is not merely the best answer; avoiding it is measurably costly.

A third consequence, and the one that made LYM worth naming: the inequality is about the sizes of the antichain’s members and knows nothing else about them. So any statement that can be phrased as a constraint on those sizes gets a bound for free. An antichain in which every member has at least three elements, or at most six, or an even number — each of those is a restriction on which terms may appear in the sum, and each therefore has an immediate bound with no new argument at all. A theorem that answers a family of questions rather than one is usually the one worth having.

It also gives the equality case for nothing, which the figure checks by exhaustion. The shares add to exactly one only when the chains are used up completely, which happens exactly when the antichain is a whole layer. There are $n+1$ of those, one per layer, and the search over all 65,536 collections finds exactly five for $n = 4$.

What the equality case is worth #

Knowing when a bound is tight is usually more useful than knowing the bound, and here it is the difference between “at most six” and “six, and only in one way”.

Sperner’s bound is $\binom{n}{\lfloor n/2 \rfloor}$, and the antichains attaining it are the middle layer — one of them for even $n$, two for odd $n$ where two layers are equally wide. That uniqueness is what makes the theorem usable as a classification rather than as a count: an extremal antichain is not merely large, it is a specific object, and any argument producing a large antichain has produced the middle layer.

The LYM equality case is the reason. Equality needs every chain covered, and covering every chain with an antichain forces the antichain to be a level set — because a chain passes through each layer exactly once, so an antichain of mixed sizes must miss some chains at the sizes it does not use.

The same weights elsewhere #

The share is $1/\binom{n}{k}$, so the whole argument runs on the binomial coefficients, and their shape decides everything about the answer.

The middle coefficient is the largest, which is why the middle layer is the largest antichain; and the coefficients fall off fast on either side, which is why an antichain avoiding the middle is penalised heavily. Both facts are visible in Pascal’s triangle and neither needs a formula.

There is a quantitative version worth knowing. The middle coefficient is about $2^n / \sqrt{n}$, so the largest antichain holds about $1/\sqrt{n}$ of all subsets — a vanishing fraction, and one that vanishes slowly. Half the subsets of a hundred-element set can be listed with no two comparable to within a factor of about ten; that is a great many more than the intuition of “no two comparable” suggests, and it is the middle coefficient being enormous rather than anything subtle about antichains.

What a share is a share of #

It is worth being careful about what the twenty-four chains are, because the count is the load-bearing part and it is easy to mis-state.

A maximal chain here is a chain that cannot be extended: it runs from the empty set to the whole set and picks up exactly one element at each step, so it has $n+1$ members and corresponds to an ordering of the $n$ elements. There are $n!$ of them, and for $n = 4$ that is twenty-four.

It is not the number of chains in the order — that is enormously larger, since any subset of any maximal chain is a chain. It is not the number of paths in the Hasse diagram between arbitrary nodes either. The maximality is what makes the count $n!$ and what makes every element’s share a clean fraction, and dropping it destroys both.

The distinction matters because the argument uses maximality twice: once to know the total is $n!$, and once to know that a chain through two comparable sets exists. Both are false for chains in general, and neither is stated in the inequality.

Where the shares come from #

There is a second reading of the share worth having, because it turns the inequality into a probability statement and probability statements generalise more easily.

Pick a maximal chain uniformly at random — equivalently, shuffle the $n$ elements and add them one at a time. For a fixed subset $A$, the probability that the chain passes through $A$ is $1/\binom{n}{|A|}$, because the chain’s set at time $|A|$ is a uniformly random subset of that size.

The events the chain passes through $A$ for $A$ in an antichain are disjoint, so their probabilities add to at most one. That is LYM again, and the change of language costs nothing.

What it buys is the method. Once the argument is choose a random chain and count the expected number of hits, the same technique applies to structures with no layers at all — and the whole subject of the probabilistic method in extremal combinatorics is that observation applied repeatedly. A colouring that must contain a monochromatic triangle and one that need not are separated by exactly this kind of expectation count, and so is the point at which a random graph acquires a property.

What the inequality does not say #

Three things worth ruling out, because each is a natural over-reading.

It does not say the middle layer is the only large antichain. It says the only antichains of the maximum size are the widest layers. Antichains one member smaller are plentiful and are not layers: remove a set from the middle layer and add a set of an adjacent size that is incomparable to what remains, and the result is a perfectly good antichain of the same size less one.

It does not extend to the divisors of a number without an argument. The subset order is graded by size and every maximal chain has the same length, which is what makes the shares add tidily. The divisors of a number form an order in which that is still true — the rank is the number of prime factors with multiplicity — but drop to an order with chains of different lengths and there is no share to speak of.

And it says nothing about finding a large antichain. LYM is an upper bound and the middle layer is a construction, and it happens here that they meet. Two rungs above, where the question becomes about intersecting families rather than antichains, the same shape of argument gives a bound and the matching construction has to be produced separately.

What the pictures cannot show #

One order, of sixteen elements. The exhaustive search tests every collection of the sixteen subsets, which is 65,536 tests; at $n = 5$ there are 32 subsets and $2^{32}$ collections, and the search is over. The inequality is a theorem for every $n$ and the verification is available for two of them.

The chains are counted and not drawn. Twenty-four maximal chains through sixteen nodes would be twenty-four paths overlapping everywhere, and the fraction on each node is the honest summary of what they do.

The equality case is verified where it is checkable. That exactly the whole layers achieve equality is confirmed here for $n = 3$ and $n = 4$ by generating every antichain; that it holds for every $n$ is the argument in the text.

The random-chain reading is not drawn. A uniformly random maximal chain is a shuffle, and a figure of one shuffle says nothing about an expectation.

And no figure shows the weighted bound biting. The claim that an antichain avoiding the middle layer is strictly smaller is arithmetic on binomial coefficients, and a picture of it would be a picture of two numbers.

Where the ladder goes next #

The rung above replaces the counting with a construction. LYM proves the bound and produces nothing; the symmetric chain decomposition cuts the cube into exactly $\binom{n}{\lfloor n/2\rfloor}$ chains, each running from size $k$ to size $n-k$, by a rule with no search in it. An antichain meets each chain at most once, so the bound is immediate — and the middle layer meets each of them exactly once, so the example arrives with the bound rather than after it.

There is a third thing the partition gives that the counting cannot: a certificate. Handed a collection of subsets, the partition lets anyone verify in one pass that it is not too large — assign each member to its chain and check no chain is used twice. The counting argument offers no such check; it proves a number and hands over nothing to test a candidate against. Dilworth’s theorem does the same job for a general order, and the value of a min-max theorem is very often the certificate rather than the equality.

That upgrade from a counting bound to a partition is the same one Dilworth’s theorem makes over the easy inequality, and it is the general shape of a good extremal argument: turn the obstruction into a structure.

What is worth carrying away #

A bound proved by counting one thing two ways is usually stronger than the statement it was invented for, and the extra strength is in the weights.

Sperner’s theorem counts members of an antichain. LYM counts their shares of the maximal chains, which is the same count with the middle layer’s members discounted — and it gives Sperner’s bound, the equality case, and a penalty for avoiding the middle, all from one line of arithmetic. The weighted version of a counting argument costs nothing to state and usually says more, and the weight to try first is the one that makes the whole thing add to exactly one.