Sorting probability for large Young diagrams

Abstract

For a finite poset $P=(X,\prec )$, let ${\mathcal{L}}_P$ denote the set of linear extensions of $P$. The sorting probability $\delta (P)$ is defined as \[δ(P) \, := \, \min_{x,y\in X} \, \bigl| \mathbf{P} \, [L(x)\leq L(y) ] \ - \ \mathbf{P} \, [L(y)\leq L(x) ] \bigr|\,, \] where $L\in {\mathcal{L}}_P$ is a uniform linear extension of $P$. We give asymptotic upper bounds on sorting probabilities for posets associated with large Young diagrams and large skew Young diagrams, with bounded number of rows.

arXiv comment57 pages, 5 pages

References in corpus (8)

• A variational principle for domino tilings
• Shifted Schur Functions
• Hook formulas for skew shapes I. $q$-analogues and bijections
• Hook formulas for skew shapes II. Combinatorial proofs and enumerative applications
• Dimer model, bead model and standard Young tableaux: finite cases and limit shapes
• A Family of Partially Ordered Sets with Small Balance Constant
• Sorting probability of Catalan posets
• Balance constants for Coxeter groups