A subexponential upper bound for the on-line chain partitioning problem (Q276436)

The online chain partitioning problem is a game between two players: Spoiler and Algorithm. In each round Spoiler introduces a new point to the poset and gives its relation to all existing points. Algorithm's task is to maintain a chain partition of the growing poset by incorporating the new point into one of the already existing chains or creating a new chain for the new point. Spoiler tries to build a poset to force Algorithm to use as many chains as possible, while Algorithm's task is to keep the number of chains as small as possible. Let \(\text{val}(w)\) denote the smallest number \(n\) for which Algorithm has a strategy that can partition any poset of width \(w\) into at most \(n\) chains. By Dilworth's theorem \(\text{val}(w)\) would be \(w\) if the game were played off-line. For the on-line game the best upper bound so far is \(\text{val}(w) \leq (5^w-1)/4\) by \textit{H. A. Kierstead} [Trans. Am. Math. Soc. 268, 63--77 (1981; Zbl 0485.03019)], the highest lower bound is \(\text{val}(w) \geq (2-o(1))\binom{w+1}{2}\) from the survey paper by \textit{B. Bosek} et al. [Order 29, No. 1, 49--73 (2012; Zbl 1259.06002)] which slightly improves E. Szemerédi's earlier lower bound of \(\binom{w+1}{2}\). The main result of the paper is that \(\text{val}(w) \leq w^{13 \log w}\). The proof is by first reducing the chain partition problem to a so-called regular game, where Spoiler introduces certain antichains rather than points. In Lemma~3.1 it is proved that if Algorithm has a strategy for using at most \(\text{reg}(w)\) colors for the on-line regular game of width \(w\), then \[ \text{val}(w) \leq \text{reg}(1)+ \dots + \text{reg}(w). \] Second, the authors give a recursive algorithm for the on-line regular game and prove the recursion \[ \text{reg}(w) \leq 32\left(1+\binom{w^3+1}{2} \right)(2w-1)w^5 \text{val}(w/2) \] in Lemma~3.2. Putting the two lemmas together yields the desired upper bound for \(\text{val}(w)\).