Show simple item record

dc.contributor.authorHoward, David M.en_US
dc.date.accessioned2010-09-15T19:06:31Z
dc.date.available2010-09-15T19:06:31Z
dc.date.issued2010-05-20en_US
dc.identifier.urihttp://hdl.handle.net/1853/34794
dc.description.abstractIn 2001, Fishburn, Tanenbaum, and Trenk published a pair of 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. The first chapter of my thesis partially answers a question of Fishburn, Tanenbaum, and Trenk that was to characterize those posets with linear discrepancy two. It makes the characterization for those posets with width two and references the paper where the full characterization is given. The second chapter introduces the notion of t-discrepancy which is similar to weak discrepancy except only the weak labelings with at most t copies of any label are considered. This chapter shows that determining a poset's t-discrepancy is NP-Complete. It also gives the t-discrepancy for the disjoint sum of chains and provides a polynomial time algorithm for determining t-discrepancy of semiorders. The third chapter presents another notion of discrepancy namely total discrepancy which minimizes the average distance between incomparable elements. This chapter proves that finding this value can be done in polynomial time unlike linear discrepancy and t-discrepancy. The final chapter answers another question of Fishburn, Tanenbaum, and Trenk that asked to characterize those posets that have equal linear and weak discrepancies. Though determining the answer of whether the weak discrepancy and linear discrepancy of a poset are equal is an NP-Complete problem, the set of minimal posets that have this property are given. At the end of the thesis I discuss two other open problems not mentioned in the previous chapters that relate to linear discrepancy. The first asks if there is a link between a poset's dimension and its linear discrepancy. The second refers to approximating linear discrepancy and possible ways to do it.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectPoseten_US
dc.subjectLinear discrepancyen_US
dc.subjectWeak discrepancyen_US
dc.subject.lcshPartially ordered sets
dc.subject.lcshIrregularities of distribution (Number theory)
dc.titleA study of discrepancy results in partially ordered setsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Trotter, William T.; Committee Member: Dieci, Luca; Committee Member: Duke, Richard; Committee Member: Randall, Dana; Committee Member: Tetali, Prasaden_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record