Random subnetworks of random sorting networks

zbMATH Open1197.60003arXiv0911.2519MaRDI QIDQ976676FDOQ976676

A. E. Holroyd, Omer Angel

Publication date: 16 June 2010

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

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.

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

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

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

zbMATH Keywords

reduced wordPolya urngreat circle conjecturerandom sorting network

Mathematics Subject Classification ID

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

Cited In (10)

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

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)