Originators: Bartłomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, Grzegorz Matecki, Piotr Micek (presented by Kevin Milans - REGS 2010)
Definitions: Given a set P of real numbers (viewed as points on a line), let the width be the maximum size of a subset contained in a closed interval of length 1. A coloring of P is proper if x and y have distinct colors whenever they differ by at most 1.
Two players, Spoiler and Algorithm, play a game. Spoiler presents a point x on the real line. Algorithm assigns a color to x so that the coloring remains proper for the set of all points that have been presented. Algorithm tries to use as few colors as possible, and Spoiler tries to force Algorithm to use many colors while keeping the width of the presented set to at most w. Let f(w) be the least number of colors that Algorithm needs to survive forever against (an optimal) Spoiler restricted to width w.
Background: One simple strategy for Algorithm is FirstFit, which uses the positive integers as colors. When given x, FirstFit colors x with the least color that keeps the coloring proper; this may require introducing a new color. Since a color is available for use on x if it does not already appear on a point within distance 1 of x (to either side), FirstFit uses at most 2w-1 colors when Spoiler is restricted to sets having width at most w. On the other hand, Bosek et al. [BFKKMM] proved that Spoiler has a strategy to force Algorithm to use at least ⌊3w/2⌋ colors, no matter what strategy Algorithm uses. Therefore, ⌊3w/2⌋ ≤ f(w) ≤ 2w-1.
Problem: Improve the bounds on f(w).
Comments: The game is equivalent to the problem of online chain partitioning for a semiorder presented with a semiorder representation. A semiorder is a poset whose elements correspond to closed unit length intervals such that x<y in the poset if and only if the interval for x is completely to the left of the interval for y. Equivalently, x<y if the centers of the intervals on the line differ by more than 1. Thus we can view a semiorder representation as a set of points on the real line such that x<y in the poset if and only if y-x>1 on the real line.
A set of points corresponds to a chain in the semiorder if and only if every two of them are more than distance 1 apart on the line. That is, the points given a common color in the game must form a chain in the semiorder. Points within an interval of length 1 are pairwise incomparable and form an antichain in the poset. The maximum size of an antichain in a poset is its width. Thus the on-line coloring problem for point-sets having width at most w is precisely the same as the on-line chain partitioning problem for semiorders having width at most w.
References:
[1] B. Bosek, S. Felsner, K. Kloch, T. Krawczyk, G. Matecki and P. Micek,
On-line chain partitions of orders: A survey, submitted. pdf