Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.26134 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918178740764672 |
|---|---|
| author | Aires, Max Kahn, Jeff |
| author_facet | Aires, Max Kahn, Jeff |
| contents | An old conjecture of Kahn and Saks says, roughly, that any poset $P$ of large enough width contains elements $x,y$ which are "balanced" in the sense that the probability that $x$ precedes $y$ in a uniformly random linear extension of $P$ is close to $1/2$. We show this implies the seemingly stronger statement that the same conclusion holds if, instead of large width, we assume only that, for some $x$, the number, $π(x)$, of elements of $P$ incomparable to $x$ is large. The implication follows from our two main results: first, that if $π(P):=\max π(x)$ is large then $P$ has large variance, i.e. there is a $y$ whose position in a uniform extension of $P$ has large variance; and second, that the conclusion of the Kahn-Saks Conjecture holds for $P$ with large variance and bounded width. These two assertions also yield an easy proof of a (not easy) result of Chan, Pak and Panova on "sorting probabilities" for Young diagrams, together with its natural generalization to higher dimensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26134 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Variance vs. range for linear extensions, and balancing extensions in posets of bounded width Aires, Max Kahn, Jeff Combinatorics 06A07, 60C05, 05A20 An old conjecture of Kahn and Saks says, roughly, that any poset $P$ of large enough width contains elements $x,y$ which are "balanced" in the sense that the probability that $x$ precedes $y$ in a uniformly random linear extension of $P$ is close to $1/2$. We show this implies the seemingly stronger statement that the same conclusion holds if, instead of large width, we assume only that, for some $x$, the number, $π(x)$, of elements of $P$ incomparable to $x$ is large. The implication follows from our two main results: first, that if $π(P):=\max π(x)$ is large then $P$ has large variance, i.e. there is a $y$ whose position in a uniform extension of $P$ has large variance; and second, that the conclusion of the Kahn-Saks Conjecture holds for $P$ with large variance and bounded width. These two assertions also yield an easy proof of a (not easy) result of Chan, Pak and Panova on "sorting probabilities" for Young diagrams, together with its natural generalization to higher dimensions. |
| title | Variance vs. range for linear extensions, and balancing extensions in posets of bounded width |
| topic | Combinatorics 06A07, 60C05, 05A20 |
| url | https://arxiv.org/abs/2510.26134 |