An antichain is a family of mutually incomparable elements. In the subset lattice, all subsets of a fixed size form an antichain. For five labels the middle layers have ten members. Could a mixture of different sizes be larger? Sperner’s theorem says no. A weighted count of maximal chains proves this without assuming that an extremal family already lies in one layer.
Predict
Predict how often a k-element set appears along a chain generated by a permutation. Read the permutation from left to right and take successive initial subsets. The set appears exactly when its k elements occupy the first k positions, in any order, and the remaining labels occupy the rest. There are k!(n−k)! such permutations. Because a chain is totally ordered, it can meet an antichain in at most one member.
Experiment
Compare layer sizes for four labels.
Subset size
Layer size
Weight per member
0 or 4
1
1
1 or 3
4
1/4
2
6
1/6
An antichain containing an endpoint uses the entire weight budget. Try a mixed family containing a singleton and several pairs, and remove every pair containing that singleton before evaluating the total weight.
Understand
Count pairs consisting of an antichain member A and a permutation chain containing it. The count is at most n!, while summing by A gives Σ over A of size (A)!(n−size (A))!. Division yields the LYM inequality Σ_A1/C(n, size (A))≤1. Every binomial coefficient is at most the middle coefficient, so the antichain has at most C(n, floor (n/2)) members. A middle layer attains equality, proving Sperner’s theorem. The weighted inequality is stronger than the final unweighted bound and retains information about which ranks the family occupies.
Apply
Dilworth’s theorem for an arbitrary finite poset says that its maximum antichain size equals its minimum number of chains in a partition. Here is a proof using the matching-cover theorem proved later. Make left and right copies of each element and join x on the left to y on the right whenever x< y. A matching of size m links elements into n−m directed paths, hence chains; cycles cannot occur in a strict order. Conversely a partition into k chains gives n−k matching edges by linking consecutive chain elements. A maximum matching has a vertex cover of the same size m by Kőnig’s theorem. The elements with neither copy in that cover form an antichain of size at least n−m. Every antichain meets each chain at most once, so both bounds coincide.
Continue
This proof makes its dependency explicit: the chain construction is immediate, while equality uses the later bipartite matching-cover theorem. Return after that proof to close the dependency rather than treating it as an unexplained black box. The terms maximum and maximal differ: a maximal antichain cannot be enlarged locally, but may be smaller than a maximum one. Likewise, a chain partition that looks natural need not minimize the number of chains. Supply both an antichain and a chain partition of the same size as an optimality certificate.
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
What is the largest antichain size in the subset lattice of six labels?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
A finite poset of eight elements has maximum matching size 5 in its strict-order split graph. Find its minimum chain-partition size.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Prove the LYM inequality for a subset antichain.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Deduce Sperner’s theorem from LYM.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Explain why a matching of size m in the split order graph gives n−m chains.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Given a vertex cover C of the split graph, show elements with neither copy in C form an antichain of size at least n−size (C).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
