On-line Chain Partitioning of Up-growing Interval Orders

On-line chain partitioning problem of on-line posets has been open for the past 20 years. The best known on-line algorithm uses \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{5^w-1}{4}$\end{document} chains to cover poset of width w. Felsner (Theor. Comput. Sci., 175(2):283–292, 1997) introduced a variant of this problem considering only up-growing posets, i.e. on-line posets in which each new point is maximal at the moment of its arrival. He presented an algorithm using \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\left( {\begin{array}{*{20}c} {{w + 1}} \\ {2} \\ \end{array} } \right)}$\end{document} chains for width w posets and proved that his solution is optimal. In this paper, we study on-line chain partitioning of up-growing interval orders. We prove lower bound and upper bound to be 2w−1 for width w posets.