On-Line Dimension for Posets Excluding Two Long Incomparable Chains

作     者：Felsner, Stefan Krawczyk, Tomasz Trotter, William T. 

作者机构：Tech Univ Berlin Inst Math D-10623 Berlin Germany Jagiellonian Univ Fac Math & Comp Sci PL-30348 Krakow Poland Georgia Inst Technol Sch Math Atlanta GA 30332 USA 

出 版 物：《ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS》 (序；有序集理论杂志)

年 卷 期：2013年第30卷第1期

页      面：1-12页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：On-line algorithm Partially ordered set Dimension 

摘      要：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.