Abstract
dc:descriptionLet (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.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Olson, Emily Jean
- Contributors dc:contributor
-
- Sagan, Bruce
- Bell, Robert
- Hall, Jonathan
- Magyar, Peter
- Shapiro, Michael
Subjects
dc:subject × 2Rights
dc:rights- Statement dc:rights
-
- In Copyright
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
etd:4604
isbn:9781369711790
isbn:1369711794
oclc:1028048610
umi:10271301
local:Olson_grad.msu_0128D_15173 - OAI record oai:identifier
- https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_4604