Báo cáo toán học: "Random Subnetworks of Random Sorting Networks"

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 .