On-line chain partitions of orders: a survey (Q766153)

The paper surveys the state of the art in the field of online-chain partitioning of partially ordered sets (posets) and contributes some new results. Online-chain partitioning may be described as a two-player game between Spoiler and Algorithm on a poset \(P\) as follows: Each round starts with Spoiler presenting an element \(p\) of \(P\) together with all its relations to already presented elements, i.e., the presented elements together form an induced subposet \(P'\) of \(P\). Afterwards, Algorithm has to assign \(p\) to a chain \(C_p\) of \(P'\) such that, together with the earlier assignments, \(C_p\) forms a chain-partition of \(P'\), i.e., \(\{C_q\mid q\in P'\}\) is a partition of \(P'\) into chains. The assignments made by Algorithm are irrevocable during the course of the game. It is Algorithm's goal to use as few chains as possible, while Spoiler wants to force many chains. Since the width \(w(P)\) is the minimum size of a chain-partition of \(P\) (in the offline setting) the value of the game is taken with respect to the class of width-\(w\) posets, i.e., \(\operatorname{val}(w)\) is the minimum size of a chain-partition that Algorithm can guarantee on this class. The paper describes a variety of classical and recent results and variations of the problem. The most important parts are: A sketch of the proof by Bosek and Krawczyk for the new sub-exponential bound \(\operatorname{val}(w)\leq w^{16\text{lg}w}\); a new lower bound \(\operatorname{val}(w)\geq (2-o(1)) {w+1\choose 2}\); the inclusion of some simplified proofs of previously published results; a comprehensive account on variants of the problem for interval orders; and a new lower bound for 2-dimensional up-growing orders.