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
