First-Fit chain partitioning of partial orders
by Gwenael Joret
Abstract: By Dilworth's theorem, every partial order P can be partitioned into w chains, where w is the maximum size of an antichain in P (called the
width of P).
A natural greedy algorithm to construct a chain partition of P with few chains is First-Fit: Consider the elements of P in some order and put each element v in the first chain that fits, that is, the first chain C where v is comparable to all elements in C.
It has been known for a long time that First-Fit uses O(w) chains on interval orders of width w, and it was conjectured that this remains
true more generally for partial orders without two incomparable chains
of length k, for fixed k (for k=2, these are exactly the interval orders).
In this talk I will present a proof of this conjecture. This is joint work with Kevin G. Milans (U. South Carolina).