A Dichotomy Theorem for First-Fit Chain Partitions

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}$forsomeconstant$c$dependingonlyon$Q$,andif$Q\not\in$\mathcal{Q}$$,then$$\text{FF}$(w,Q) \ge 2^w - 1$.