Dilworth's Theorem

Dilworth’s Theorem

Combinatorics – Beginner Friendly Study Notes

1. What is a partial order?

Think of a set of items that have a “can‑be‑before‑or‑after” relationship, but not every pair of items can be compared.

Formal idea (very simple)

• Reflexive: every item is “before or equal to” itself.
• Transitive: if A is before B and B is before C, then A is before C.
• Not necessarily comparable: some items never compare.

2. Chains and Antichains

Everyday picture

• Chain – a straight line of friends standing in a row, each next friend is taller than the previous one.
• Antichain – a group of friends standing side‑by‑side where none is taller than another (they all have the same height).

3. Statement of Dilworth’s Theorem

In a finite partially ordered set (a set that is small enough to count),
the size of the largest antichain (the most items you can pick that don’t compare)
equals
the fewest number of chains needed to cover (cover = every item belongs to at least one chain).

In plain words:

If you can’t find a big “tall‑in‑a‑row” chain, you can cover everything with only a few chains.

4. Tiny Example

Consider the set
S = {1, 2, 3, 4}
with the following comparison rule:

• 1 ≤ 3
• 1 ≤ 4
• 2 ≤ 4

No other comparisons exist.

Visualizing it

   3   4
   |  /|
   | / |
   1---2

• Chains we can build:

  1. {1, 3}
  2. {1, 4}
  3. {2, 4}

• Largest antichain (no two comparable):
  {2, 3} – size = 2 (you can’t add 1 or 4 because they compare to one of them).

• Covering with chains:
  One possible cover:

  • Chain A: {1, 3}
  • Chain B: {2, 4}

  That’s 2 chains.

Dilworth’s theorem says:

Size of the largest antichain = 2
Minimum number of chains to cover = 2

They match!

5. Why is it useful?

• Helps in scheduling where tasks have precedence constraints.
• Gives a way to split a messy set into manageable “rows” (chains).
• Provides a dual view: the same structure can be seen as both a “big spread” (antichain) and a “tight stack” (few chains).

6. A Very Simple Proof Idea (No heavy math)

1. Start with a maximum antichain (the biggest spread).
2. Build chains one by one:
   • Take an element not yet in a chain.
   • Extend it backwards and forwards using the order until you can’t go further.
3. You’ll end up with a set of chains that together touch every element.
4. The number of chains you needed can never be less than the size of the maximum antichain – otherwise the antichain would fit into fewer chains, contradicting its size.
5. Therefore, the two numbers are equal.

7. Quick Checklist for Studying

• Know the definitions: partial order, chain, antichain.
• Remember the theorem’s statement in plain English.
• Be able to draw a small poset and find its max antichain and a minimal chain cover.
• Understand the intuitive proof sketch (no need for formal proofs yet).

8. Practice Problem (Try it yourself)

Given the set T = {a, b, c, d, e} with relations:

• a ≤ c
• b ≤ c
• c ≤ e
• d ≤ e

1. Find the largest antichain.
2. Cover the set with the fewest chains.
3. Check that the two numbers match.

(Hint: draw a little diagram and look for the biggest group of incomparable items.)

Happy studying! 🎉