A Dichotomy Theorem for First-Fit Chain Partitions

2018/10/09 by Milans, Kevin G., Wigal, Michael C.
#06A07 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1810.03807

Abstract

First-Fit is a greedy algorithm for partitioning the elements of a poset into chains. Let \textrmFF(w,Q) be the maximum number of chains that First-Fit uses on a Q-free poset of width w. A result due to Bosek, Krawczyk, and Matecki states that \textrmFF(w,Q) is finite when Q has width at most 2. We describe a family of posets Q and show that the following dichotomy holds: if Q\inQ, then \textrmFF(w,Q) ≤ 2^{c(log w)2} for some constant c depending only on Q, and if Q\not\inQ, then \textrmFF(w,Q) ≥ 2^w - 1.

Related

• Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
• An easy subexponential bound for online chain partitioning
• On-line partitioning of width w posets into w^O(log log w) chains
• Polyunsaturated Posets and Graphs and the Greene-Kleitman Theorem
• Poset saturation of unions of chains