Sorting probability for large Young diagrams

DOI10.19086/DA.30071MaRDI QIDQ5028494zbMATH OpenOpenAlexFDO

Authors Swee Hong Chan, Igor Pak, Greta Panova

Publication date 10 February 2022

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2005.08390

zbMATH Keywords

\(1/3-2/3\) conjecturehook-length formulalinear extensionSchur functionsorting probabilitystandard Young tableau

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Combinatorial aspects of representation theory (05E10) Combinatorics of partially ordered sets (06A07) Combinatorial probability (60C05)

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 [delta(P) , := , min_{x,yin X} , �igl| mathbf{P} , [L(x)leq L(y) ] - mathbf{P} , [L(y)leq L(x) ] �igr|,, ] where $Linmathcal{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.

Recommendations

• Balancing poset extensions
• A non-messing-up phenomenon for posets
• Linear extensions of infinite posets
• Balancing pairs and the cross product conjecture
• scientific article; zbMATH DE number 6806844

Cites work

• A family of partially ordered sets with small balance constant
• A note on merging
• A strange pigeon-hole principle
• A variational principle for domino tilings
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Asymptotic theory of characters of the symmetric group
• Asymptotics of the number of standard Young tableaux of skew shape
• Balance theorems for height-2 posets
• Balanced pairs in partial orders
• Balancing extensions via Brunn-Minkowski
• Balancing pairs and the cross product conjecture
• Balancing poset extensions
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Counting linear extensions
• Entropy and sorting.
• Enumeration formulas for Young tableaux in a diagonal strip
• Finite partially ordered sets and their corresponding permutation sets
• Hook Formulas for Skew Shapes II. Combinatorial Proofs and Enumerative Applications
• Hook formulas for skew shapes. I: \(q\)-analogues and bijections
• Hook formulas for skew shapes. III: Multivariate and product formulas
• How good is the information theory bound in sorting?
• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 446489 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• scientific article; zbMATH DE number 1117961 (Why is no real title available?)
• scientific article; zbMATH DE number 863477 (Why is no real title available?)
• scientific article; zbMATH DE number 924935 (Why is no real title available?)
• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
• Limit shapes for random square Young tableaux
• On linear extensions of ordered sets with a symmetry
• On the \(1/3-2/3\) conjecture
• On the enumeration of skew Young tableaux
• Poset limits and exchangeable random posets
• Probability Inequalities for Sums of Bounded Random Variables
• Schur functions: Theme and variations
• Semiorders and the 1/3-2/3 conjecture
• Skew shape asymptotics, a case-based introduction
• Sorting probability of Catalan posets
• The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest
• The 1/3–2/3 Conjecture for 5-Thin Posets
• The 1/3-2/3 conjecture for N-free ordered sets
• The Degree Formula for the Skew-Representations of the Symmetric Group
• The Hook Graphs of the Symmetric Group
• The Information-Theoretic Bound is Good for Merging

Cited in

(9)

• Sorting networks, staircase Young tableaux, and last passage percolation
• The expected jaggedness of order ideals
• On the Okounkov-Olshanski formula for standard tableaux of skew shapes
• The cross-product conjecture for width two posets
• Experimenting with standard Young tableaux
• Minimal skew semistandard tableaux and the Hillman-Grassl correspondence
• Sort-invariant non-messing-up
• Minimal skew semistandard Young tableaux and the Hillman-Grassl correspondence
• Combinatorics. Abstracts from the workshop held January 4--9, 2026

This page was built for publication: Sorting probability for large Young diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028494)