On the $1/3-2/3$ Conjecture

Abstract

Let $(P,\le )$ be a finite poset (partially ordered set), where $P$ has cardinality $n$. Consider linear extensions of $P$ as permutations $x_1{x}_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\le \alpha \le \frac{1}{2}$, we say $(x,y)$ is an $\alpha$-balanced pair if $\alpha \le \mathbb{P}(x\prec y)\le 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 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; partial orders that arise from a Young diagram; and some partial orders of dimension $2$. We also consider various posets which satisfy the stronger condition of having a $1/2$-balanced pair. For example, this happens when the poset has an automorphism with a cycle of length $2$. Various questions for future research are posed.

V2 is revised to reflect referee's comments, notation change in Prop 3.4, other typos corrected