Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:Random Subnetworks of Random Sorting Networks. | Random Subnetworks of Random Sorting Networks Omer Angel Department of Mathematics University of British Columbia 121-1984 Mathematics Road Vancouver BC V6T 1Z2 Canada. angel at math dot ubc dot ca Alexander E. Holroyd Department of Mathematics University of British Columbia 121-1984 Mathematics Road Vancouver BC V6T 1Z2 Canada. and Microsoft Research 1 Microsoft Way Redmond WA 98052 USA. holroyd at math dot ubc dot ca Submitted Nov 19 2009 Accepted Apr 4 2010 Published Apr 19 2010 Mathematics Subject Classification 60C05 05E10 68P10 Abstract A sorting network is a shortest path from 12 n to n 21 in the Cayley graph of Sn 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 TO implied by the great circle conjecture of Angel Holroyd Romik and Virag. 1 Introduction Let Sn be the symmetric group of all permutations Ơ a 1 . a n on 1 . n with composition given by ar i ơ t i . For 1 s n 1 denote the adjacent transposition or swap at location s by Ts s s 1 1 2 . s 1 s . n G Sn. Key words sorting network random sorting reduced word Polya urn Funded in part by Microsoft Research and NSERC. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N23 1 5 4 3 2 1 Figure 1 An illustration of the 5-particle sorting network w 2 1 3 4 2 3 4 2 1 2 together with the 3-particle subnetwork w A 2 1 2 induced by the subset of particles A 1 2 4 . Denote the identity id 1 2 . n and the reverse permutation p n . 2 1 . An n-particle sorting network .
