Graduation Year

Spring 2012

Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Arts

Department

Mathematics

Reader 1

Shahriar Shahriari

Reader 2

Anie Chaderjian

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Rights Information

© 2012 Leah F. Rosenbaum

Abstract

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.

Download

Share

COinS