Progress on the 1/3  2/3 conjecture
Let (P,<) be a finite partially ordered set, also called a poset, and let n denote the cardinality of P. Fix a natural labeling on P so that the elements of P correspond to [n] = {1,2,...,n}. A linear extension is an orderpreserving total order x_1 < x_2 < ... < x_n on the elements of P, and more compactly, we can view this as the permutation x_1x_2 ... x_n in oneline notation. For distinct elements x,y in P, we define P(x < y) to be the proportion of linear extensions of P in which x comes before y. For 0 <= alpha <= 1/2, we say (x,y) is an alphabalanced pair if alpha <= P(x < y) <= 1alpha. The 1/32/3 Conjecture states that every finite partially ordered set that is not a chain has a 1/3balanced pair. This dissertation focuses on showing the conjecture is true for certain types of partially ordered sets. We begin by discussing a special case, namely when a partial order is 1/2balanced. For example, this happens when the poset has an automorphism with a cycle of length 2. We spend the remainder of the text proving the conjecture is true for some lattices, including Boolean, set partition, and subspace lattices; partial orders that arise from a Young diagram; and some partial orders of dimension 2.
Read
 In Collections

Electronic Theses & Dissertations
 Copyright Status
 In Copyright
 Material Type

Theses
 Authors

Olson, Emily Jean
 Thesis Advisors

Sagan, Bruce
 Committee Members

Bell, Robert
Hall, Jonathan
Magyar, Peter
Shapiro, Michael
 Date
 2017
 Subjects

Partially ordered sets
Lattice theory
 Program of Study

Mathematics  Doctor of Philosophy
 Degree Level

Doctoral
 Language

English
 Pages
 v, 42 pages
 ISBN

9781369711790
1369711794
 Permalink
 https://doi.org/doi:10.25335/M55J04