Open Access Senior Thesis
Bachelor of Arts
© 2012 Leah F. Rosenbaum
One question relating to partially ordered sets (posets) is that of partitioning or dividing the poset's elements into the fewest number of chains that span the poset. In 1950, Dilworth established that the width of the poset - the size of the largest set composed only of incomparable elements - is the minimum number of chains needed to partition that poset. Such a bound in on-line partitioning has been harder to establish, and work has evalutated classes of posets based on their width. This paper reviews the theorems that established val(2)=5 and illustrates them with examples. It also covers some of the work on establishing bounds for on-line partitioning with the Greedy Algorithm. The paper concludes by contributing a bound on incomparable elements in graded, (t+t)-free, finite width posets.
Rosenbaum, Leah F., "Exploring the On-line Partitioning of Posets Problem" (2012). Scripps Senior Theses. 53.