Abstract
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 ≥ 1, there exists a constant c k so that First Fit will use at most \(c_kw^2\) 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: (5w − 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 − 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bosek, B., Krawczyk, T.: The sub-exponential upper bound for on-line chain partitioning. In: IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 347–354 (2010). doi:10.1109/FOCS.2010.40
Bosek, B., Krawczyk, T., Szczypka, E.: First-fit algorithm for on-line chain partition problem. SIAM J. Discrete Math. 23(4), 1992–1999 (2010)
Bosek, B., Felsner, S., Kloch, K., Krawczyk, T., Matecki, G., Micek, P.: On-line chain partitions of orders: a survey. Order (2011). doi:10.1007/s11083-011-9197-1
Chrobak, M., Ślusarek, M.: On some packing problems related to dynamic storage allocation. RAIRO Inf. Théor. Appl. 22, 487–499 (1988)
Fishburn, P.C.: Intransitive indifference with unequal indifference intervals. J. Math. Psychol. 7, 144–149 (1970)
Hopkins, L.: Some Problems Involving Combinatorial Structures Determined by Intersections of Intervals and Arcs. Ph.D. thesis, University of South Carolina (1981)
Joret, G., Milans, K.: First-fit is linear on (r + s)-free posets. Order (2011, in press)
Kierstead, H.: An effective version of Dilworth’s theorem. Trans. Am. Math. Soc. 268, 63–77 (1981)
Kierstead, H.: The linearity of first-fit coloring of interval graphs. SIAM J. Discrete Math. 4, 526–530 (1988)
Kierstead, H., Qin, J.: Coloring interval graphs with first-fit. Discrete Math. 144, 47–57 (1995)
Kierstead, H., Trotter, W.T.: An extremal problem in recursive combinatorics. Congressus Numerantium 33, 143–153 (1981)
Kierstead, H., McNulty, G., Trotter, W.T.: A theory of recursive dimension for ordered sets. Order 1, 67–82 (1984)
Narayanaswamy, N., Babu, R.: A note on first-fit coloring of interval graphs. Order 25, 49–53 (2008)
Pemmaraju, S., Raman, R., Varadarajan, K.: Buffer minimization using max-coloring. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 562–571 (2004)
Ślusarek, M.: A lower bound for the first fit coloring of interval graphs. Zeszyty Naukowe Uniwersytetu Jagiellońskiego, Prace Informatyczne z. 5, 25–32 (1993)
Trotter, W.T.: Dimension of the crown \(S^k_n\). Discrete Math. 8, 85–103 (1974)
Trotter, W.T.: Combinatorics and Partially Ordered Sets: Dimension Theory. The Johns Hopkins University Press, Baltimore (1992)
Trotter, W.T.: Partially ordered sets. In: Graham, R.L., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics. Elsevier, Amsterdam, 433–480 (1995)
Woodall, D.R.: Problem no. 4. In: Proceedings of the British Combinatorial Conference 1973, London Math. Soc., Lecture Note Series 13. Cambridge University Press (1974)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Felsner, S., Krawczyk, T. & Trotter, W.T. On-Line Dimension for Posets Excluding Two Long Incomparable Chains. Order 30, 1–12 (2013). https://doi.org/10.1007/s11083-011-9222-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-011-9222-4