On-Line Dimension for Posets Excluding Two Long Incomparable Chains

For a positive integer k, let k + k denote the poset consisting of two disjoint k-element chains, with all points of one chain incomparable with all points of the other. Bosek, Krawczyk and Szczypka showed that for each k a parts per thousand yenaEuro parts per thousand 1, there exists a constant c (k) so that First Fit will use at most chains in partitioning a poset P of width at most w, provided the poset excludes k + k as a subposet. This result played a key role in the recent proof by Bosek and Krawczyk that O(w (16logw) ) chains are sufficient to partition on-line a poset of width w into chains. This result was the first improvement in Kierstead's exponential bound: (5 (w) -aEuro parts per thousand 1)/4 in nearly 30 years. Subsequently, Joret and Milans improved the Bosek-Krawczyk-Szczypka bound for the performance of First Fit to 8(k -aEuro parts per thousand 1)(2) w, which in turn yields the modest improvement to O(w (14logw) ) for the general on-line chain partitioning result. In this paper, we show that this class of posets admits a notion of on-line dimension. Specifically, we show that when k and w are positive integers, there exists an integer t = t(k,w) and an on-line algorithm that will construct an on-line realizer of size t for any poset P having width at most w, provided that the poset excludes k + k as a subposet.