Orderings & Lattices · step 11 of 13

Dilworth’s theorem & chain covers

Dilworth’s theorem states that in any finite poset, the minimum number of chains needed to cover all elements equals the size of the largest antichain. One direction is easy — a chain hits each antichain at most once, so you need at least as many chains as the antichain’s size. The reverse is the substantial content, and it makes the width of a poset computable.

Practise dilworth’s theorem & chain covers free → All Orderings & Lattices subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Find a large antichainThis gives a lower bound: covering it requires at least that many chains.
Build a chain cover of matching sizePartition the elements into that many chains. Matching the bound proves both are optimal.
Stop when the numbers agreeBy Dilworth, a cover whose size equals an antichain’s size is certified minimum — no further search needed.
Use matching for larger casesA minimum chain cover corresponds to a maximum matching in a bipartite graph built from the order, computable in polynomial time.

Worked example

For the divisors of 12 under divisibility, find the minimum number of chains covering the poset.

Largest antichain: {4, 6} has size 2 — no three divisors of 12 are pairwise incomparable.
So at least 2 chains are needed.
Cover with 2 chains: 1 ∣ 2 ∣ 4 ∣ 12 and 3 ∣ 6.
Every element appears exactly once, and there are 2 chains.

Answer. The minimum chain cover has 2 chains, matching the width of 2 — exactly as Dilworth’s theorem predicts.

Where marks get dropped

These are the specific errors that cost credit on dilworth’s theorem & chain covers questions — QED's rubric penalises each of them separately.

Confusing Dilworth with Mirsky. Dilworth covers with CHAINS and matches the largest ANTICHAIN; Mirsky covers with antichains and matches the longest chain.
Producing overlapping chains. A cover is usually required to be a partition, so each element appears in exactly one chain.
Assuming a greedy longest-chain-first strategy is optimal. It often is not, which is why the matching formulation matters.

Practise this until it is automatic

Unlimited fresh questions

QED generates new dilworth’s theorem & chain covers problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Orderings & Lattices mastery is tracked so you know when this is exam-ready.

Dilworth’s theorem & chain covers — frequently asked questions

How is Dilworth’s theorem proved?

Most cleanly via König’s theorem on bipartite graphs, using the min-max duality of matchings and vertex covers. There are also direct inductive proofs.

What is the dual statement?

Mirsky’s theorem: the minimum number of antichains covering a poset equals the length of its longest chain. Its proof is much easier — group by chain height.

Where is this applied?

Scheduling with parallel machines, where chains are sequential job streams, and in bounding the size of families of sets, as in Sperner’s theorem.

The rest of Orderings & Lattices

Partial orders, Hasse diagrams, bounds, lattices. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make dilworth’s theorem & chain covers exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →