Balancing Extensions in Posets of Large Width

Abstract

We revisit classic balancing problems for linear extensions of a partially ordered set $P$, proving results that go far beyond many of the best earlier results on this topic. For example, with $p(x\prec y)$ the probability that $x$ precedes $y$ in a uniform linear extension, $\hat{I}{´}_{xy}=\min \{p(x\prec y),p(y\prec x)\}$, and $\hat{I}´(P)=\max \hat{I}{´}_{xy}$, we show that $\hat{I}´(P)$ tends to $1/2$ as $n:=|P|\to \infty$ if $P$ has width $\hat{I}\text{c◯}(n)$ or $\ddot{I}‰(\log (n))$ minimal elements, and is at least $1/e-o(1)$ if $P$ has width $\ddot{I}‰(\sqrt{n})$ or height $o(n)$. Motivated by both consequences for balance problems and intrinsic interest, we also consider several old and new parameters associated with $P$. Here, in addition to balance, we study relations between the parameters and suggest various questions that are thought to be worthy of further investigation.

24 pages