Improved Lower Bounds on the On-line Chain Partitioning of Posets of Bounded Dimension

An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemerédi proved that any on-line algorithm could be forced to use (w+12) chains to partition a poset of width w. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In a survey paper by Bosek et al., it is shown that Szemerédi’s argument could be improved to obtain a lower bound almost twice as good. Variants of the problem were considered where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size d. In this paper, we prove two results. First, we prove that any on-line algorithm can be forced to use (2-o(1))(w+12) chains to partition a 2-dimensional poset of width w. Second, we prove that any on-line algorithm can be forced to use (2-1d-1-o(1))(w+12) chains to partition a poset of width w presented via a realizer of size d.