#### Date on Master's Thesis/Doctoral Dissertation

8-2022

#### Document Type

Doctoral Dissertation

#### Degree Name

Ph. D.

#### Department

Mathematics

#### Degree Program

Applied and Industrial Mathematics, PhD

#### Committee Chair

Biro, Csaba

#### Committee Co-Chair (if applicable)

Kezdy, Andre

#### Committee Member

Kezdy, Andre

#### Committee Member

Kubicki, Grzegorz

#### Committee Member

Wildstrom, David

#### Committee Member

Frigui, Hichem

#### Author's Keywords

poset; on-line; algorithm; partition; chain; order

#### Abstract

An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemer\'edi proved that any on-line algorithm could be forced to use $\binom{w+1}{2}$ chains to partition a poset of width $w$. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In the survey paper by Bosek et al., variants of the problem were studied where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size $d$. We prove two results for this problem. First, we prove that any on-line algorithm can be forced to use $(2-o(1))\binom{w+1}{2}$ chains to partition a $2$-dimensional poset of width $w$. Second, we prove that any on-line algorithm can be forced to use $(2-\frac{1}{d-1}-o(1))\binom{w+1}{2}$ chains to partition a poset of width $w$ presented via a realizer of size $d$. Chrobak and \'Slusarek considered variants of the on-line chain partitioning problem in which the elements are presented as intervals and intersecting intervals are incomparable. They constructed an on-line algorithm which uses at most $3w-2$ chains, where $w$ is the width of the interval order, and showed that this algorithm is optimal. They also considered the problem restricted to intervals of unit-length and while they showed that first-fit needs at most $2w-1$ chains, over $30$ years later, it remains unknown whether a more optimal algorithm exists. We improve upon previously known bounds and show that any on-line algorithm can be forced to use $\lceil\frac{3}{2}w\rceil$ chains to partition a semi-order presented in the form of its unit-interval representation. As a consequence, we completely solve the problem for $w=3$. We also consider entirely new variants and present the results for those.

#### Recommended Citation

Curbelo, Israel R., "The on-line width of various classes of posets." (2022). *Electronic Theses and Dissertations.* Paper 3974.

https://doi.org/10.18297/etd/3974