On Partially Ordered Sets and the 1/3–2/3 Conjecture
摘要
For this article, I assume that the reader has experience with proof writing but no other particular background. Since discrete mathematics courses vary drastically in terms of content, I include definitions that one would see in a full semester course on combinatorics or graph theory. We begin with background information on partially ordered sets. Let \((P,\leq )\) be a finite partially ordered set, where P has cardinality n. Consider linear extensions of P as permutations \(x_1x_2\cdots x_n\) in one-line notation. For distinct elements \(x,y\in P\) , we define \(\mathbb {P}(x\prec y)\) to be the proportion of linear extensions of P in which x comes before y. For \(0\leq \alpha \leq \frac {1}{2}\) , we say \((x,y)\) is an \(\alpha \) -balanced pair if \(\alpha \leq \mathbb {P}(x\prec y) \leq 1-\alpha .\) The \(1/3\) – \(2/3\) Conjecture states that every finite partially ordered set which is not a chain has a \(1/3\) -balanced pair. We include some history of the conjecture, including results commonly found in the literature. We make progress on this conjecture by showing that it holds for certain families of posets. These include lattices such as the Boolean, set partition, and subspace lattices, and partial orders that arise from Young diagrams. We also consider posets that satisfy the stronger condition of having a \(1/2\) -balanced pair. We pose various questions for future research throughout the article.