Masters Thesis

Geometric extensions and the 1/3 - 2/3 conjecture

The 1/3—2/3 Conjecture is a famous open problem that deals with partially ordered sets, called posets. Understanding the linear extensions of a poset can unlock hidden structure with interesting applications and further questions. The conjecture says that in every finite poset that is not totally ordered there is a pair x and y, such that x y in 1/3 to 2/3 of all the linear extensions. Such pairs are called balanced pairs. We develop a geometric version of the conjecture, amenable to computational analysis by considering one dimensions projections of Euclidean realizations of the poset. We confirm the geometric 1/3—2/3 conjecture for certain classes of posets, for which the original 1/3—2/3 conjecture is currently out of reach. Ultimately, we derive quantitative estimates for the number of geometrically balanced pairs for the hom poset.

Relationships

In Collection:

Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.