Random Sorting Networks

Details Random Sorting Networks Random Sorting Networks

2006-09-19

arxiv.org/abs/math/0609538v1

Adv. Math. 215 (2007), no. 2, 839-868

Mathematics

Probability

38 pages, 12 figures

Scientific paper

10.1016/j.aim.2007.05.019

A sorting network is a shortest path from 12...n to n...21 in the Cayley graph of S_n generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as n->infinity the space-time process of swaps converges to the product of semicircle law and Lebesgue measure. We conjecture that the trajectories of individual particles converge to random sine curves, while the permutation matrix at half-time converges to the projected surface measure of the 2-sphere. We prove that, in the limit, the trajectories are Holder-1/2 continuous, while the support of the permutation matrix lies within a certain octagon. A key tool is a connection with random Young tableaux.

Affiliated with

Also associated with

No associations

Rating

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 Sorting Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Sorting Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-351388