# First-Fit chain partitioning of partial orders

*Discrete Structures and Algorithms (Seminar)*

*by Gwenael Joret*

*Institution:*Université Libre de Bruxelles

*Date: Tue 25th October 2011*

*Time: 11:00 AM*

*Location: Russell Love Theatre, Richard Berry Building*

*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).