Random Subnetworks of Random Sorting Networks

Details Random Subnetworks of Random Sorting Networks Random Subnetworks of Random Sorting Networks

2009-11-13

arxiv.org/abs/0911.2519v2

Mathematics

Probability

9 pages; minor changes to open problems

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Random Subnetworks of Random Sorting Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random Subnetworks of Random Sorting Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Subnetworks of Random Sorting Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-113157