Random subnetworks of random sorting networks

MaRDI QIDQ976676zbMATH OpenFDO

Authors Omer Angel, A. E. Holroyd

Publication date 16 June 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.2519, https://eudml.org/doc/231498, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1n23.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

great circle conjecturePolya urnrandom sorting networkreduced word

Mathematics Subject Classification ID

Combinatorial probability (60C05) Searching and sorting (68P10)

Abstract: A sorting network is a shortest path from 12...n to n...21 in the Cayley graph of S_n generated by nearest-neighbor swaps. For m<=n, consider the random m-particle sorting network obtained by choosing an n-particle sorting network uniformly at random and then observing only the relative order of m particles chosen uniformly at random. We prove that the expected number of swaps in location j in the subnetwork does not depend on n, and we provide a formula for it. Our proof is probabilistic, and involves a Polya urn with non-integer numbers of balls. From the case m=4 we obtain a proof of a conjecture of Warrington. Our result is consistent with a conjectural limiting law of the subnetwork as n->infinity implied by the great circle conjecture Angel, Holroyd, Romik and Virag.

Recommendations

• Circular support in random sorting networks
• Random sorting networks
• A pattern theorem for random sorting networks
• The Archimedean limit of random sorting networks
• The local limit of random sorting networks
• Random permutation graphs and related Markov chains
• Emergence of a giant component in a random permutation with given number of cycles
• Random sorting networks: local statistics via random matrix laws
• A rearrangement inequality for the longest run, with an application to network reliability

Cited in

(12)

• The local limit of random sorting networks
• Absorbing time asymptotics in the oriented swap process
• Milnor invariants of sorting networks
• Sorting networks, staircase Young tableaux, and last passage percolation
• Random sorting networks: local statistics via random matrix laws
• Geometry of permutation limits
• Random sorting networks
• A pattern theorem for random sorting networks
• Relating Edelman-Greene insertion to the Little map
• The Archimedean limit of random sorting networks
• Circular support in random sorting networks
• A combinatorial version of Sylvester's four-point problem

This page was built for publication: Random subnetworks of random sorting networks

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