- Series
- Graph Theory Seminar
- Time
- Thursday, March 10, 2011 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Kevin Milans – University of South Carolina
- Organizer
- William T. Trotter

First-Fit is an online algorithm that partitions the elements of a poset
into chains. When presented with a new element x, First-Fit adds x
to the first chain whose elements are all comparable to x. In 2004,
Pemmaraju, Raman, and Varadarajan introduced the Column Construction
Method to prove that when P is an interval order of width w,
First-Fit partitions P into at most 10w chains. This bound was
subsequently improved to 8w by Brightwell, Kierstead, and Trotter, and
independently by Narayanaswamy and Babu.
The poset r+s is the disjoint union of a chain of size r and a chain
of size s. A poset is an interval order if and only if it does not
contain 2+2 as an induced subposet. Bosek, Krawczyk, and Szczypka
proved that if P is an (r+r)-free poset of width w, then First-Fit
partitions P into at most 3rw^2 chains and asked whether the bound
can be improved from O(w^2) to O(w). We answer this question in
the affirmative. By generalizing the Column Construction Method, we
show that if P is an (r+s)-free poset of width w, then First-Fit
partitions P into at most 8(r-1)(s-1)w chains.
This is joint work with Gwena\"el Joret.