Dilworth's Theorem: Combinatorics Notes for IMO (Maths Olympiad)

Dilworth’s Theorem – Study Notes

Goal : Understand the statement, why it matters, and how to apply it in combinatorics.

1. Simple Explanation

In a partially ordered set (poset) you can look at two opposite structures:

Chains – collections of elements where each pair is comparable (one is “≤” the other).
Antichains – collections where no two elements are comparable.

Dilworth’s Theorem tells us that the size of the largest antichain and the minimum number of chains needed to cover the whole poset are the same.
In other words, if the biggest set of mutually incomparable elements has size k, then you can split the whole poset into exactly k chains, and you cannot do it with fewer.

2. Key Points

Concept	Definition	Role in Dilworth
Poset	Set (P) with reflexive, antisymmetric, transitive relation (\leq).	The universe we work in.
Chain	Subset (C \subseteq P) where ∀(x,y\in C), either (x\le y) or (y\le x).	The building blocks we try to cover (P).
Antichain	Subset (A \subseteq P) where ∀(x,y\in A), (x\not\le y) and (y\not\le x).	Measures “width” of the poset.
Width	Size of the largest antichain.	Denoted (w(P)).
Chain decomposition	Partition of (P) into disjoint chains whose union is (P).	The minimal number of chains is (w(P)).
Dilworth’s Theorem	In any finite poset (P), the minimum number of chains in a chain decomposition equals the width of (P).	Core theorem.

Why it matters

Gives a duality between “maximum” and “minimum” structures.
Useful in problems about scheduling, sorting, and graph theory (e.g., bipartite matching, Dilworth’s theorem is a corollary of König’s theorem).
Provides a constructive way: if you can find the biggest antichain, you know exactly how many chains you need.

3. Worked Example

Problem

Consider the poset (P) of all subsets of ({1,2,3}) ordered by inclusion (\subseteq).
Find:

The width (w(P)).
A chain decomposition using exactly (w(P)) chains.

Step‑by‑Step

List all elements of (P)
[ \begin{aligned} &\emptyset,;{1},;{2},;{3},\ &{1,2},;{1,3},;{2,3},;{1,2,3} \end{aligned} ]
Find the largest antichain
Two subsets are incomparable iff neither is contained in the other.
The subsets of size 1 and subsets of size 2 are incomparable with each other?
Size‑1 subsets all pairwise incomparable?
Yes, because ({1}\not\subseteq {2}) etc.
Similarly, size‑2 subsets are pairwise incomparable.
So we can take all 3 singletons or all 3 doubletons.
Hence the maximum antichain size is (3).
(w(P) = 3).
Construct a chain decomposition with 3 chains
We need to partition the 8 elements into 3 chains.
A convenient decomposition:

Chain 1 Chain 2 Chain 3

(\emptyset \subset {1} \subset {1,2} \subset {1,2,3}) ({2} \subset {2,3}) ({3})

Verify:
- Each set of columns is a chain (increasing by inclusion).
- The chains are disjoint and cover all 8 elements.
- Number of chains = (3 = w(P)).
Check optimality
By Dilworth’s theorem, we cannot cover (P) with fewer than 3 chains because the width is 3.
Thus the decomposition is minimal.

Chain 1	Chain 2	Chain 3
(\emptyset \subset {1} \subset {1,2} \subset {1,2,3})	({2} \subset {2,3})	({3})

Summary of the Example

Width (w(P)=3).
Minimum chain decomposition: 3 chains (explicitly listed above).
The decomposition respects Dilworth’s theorem.

4. Quick Revision Summary

Topic	Take‑away
Dilworth’s Theorem	In any finite poset, width (size of largest antichain) = minimum number of chains needed to cover the poset.
Key Definitions	Chain: totally ordered subset. Antichain: pairwise incomparable subset. Width: largest antichain size.
Typical Usage	• Proving existence of chain decompositions. • Bounding sizes in extremal combinatorics. • Connecting to bipartite matchings and König’s theorem.
Proof Idea	Construct a bipartite graph from the poset (copying each element twice, adding edges for comparabilities). Apply König’s theorem to obtain a minimum vertex cover → chain decomposition.
Worked Example	Subsets of ({1,2,3}): width (=3), min chain decomposition = 3 chains.
Remember	Dilworth’s theorem is a duality: “maximum antichain” ↔ “minimum chain cover”.

Tip: When solving a problem, first try to identify a large antichain. Its size immediately tells you how many chains you need. Then, build a chain cover that matches that number.

Happy studying!