Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


The main question in the on-line chain partitioning problem is to determine whether there exists an algorithm that partitions on-line posets of width at most $w$ into polynomial number of chains -- see Trotter's chapter emph{Partially ordered sets} in the emph{Handbook of Combinatorics}. So far the best known on-line algorithm of Kierstead used at most $(5^w-1)/4$ chains; on the other hand Szemer'{e}di proved that any on-line algorithm requires at least $inom{w+1}{2}$ chains. These results were obtained in the early eighties and since then no progress in the general case has been done.

We provide an on-line algorithm that partitions orders of width $w$ into at most $w^{16log{w}}$ chains. This yields the first sub-exponential upper bound for on-line chain partitioning problem.

Questions and Answers

You need to be logged in to be able to post here.