Improved lower bounds on the on-line chain partitioning of posets of bounded dimension

DOI10.1007/S11083-023-09629-7MaRDI QIDQ6139864zbMATH OpenOpenAlexFDO

Authors Csaba Biró, Israel R. Curbelo

Publication date 19 December 2023

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.04802

zbMATH Keywords

chain partitioningon-line algorithmposet dimension

Mathematics Subject Classification ID

Order, lattices, ordered algebraic structures (06-XX)

Abstract: 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'edi proved that any on-line algorithm could be forced to use $$ 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'edi'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 $$ chains to partition a $2$-dimensional poset of width $w$. Second, we prove that any on-line algorithm can be forced to use $$ chains to partition a poset of width $w$ presented via a realizer of size $d$.

Cites work

• scientific article; zbMATH DE number 3993569 (Why is no real title available?)
• A theory of recursive dimension of ordered sets
• An Effective Version of Dilworth's Theorem
• On-line chain partitions of orders
• On-line chain partitions of orders: a survey
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains

Cited in

(5)

• scientific article; zbMATH DE number 5762570 (Why is no real title available?)
• Improved lower bound on the on-line chain partitioning of semi-orders with representation
• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• On-line chain partitioning of up-growing interval orders
• First-Fit Algorithm for the On-Line Chain Partitioning Problem

This page was built for publication: Improved lower bounds on the on-line chain partitioning of posets of bounded dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139864)