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, ${\delta }_{xy}=\min \{p(x\prec y),p(y\prec x)\}$, and $\delta (P)=\max {\delta }_{xy}$, we show that $\delta (P)$ tends to $1/2$ as $n:=|P|\to \infty$ if $P$ has width $\Omega (n)$ or $\omega (\log (n))$ minimal elements, and is at least $1/e-o(1)$ if $P$ has width $\omega (\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.

arXiv comment24 pages