A Dichotomy Theorem for First-Fit Chain Partitions

Abstract

First-Fit is a greedy algorithm for partitioning the elements of a poset into chains. Let $\text{FF}(w,Q)$ be the maximum number of chains that First-Fit uses on a $Q$-free poset of width $w$. A result due to Bosek, Krawczyk, and Matecki states that $\text{FF}(w,Q)$ is finite when $Q$ has width at most $2$. We describe a family of posets $\mathcal{Q}$ and show that the following dichotomy holds: if $Q\in \mathcal{Q}$, then $\text{FF}(w,Q)\le 2^{c(\log w{)}^2}$ for some constant $c$ depending only on $Q$, and if $Q\notin \mathcal{Q}$, then $\text{FF}(w,Q)\ge 2^w-1$.

13 pages, 1 figure