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$.