Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.11549 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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, $δ_{xy} = \min\{p(x \prec y), p(y \prec x)\}$, and $δ(P)=\max δ_{xy}$, we show that $δ(P)$ tends to $1/2$ as $n := |P| \to\infty$ if $P$ has width $Ω(n)$ or $ω(\log(n))$ minimal elements, and is at least $1/e-o(1)$ if $P$ has width $ω(\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.