A Family of Partially Ordered Sets with Small Balance Constant

Abstract

Given a finite poset $\mathcal{P}$ and two distinct elements $x$ and $y$, we let ${\mathrm{pr}}_{\mathcal{P}}(x\prec y)$ denote the fraction of linear extensions of $\mathcal{P}$ in which $x$ precedes $y$. The balance constant $\delta (\mathcal{P})$ of $\mathcal{P}$ is then defined by \[ δ(\mathcal P) = \max_{x \neq y \in \mathcal P} \min \left\{ \operatorname{pr}_{\mathcal P}(x \prec y), \operatorname{pr}_{\mathcal P}(y \prec x) \right\}. \] The $1/3$-$2/3$ conjecture asserts that $\delta (\mathcal{P})\ge \frac{1}{3}$ whenever $\mathcal{P}$ is not a chain, but except from certain trivial examples it is not known when equality occurs, or even if balance constants can approach $1/3$. In this paper we make some progress on the conjecture by exhibiting a sequence of posets with balance constants approaching $\frac{1}{32}(93-\sqrt{6697})\approx 0.3488999$, answering a question of Brightwell. These provide smaller balance constants than any other known nontrivial family.

11 pages, 4 figures. Latest version fixed a small typo reported by A Gudibanda in July 2017, and is otherwise unchanged

Cited by in corpus (3)

• Extensions of the Kahn--Saks inequality for posets of width two
• The cross-product conjecture for width two posets
• Sorting probability for large Young diagrams