The cube cut into chains

The counting argument proves that no antichain of subsets beats the middle layer, and it does so by adding fractions. What it produces is a number. What it does not produce is a way of checking a candidate: handed a collection of subsets and asked whether it is too large, the inequality offers nothing to run.

A symmetric chain decomposition produces one. Cut the whole order into chains, each running from some size $k$ up to size $n-k$. An antichain meets each chain at most once — two elements of one chain are comparable — so it has at most as many members as there are chains. The count of chains is $\binom{n}{\lfloor n/2\rfloor}$, which is Sperner’s bound, and the middle layer meets every chain exactly once, which is Sperner’s example. Both come out of one construction.

The rule #

The construction is due to de Bruijn, Tengbergen and Kruyswijk in 1951, and the bracket form of it is the one worth remembering because it needs no memory of what came before.

Write a subset of $\{1, \ldots, n\}$ as a string of $n$ brackets: a closing bracket at position $i$ when $i$ is in the set, an opening bracket when it is not.

Match the brackets in the ordinary way — each closing bracket matches the nearest unmatched opening bracket to its left. What is left over is some closing brackets near the front, which had nothing to match, and some opening brackets near the back.

The next set up the chain adds the leftmost unmatched opening bracket. The chain starts at the set with no unmatched closing brackets and ends at the set with no unmatched opening ones.

That is the whole rule. For $n = 4$ it produces six chains, one of length five, three of length three and two of length one — and the figure checks that they cover all sixteen subsets with none appearing twice.

The lengths are worth a look. One chain of length five, three of length three, two of length one: $5 + 9 + 2 = 16$, which is the number of subsets. The number of chains of each length is a difference of binomial coefficients — one chain from size 0 to size 4, three from size 1 to size 3, two from size 2 to size 2 — and $1, 3, 2$ is $\binom{4}{0}$, $\binom{4}{1} - \binom{4}{0}$, $\binom{4}{2} - \binom{4}{1}$. Those differences are what the last section of this essay is about.

Why the chains are symmetric #

Say a subset’s string has $p$ unmatched closing brackets, $q$ unmatched opening brackets, and $m$ matched pairs, so $2m + p + q = n$.

Moving down the chain removes the rightmost unmatched closing bracket, so the bottom of the chain has $p = 0$ and its size is $m$ — one element per matched pair, since each matched pair contributes one closing bracket. Moving up adds unmatched opening brackets, so the top has $q = 0$ and its size is $m + q$ where $q$ was the original count, which is $n - m$.

So the chain runs from size $m$ to size $n - m$: symmetric about the middle, and therefore passing through the middle layer exactly once. Every claim in that paragraph is checked in the figure, element by element, rather than argued from the string.

The count follows. Each chain contains exactly one element of the middle layer, and every element of the middle layer is on some chain, so the number of chains is the size of the middle layer, $\binom{n}{\lfloor n/2\rfloor}$.

What the partition gives that the count does not #

A construction and a bound answer the same question and are not the same object, and the difference is worth enumerating rather than asserting.

Three things, and each is a reason to prefer a construction to a bound. The general principle is the one Dilworth’s theorem states: an obstruction that can be exhibited as a structure is worth more than the number it bounds.

A certificate. Handed a collection of subsets, assign each to its chain and check no chain is used twice. That is a linear-time verification that the collection is an antichain of legitimate size, and it needs no arithmetic. The counting argument verifies nothing.

The distinction is the ordinary one between a proof of impossibility and a witness of it. A bound says there is no antichain of seven; a partition into six chains says here is why, and here is the pigeonhole to point at. The second can be handed to somebody who does not accept the first, and it is checkable by somebody who cannot follow the argument at all — which is what makes it a certificate rather than merely an explanation.

The example, for free. The bound and the antichain achieving it come out of the same construction, because the middle layer is exactly a transversal of the chains. A bound with no matching example leaves open whether it is tight, and half of extremal combinatorics is the gap between the two. A bound on how many people are needed to force a monochromatic triangle and a colouring showing one fewer will not do are two separate pieces of work; a construction that supplies both at once is worth a great deal.

Generalisations the count cannot reach. The largest collection of subsets with no $k+1$ of them forming a chain is the union of the $k$ widest layers — Erdős’s theorem, from 1945 — and the symmetric chain decomposition proves it in one line: take at most $k$ from each chain, and there are $\binom{n}{\lfloor n/2\rfloor}$ chains of which the long ones supply $k$ each. The LYM inequality does not prove that; the partition does.

Following one chain #

Working the rule by hand on one subset is the fastest way to see why it terminates, and it is worth doing once.

