Random Sorting Networks

@misc{citeulike:854315, abstract = {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.}, author = {Angel, Omer and Holroyd, Alexander E. and Romik, Dan and Virag, Balint }, citeulike-article-id = {854315}, eprint = {math.PR/0609538}, keywords = {assignment, asymptotic, permutahedron, probability, sorting, symmetric-group, young-tableau}, month = {Sep}, posted-at = {2006-09-22 11:02:20}, priority = {2}, title = {Random Sorting Networks}, url = {http://arxiv.org/abs/math.PR/0609538}, year = {2006} }

TY - ELEC ID - citeulike:854315 L3 - citeulike-article-id:854315 TI - Random Sorting Networks N2 - 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. KW - assignment KW - asymptotic KW - permutahedron KW - probability KW - sorting KW - symmetric-group KW - young-tableau AU - Angel, Omer AU - Holroyd, Alexander AU - Romik, Dan AU - Virag, Balint PY - 2006/Sep/19/ UR - http://arxiv.org/abs/math.PR/0609538 ER -