A Study of Discrepancy Results in Partially Ordered Sets

Dissertation Defense
Friday, March 19, 2010 - 9:00am for 3 hours
Skiles 269
David Howard – School of Math, Georgia Tech
Prasad Tetali
In 2001, Fishburn, Tanenbaum, and Trenk published a series of two papers that introduced the notions of linear and weak discrepancy of a partially ordered set or poset. Linear discrepancy for a poset is the least k such that for any ordering of the points in the poset there is a pair of incomparable points at least distance k away in the ordering. Weak discrepancy is similar to linear discrepancy except that the distance is observed over weak labelings (i.e. two points can have the same label if they are incomparable, but order is still preserved). My thesis gives a variety of results pertaining to these properties and other forms of discrepancy in posets.