Dilworth's theorem.md

---

categories: Graph theory ...

Dilworth's theorem states that the length of a longest [antichain](Partially ordered set#Antichain) in a [partially ordered set](Partially ordered set) $S$ is equal to the size of a minimum partition of $S$ into [chains](Partially ordered set#Chain).

If the poset is represented as a [directed acyclic graph](Directed acyclic graph), the minimum partition into chains is equivalent to the [vertex-disjoint path cover](Vertex-disjoint path cover) problem.

Note: Posets are transitive by nature. If a poset is represented in compressed form as a DAG, then the [transitive closure](Transitive closure) must be taken before computing the vertex-disjoint path cover.

Problems

• Fat Hobbits
• Nested Dolls
• Incubator ¹
• Gentrification
• Birthday ²

See also

• Vertex-disjoint path cover
• [Hall's marriage theorem](Hall's marriage theorem)

External links

• Dilworth's theorem
• Partially Ordered Sets

Footnotes

1. https://apps.topcoder.com/wiki/display/tc/SRM+557 ↩

2. http://codeforces.com/blog/entry/21203 ↩