Take $n = 6$ and the subset $\{2, 3, 6\}$. Its string is ()) ()( without the spaces: opening at 1, closing at 2 and 3, opening at 4 and 5, closing at 6. Matching, position 2 takes position 1; position 3 has nothing to its left unmatched, so it is an unmatched closing bracket; position 6 takes position 5; position 4 is an unmatched opening bracket.

So there is one unmatched closing bracket at position 3 and one unmatched opening bracket at position 4. Going up adds position 4, giving $\{2,3,4,6\}$; that string has no unmatched opening bracket left, so it is the top. Going down removes position 3, giving $\{2, 6\}$, which has no unmatched closing bracket and is the bottom.

The chain is therefore $\{2,6\} < \{2,3,6\} < \{2,3,4,6\}$, running from size 2 to size 4 in a six-element set — symmetric, as promised, with two matched pairs.

Notice that the matched pairs never move. They are the part of the string the chain does not touch, and they are what tells the rule which chain a subset belongs to: two subsets are on the same chain exactly when their matched pairs are in the same places.

The rule is a bijection #

The bracket construction is doing something more than partitioning, and naming it explains why the same idea recurs.

The map subset $\mapsto$ (its chain, its position on it) is a bijection between the $2^n$ subsets and the pairs (chain, height). Counting the pairs gives

$$2^n = \sum_{m} \binom{n}{m} \cdot 1 \quad\text{re-read as}\quad 2^n = \sum_{\text{chains}} (\text{length of chain}),$$

and grouping the chains by their bottom size turns that into an identity between binomial coefficients. Counting the same set two ways is the whole method, and it is the method the rung below used to get the inequality — there the two ways were “by chain” and “by antichain member”, here they are “by subset” and “by chain and height”. A construction that partitions a set is always an identity waiting to be read off, because the parts have to add up.

So the decomposition is a combinatorial proof of an identity, and the identity is the one saying that the number of chains starting at size $m$ is $\binom{n}{m} - \binom{n}{m-1}$.

That number is a ballot number, and the bracket matching is why: strings with no unmatched closing bracket in any prefix are exactly the ones a ballot count stays ahead in. The chains of a symmetric chain decomposition are indexed by the same objects that count the ways of pairing brackets — and the Catalan numbers appear here for exactly the reason they appear there, which is that both are questions about matching.

What else can be cut this way #

The subset order is not the only one with a symmetric chain decomposition, and knowing which orders have one is a subject.

An order is rank-symmetric when its layers have the same sizes read up or down, rank-unimodal when the sizes rise and then fall, and it has the Sperner property when its largest antichain is its widest layer. A symmetric chain decomposition implies all three, and the implication is one-directional: there are orders with the Sperner property and no such decomposition.

The divisor lattice of any number has one, which is the same construction applied to a product of chains — the divisors of a number are a product of one chain per prime, and a product of orders with symmetric chain decompositions has one, built by a rule that combines them. The partition lattice does not, and whether it even has the Sperner property was open for decades and is now known to fail for large enough ground sets. That failure is worth noticing because the partition lattice looks so much like the subset lattice: both are graded, both are rank-unimodal, both have a top and a bottom, and one has the property while the other does not. The resemblance between two orders is a poor guide to whether an argument transfers, and there is no shortcut past checking.

What the pictures cannot show #

No chain is followed. The worked example in the text traces one subset up and down its chain by hand; the figures show the resulting partition and never the rule being applied, because a rule applied to one element is a picture of an arrow.

Small orders only. The figures draw sixteen and thirty-two subsets; the construction is defined for every $n$ and the picture becomes unreadable at $n = 6$, where there are sixty-four subsets and twenty chains.

The bracket strings are not printed. The rule is stated in the text and the figure shows its output — which chains result — because a Hasse diagram with sixteen bracket strings on it is a diagram with nothing visible.

The generalisation is described and not drawn. That the union of the $k$ widest layers is the largest chain-free-of-length-$k{+}1$ collection follows from the partition in one line, and illustrating it would need a second figure with $k$ elements marked on each chain.

The verification claim is not demonstrated. The certificate argument says a candidate collection can be checked in one pass by assigning each member to its chain; no figure runs that check on a candidate, and the mode instead verifies the properties of the partition itself.

And the chains are not canonical. The bracket rule produces one symmetric chain decomposition; there are others, and nothing in Sperner’s theorem picks this one out. It is chosen because it needs no search.

Where the ladder goes next #

The rung above changes the question rather than the method. Instead of no two comparable, ask for every two intersecting: what is the largest family of $k$-element subsets in which every two share an element?

The answer is a star — all the sets containing one fixed element — and the proof is a counting argument of exactly the shape of the one two rungs below, run over cyclic orders instead of over chains. That is Erdős–Ko–Rado, and the change from “layer” to “star” as the extremal object is the interesting part — a level set has no distinguished element and a star is defined by one: a small change to the question moves the answer from a level set to something with a distinguished point in it.

What the rule is not doing #

Two clarifications, because the bracket rule is easy to over-read.

It is not sorting. The chains are not produced by any greedy procedure that walks up the order picking elements; each subset’s chain is determined by the subset alone, in time proportional to $n$, with no reference to any other subset. That is what makes the decomposition constructible for $n = 40$ as easily as for $n = 4$, and it is the property a search-based method would not have.

And the brackets are not a coincidence of notation. Encoding in as a closing bracket and out as an opening one is a choice, and the opposite choice produces the reflected decomposition. What matters is that the encoding turns “which chain” into a matching problem, and matching is the one operation on strings that produces a canonical pairing without a search. Every construction in this family — the ballot sequences, the parenthesisations, the paths that stay above a diagonal — is the same encoding applied to a different question.

What is worth carrying away #

A partition is a stronger object than a bound, and when both are available the partition is what to keep.

The counting argument proves that an antichain has at most $\binom{n}{\lfloor n/2\rfloor}$ members. The chain decomposition proves the same thing, produces the collection achieving it, supplies a way to check any candidate, and generalises to the question about longer chains that the counting cannot touch. The extra content is in the word exactly — a partition says where every element went, and a bound says only how many there were.