On First-Fit coloring of ladder-free posets (Q691598)

A classical theorem by \textit{R. P. Dilworth} [Ann. Math. (2) 51, 161--166 (1950; Zbl 0038.02003)] states that every finite partially ordered set (henceforth \textit{poset}) of width at most \(w\) can be partitioned into \(w\) chains. This bound of \(w\) chains is tight. However, this bound of \(w\) cannot be achieved by an on-line partitioning, and the quest for such an on-line upper bound of the number of chains is ongoing. More precisely, an \textit{on-line poset \(P^{\prec}\)} is a poset \(P = (V,\leq_P)\) together with a linear (or total) ordering \((V,\prec)\) (representing the order of which a partitioning algorithm receives the elements of the poset.) Let \({\mathcal{P}}_w\) denote the class of posets that have width at most \(w\), and let \(\mathrm{val}({\mathcal{P}}_w)\) denote the smallest upper bound on the number of chains that an on-line algorithm partitions a poset from \({\mathcal{P}}_w\) into. The first sub-exponential bound for \(\mathrm{val}({\mathcal{P}}_w)\) was proved by \textit{B. Bosek} and \textit{T. Krawczyk} [``The sub-exponential upper bound for on-line chain partitioning'', in: Proceedings of the 51st annual IEEE symposium on foundations of computer science, FOCS 2010. Los Alamitos: IEEE Computer Society. 347--354 (2010; \url{doi:10.1109/FOCS.2010.40})], who showed that \(\mathrm{val}({\mathcal{P}}_w) \leq w^{14\lg w}\). One of the simplest on-line chain partitioning algorithms is First-Fit (FF), which greedily assigns each new vertex \(v_i\) to the chain \(C_j\) with the least index \(j\) such that for all \(h<i\) if \(v_h\in C_j\), then \(v_h\) is comparable to \(v_i\). For a poset \(Q\) let \(\mathrm{val}_{\mathrm{FF}}(Q,w)\) denote the smallest upper bound on the number of chains that a First-Fit on-line algorithm partitions a \(Q\)-free poset of width at most \(w\) into. A poset \(L_m\) is called an \textit{\(m\)-ladder} if its vertices are two disjoint chains, \(x_1 < \cdots < x_m\) and \(y_1 < \cdots < y_m\), such that \(x_i < y_i\) for all \(i\in\{1,\ldots,m\}\) and \(y_i\) and \(x_j\) are incomparable for \(i\leq j\leq m\) (so the Hasse diagram of \(L_m\) looks like a ``skewed'' ladder, where for each \(i\in\{i,\ldots,m\}\) the step/bar between \(x_i\) and \(y_i\) goes down from \(y_i\) to \(x_i\) at a 45 degree angle.) The main theorems of the paper are then the following (in)equalities: (i) \(\mathrm{val}_{\mathrm{FF}}(L_2,w) = w^2\), (ii) \(\mathrm{val}_{\mathrm{FF}}(L_m,2) \leq 2m\), and (iii) \(\mathrm{val}_{\mathrm{FF}}(L_m,w) \leq w^{2.5\lg w + 2\lg m}\). The last inequality yields a basis for a simpler proof of the mentioned result of Bosek and Krawczyk, that \(\mathrm{val}({\mathcal{P}}_w) \leq w^{14\lg w}\).