The Sub-exponential Upper Bound for On-Line Chain Partitioning

Abstract

The main question in the on-line chain partitioning problem is to determine whether there exists an algorithm that partitions on-line posets of width at most w into polynomial number of chains see Trotter's chapter Partially ordered sets in the Handbook of Combinatorics. So far the best known on-line algorithm of Kierstead used at most (5 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ω</sup> - 1)/4 chains; on the other hand Szemeredi proved that any on-line algorithm requires at least (ω+1/2) chains. These results were obtained in the early eighties and since then no progress in the general case has been done. We provide an on-line algorithm that partitions orders of width ω into at most ω <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">16 log ω</sup> chains. This yields the first subexponential upper bound for on-line chain partitioning problem.