School Seminars and Colloquia

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