Back to search

Michigan State University

Progress on the 1/3 - 2/3 conjecture

Abstract

dc:description

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.

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 × 2

Rights

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

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Olson, Emily Jean. Progress on the 1/3 - 2/3 conjecture. 2017. https://doi.org/doi:10.25335/g4a8-fn94