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.
| Identifer | oai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:scripps_theses-1054 |
| Date | 09 March 2012 |
| Creators | Rosenbaum, Leah F. |
| Publisher | Scholarship @ Claremont |
| Source Sets | Claremont Colleges |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Scripps Senior Theses |
| Rights | © 2012 Leah F. Rosenbaum |
Page generated in 0.0019 seconds