On-Line Chain Partitions of Orders
Stefan Felsner
Institut für Informatik
Freie Universität Berlin
email: felsner@inf.fu-berlin.de
Report B 94-21
Dezember 1994
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-21.ps.gz
On-Line Chain Partitions of Orders
We analyze the on-line chain partitioning problem as a two-person
game. One person builds an order one point at a time. The other person
responds by making an irrevocable assignment of the new point to a
chain of a chain partition. Kierstead gave a strategy showing that
width $k$ orders can be on-line chain partitioned into $(5^k -1)/4$
chains. We first prove that width two orders can be partitioned
on-line into 5 chains. Secondly, we introduce a variant of the game.
We impose the restriction that the new point presented by the first
player has to be a maximum element in the present order. For this
up-growing variant we prove matching upper and lower bounds of
$k+1\choose 2$ on orders of width $k$.