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 order-preserving 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 one-line 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 alpha-balanced pair if alpha <= P(x < y) <= 1-alpha. The 1/3-2/3 Conjecture states that every finite partially ordered set that is not a chain has a 1/3-balanced 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/2-balanced. 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