Comparability in Bruhat orders
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915760567222272 |
|---|---|
| author | Boretsky, Jonathan Cornejo, Alvaro Hodges, Reuven Horn, Paul Lesnevich, Nathan McAllister, Tyrrell |
| author_facet | Boretsky, Jonathan Cornejo, Alvaro Hodges, Reuven Horn, Paul Lesnevich, Nathan McAllister, Tyrrell |
| contents | We determine the sharp asymptotic scale of the probability that two uniformly random permutations are comparable in weak Bruhat order, showing that $\mathbb{P}(σ_1 \preceq_W σ_2)=\exp\Bigl(\bigl(-\tfrac12+o(1)\bigr)\,n\log n\Bigr)$. This significantly improves both of the best known bounds, due to Hammett and Pittel, which placed this probability between $\exp((-1+o(1))n\log n)$ and $\exp(-Θ(n))$. We also improve the best known lower bound for strong Bruhat-order comparability, due to the same authors, by proving a subexponential lower bound. The Bruhat orders are natural partial orders on the symmetric group, appearing in wide-reaching settings including the geometry of flag manifolds, the representation theory of $\mathfrak{S}_{n}$, and the combinatorics of the permutohedron. To analyze weak Bruhat order, we combine classic analytic, tableau-theoretic, and poset-theoretic tools, including the Plancherel measure and the RSK bijection. For strong Bruhat order we construct large families where members are comparable with high probability. Our proof that members are comparable combines the tableau criterion with an associated random-walk-type deviation process. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21158 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Comparability in Bruhat orders Boretsky, Jonathan Cornejo, Alvaro Hodges, Reuven Horn, Paul Lesnevich, Nathan McAllister, Tyrrell Combinatorics Probability 05A05, 05A16, 06A07, 60C05 (Primary) 20B99 (Secondary) We determine the sharp asymptotic scale of the probability that two uniformly random permutations are comparable in weak Bruhat order, showing that $\mathbb{P}(σ_1 \preceq_W σ_2)=\exp\Bigl(\bigl(-\tfrac12+o(1)\bigr)\,n\log n\Bigr)$. This significantly improves both of the best known bounds, due to Hammett and Pittel, which placed this probability between $\exp((-1+o(1))n\log n)$ and $\exp(-Θ(n))$. We also improve the best known lower bound for strong Bruhat-order comparability, due to the same authors, by proving a subexponential lower bound. The Bruhat orders are natural partial orders on the symmetric group, appearing in wide-reaching settings including the geometry of flag manifolds, the representation theory of $\mathfrak{S}_{n}$, and the combinatorics of the permutohedron. To analyze weak Bruhat order, we combine classic analytic, tableau-theoretic, and poset-theoretic tools, including the Plancherel measure and the RSK bijection. For strong Bruhat order we construct large families where members are comparable with high probability. Our proof that members are comparable combines the tableau criterion with an associated random-walk-type deviation process. |
| title | Comparability in Bruhat orders |
| topic | Combinatorics Probability 05A05, 05A16, 06A07, 60C05 (Primary) 20B99 (Secondary) |
| url | https://arxiv.org/abs/2601.21158 |