An easy subexponential bound for online chain partitioning (Q1753118): Difference between revisions

Summary: In [Combinatorica 35, No. 1, 1--38 (2015; Zbl 1349.68324)], the first and third authors exhibited an online algorithm for partitioning an online poset of width \(w\) into \(w^{14\lg w}\) chains. We improve this to \(w^{6.5 \lg w + 7}\) with a simpler and shorter proof by combining the work of Bosek and Krawczyk [loc. cit.] with the work of the second author and \textit{M. E. Smith} [Eur. J. Comb. 34, No. 2, 474--489 (2013; Zbl 1288.06004)] on first-fit chain partitioning of ladder-free posets. We also provide examples illustrating the limits of our approach.