Random sorting networks

DOI10.1016/j.aim.2007.05.019zbMath1132.60008arXivmath/0609538OpenAlexW2107382982MaRDI QIDQ2383011

Dan Romik, Alexander E. Holroyd, Omer Angel, Bálint Virág

Publication date: 5 October 2007

Published in: Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

symmetric groupsCayley graphYoung tableauxpermutahedronsorting networks

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorial aspects of representation theory (05E10) Combinatorial probability (60C05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Related Items (35)

Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings ⋮ Absorbing time asymptotics in the oriented swap process ⋮ Random stable-type minimal factorizations of the n-cycle ⋮ Milnor invariants of sorting networks ⋮ Periodic P\'olya urns and an application to Young tableaux ⋮ Perfect shuffling by lazy swaps ⋮ The Archimedean limit of random sorting networks ⋮ The runsort permuton ⋮ The oriented swap process and last passage percolation ⋮ Bijecting hidden symmetries for skew staircase shapes ⋮ The maximum multiplicity of a generator in a reduced word ⋮ Large deviations for the interchange process on the interval and incompressible flows ⋮ Shift-invariance of the colored TASEP and finishing times of the oriented swap process ⋮ Ungarian Markov chains ⋮ Sorting networks, staircase Young tableaux, and last passage percolation ⋮ Second class particles and limit shapes of evacuation and sliding paths for random tableaux. ⋮ Relating Edelman-Greene insertion to the Little map ⋮ On collisions times of `self-sorting' interacting particles in one-dimension with random initial positions and velocities ⋮ Random sorting networks: local statistics via random matrix laws ⋮ A combinatorial version of Sylvester's four-point problem ⋮ Diffuse scattering on graphs ⋮ On random shifted standard Young tableaux and 132-avoiding sorting networks ⋮ On random shifted standard Young tableaux and 132-avoiding sorting networks ⋮ Geodesics and almost geodesic cycles in random regular graphs ⋮ Circular support in random sorting networks ⋮ Properties of the Edelman-Greene bijection ⋮ A symplectic refinement of shifted Hecke insertion ⋮ Representing Permutations with Few Moves ⋮ Trajectories in random minimal transposition factorizations ⋮ The oriented swap process ⋮ The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees ⋮ Periodic Pólya urns, the density method and asymptotics of Young tableaux ⋮ Jeu de taquin dynamics on infinite Young tableaux and second class particles ⋮ A generalization of balanced tableaux and marriage problems with unique solutions ⋮ Random generation and scaling limits of fixed genus factorizations into transpositions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Note on the expected number of Yang-Baxter moves applicable to reduced decompositions.
• On the number of reduced decompositions of elements of Coxeter groups
• A probabilistic proof of a formula for the number of Young tableaux of a given shape
• Representations of symmetric groups and free probability
• Transition probabilities for continual Young diagrams and the Markov moment problem
• The skeleton of a reduced word and a correspondence of Edelman and Green
• Balanced tableaux
• Combinatorial aspects of the Lascoux-Schützenberger tree
• Limit shapes for random square Young tableaux
• Fabian Stedman: The First Group Theorist?
• The Hook Graphs of the Symmetric Group

This page was built for publication: Random sorting networks