Motivation
Among all subsets of a fixed ground set, how many can be selected if none may contain another? Choosing all subsets of one size certainly works. The middle sizes have the most subsets, suggesting a sharp answer, but it is not obvious that mixing different sizes cannot do better.
Dilworth's theorem identifies antichain size with a partition optimum, yet it does not itself compute the width of the subset poset. Here we exploit the additional symmetry of subsets. Every permutation generates a complete chain of nested subsets. Counting how often a selected subset lies on these chains weights small and large sets differently. That weighted count proves both the extremal bound and useful restrictions on families with several ranks.
Definitions
Definition 6.3.1
(Boolean levels and antichain families)
For , write and order by inclusion. Its level consists of the -element subsets, so . A family is an antichain if no two distinct members contain one another. Define its Lubell weight by
The binomial coefficient in every denominator is positive. For , the ground set is empty and the Boolean poset has one element, the empty subset.
A maximal chain in the Boolean poset contains one subset of every size from zero to . It is obtained by adding one new ground-set element at each step, so there are exactly such chains. Here maximal means it cannot be extended within the poset; Boolean maximal chains all have maximum possible size . These two meanings need not coincide in arbitrary posets.
Definition 6.3.2
(The upper shadow of one level)
For and , its upper shadow is
It records every next-level set forbidden by choosing a member of in an antichain. Several members may forbid the same next-level set, so incidences must not be counted as distinct shadow members.
Theorem/Proposition
Theorem 6.3.3
(The LYM inequality)
For every antichain ,
No restriction to a single level is required. The empty family has weight zero.
Theorem 6.3.4
(Sperner's sharp bound and equality cases)
Every antichain in has size at most . This bound is attained by a full middle level. If is even, this is the unique maximum antichain. If is odd, the two full middle levels are the only maximum antichains.
Theorem 6.3.5
(Normalized upper-shadow inequality)
For and ,
This compares proportions of consecutive levels. It does not say their raw cardinalities are always ordered the same way.
Proof sketch or proof idea
Proof
(Counting members on maximal chains)
Count pairs consisting of a member of and a maximal chain containing it. If , a generating permutation must put the elements of first, in any order, and all remaining elements afterwards, in any order. There are choices. On the other hand, each maximal chain contains at most one antichain member. Hence
Divide by to obtain LYM, including the endpoint sizes zero and .
Proof
(Double counting immediate inclusions)
For the shadow inequality, count pairs with , and . Each chosen -set has immediate supersets, while each shadow member contains at most chosen -sets. Therefore
Using gives the normalized form.
Proof
(From the weight bound to the sharp bound and its equality cases)
The binomial ratio shows the largest level size is , at one middle rank for even and two for odd . Every member of any antichain therefore contributes at least to its weight. Thus , proving the size bound. Each middle level is an antichain, so the bound is attained.
If equality holds, every member must lie on a largest level, because a member on a smaller level contributes strictly more than . For even , only one rank has size , so the family must be the whole middle level. This also handles .
For odd , consider the bipartite inclusion graph between and . Both parts have size and every vertex has degree . This graph is connected: any two -sets can be joined by repeatedly replacing one element not in the target by a missing target element, passing through their common -element union at each replacement. Every upper-level vertex has a lower neighbor, so these walks connect the whole graph. For , the graph is one edge.
A nonempty proper subset of its lower part has strictly more neighbors than its own size. Edge counting first gives at least as many. If the counts were equal, every edge at the neighbor set would already come from , and every edge at stays in that neighbor set. They would form a whole component, contradicting connectedness. Now a maximum antichain has lower portion and an upper portion avoiding its shadow. Its size is at most
A nonempty proper lower portion makes this smaller than . The lower portion must therefore be empty or the entire lower level; attaining forces the other portion accordingly. This proves the odd equality classification.
Proof X-ray
Where incomparability, unimodality and connectedness enter
Three facts do separate jobs. The chain count gives each rank- member the cost , and the antichain hypothesis is used exactly once: no maximal chain passes through two members. Nothing else about the family is used. Unimodality of the binomial row converts cost into size, since every cost is at least , so . Equality forces every inequality to be tight, which pins each member to a level of size , and for even the argument ends there. For odd the two tied levels need a further idea: a mixed family of size would need a nonempty proper with . Regularity of the inclusion graph, degree on both sides, gives only ; connectedness supplies the strict inequality that excludes the mixture.
Worked examples
Worked example 6.3.6
(Six pairs form a largest family on four elements)
The six two-element subsets of form an antichain. Each has weight , so the total is one. There are maximal chains, and each pair belongs to of them. The six groups of incidences account for all chains, each with its unique two-element member. Sperner proves no larger antichain exists; the even equality case says this full level is the only family of size six.
Worked example 6.3.7
(An admissible weight budget need not realize a rank profile)
On , suppose an antichain contains four singletons and pairs. LYM gives , hence . But the actual containment restriction is stronger. After relabeling, the singletons are . Any pair must avoid all four elements, which is impossible with only element five left. Thus . The weight inequality is necessary, not a sufficient construction rule for every proposed rank profile.
Worked example 6.3.8
(A shadow explains loss when mixing the middle ranks)
On , let be the four pairs containing element one. Its upper shadow is the six triples containing one. Both middle levels have ten elements, so the normalized sizes are and . An antichain whose two-element members are exactly these four pairs can add at most the four triples outside the shadow, reaching size at most eight. It cannot attain the optimum ten by mixing these choices. Counting incidences gives twelve from the chosen pairs; each shadow triple contains two of them, explaining the six actual shadow members.
The same proof as an expectation
Choose a uniformly random permutation and expose its prefix subsets. For a fixed subset, all sets of its rank are equally likely to be the prefix set. Its probability of appearing is therefore the reciprocal level size. Let a variable count the chosen family's members encountered by the chain. Its expected value is the sum of these appearance probabilities, exactly the Lubell weight.
For an antichain the variable is always at most one, so its expectation is at most one. This is the same finite counting proof expressed probabilistically, not a separate random-input assumption about the family. The individual appearance events need not be independent. In fact, two distinct antichain members cannot both appear on one chain, which is precisely the dependence that makes the bound work.
This viewpoint helps explain the weights. A small subset lies on a relatively large proportion of all maximal chains because its level has few choices. It therefore spends more of the chain budget than one subset on a wide middle level. The optimization compares these costs rather than assuming every set uses equal resources.
What shadow growth can and cannot imply
The normalized inequality says that the proportion occupied cannot decrease when a level family is replaced by its full upper shadow. Whether the number of sets grows depends on the relative sizes of the two levels. Below the middle, the next level is at least as large, so the shadow has at least the original cardinality. Above the middle, a smaller next level may contain fewer sets even while occupying a larger proportion of that level.
For instance, take all three pairs of a three-element ground set. Their upper shadow is just the full three-element set. The cardinality falls from three to one, while both normalized proportions equal one. Dropping the denominators would turn a correct normalized statement into a false universal cardinality claim.
The proof counts incidences with multiplicity before bounding the number of distinct neighbors. Equality in the incidence bound requires every shadow member to contain the maximum possible number of chosen predecessors. On the tied middle levels of an odd-dimensional Boolean poset, connectedness makes this extremely restrictive. That extra restriction is why a mixture cannot quietly achieve the same extremal size as a full level.
Concept lensCombinatorial
A cover of maximal chains rather than a picture of the lattice
A selected subset occupies every maximal chain through it. Distinct antichain members occupy disjoint collections of chains, so their normalized occupations add to at most the whole collection. This interpretation depends on all maximal chains and their exact counts; the number of visible paths in one small Hasse drawing is not the required sample space.
Which extremum has actually been solved?
Sperner computes the width of the Boolean poset. Dilworth then guarantees a partition of all its subsets into that many chains. The maximal chains used in the LYM proof are generally not such a partition: they overlap heavily and were counted as a symmetric family of test chains. Confusing these two uses of chains would make the argument claim a disjoint decomposition it never constructed.
Common mistake
(Inclusion-maximal is not maximum)
The proof also concerns maximum size, not merely inclusion-maximal antichains. A family that cannot accept another subset may still be small. For example, the family containing only the empty subset is inclusion-maximal, because every other subset contains it, but on a ground set with at least two elements it is smaller than the middle level. No contradiction arises: maximal forbids a one-step extension, while maximum compares all families.
Common mistakes
Counterexample mode
The LYM inequality does not imply incomparability
On , the family has weight , but its two members are comparable. The correct direction is antichain implies the inequality. The numerical inequality alone does not certify the antichain property, and must not be used as a substitute for checking containment.
Common mistake
(The empty ground set still has a subset)
Do not count the empty ground set as having no subsets: it has the empty subset. For , has one element, so the largest antichain is , of size . Treating as empty would make the bound read and break the even equality case.
Common mistake
(The shadow is one level up, not every superset)
Distinguish a next-level shadow from all strict supersets: the incidence degrees in the shadow proof rely on adding exactly one element. On , the singleton has upper shadow , two sets, matching the degree . Its strict supersets also include ; counting that set would break the incidence count .
Summary
Maximal-chain incidence counting proves a weighted restriction on every Boolean antichain. The largest rank converts it into Sperner's sharp size bound, while shadow expansion and connectedness classify equality when two middle ranks tie. The normalized shadow inequality retains information that raw cardinality comparisons can lose.
Exercises
Quick check
(List all maximum antichains on a three-element ground set and justify that the list is complete.)
The two middle ranks tie, so use the proved equality classification.
Solution · Answer
The optimum size is . Its only attaining families are all three singletons and all three pairs, by the odd equality case. Each is indeed an antichain, so both possibilities occur. Families mixing ranks may be antichains, but cannot attain this size.
Quick check
(If an antichain on a six-element ground set contains a two-element member, prove its size is at most nineteen.)
Use the larger weight of that member. Do not claim the resulting bound is necessarily attainable.
Solution · Answer
The largest level has members, while the selected two-element member has weight . If the family has size , each other member has weight at least . Thus , or . Since is an integer, . This is an upper bound under an extra condition, not a construction attaining nineteen.
Quick check
(On a five-element ground set, choose three singleton sets. Compute their upper shadow exactly and compare it with the normalized shadow lower bound.)
Count pairs containing at least one selected element.
Solution · Answer
There are pairs in total. Exactly one avoids all three selected elements: the pair of the two unselected elements. Hence the shadow has nine pairs. The normalized inequality only gives a shadow size of at least . The strict difference reflects that most shadow pairs contain fewer than the two selected singletons allowed in the incidence upper bound.