A Family of Partially Ordered Sets with Small Balance Constant

摘要

Given a finite poset $mathcal P$ and two distinct elements $x$ and $y$, we let $operatorname{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 [ delta(mathcal P) = max_{x eq y in mathcal P} min left{ operatorname{pr}_{mathcal P}(x prec y), operatorname{pr}_{mathcal P}(y prec x) ight}. ] The $1/3$-$2/3$ conjecture asserts that $delta(mathcal P) ge rac13$ 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$.