Cycle structure of the interchange process and representation theory

Berestycki, Nathanaël; Kozma, Gady

Bulletin de la Société Mathématique de France, Tome 143 (2015) no. 2, pp. 265-281

Consider the process of random transpositions on the complete graph Kn. We use representation theory to give an exact, simple formula for the expected number of cycles of size k at time t, in terms of an incomplete Beta function. Using this we show that the expected number of cycles of size k jumps from 0 to its equilibrium value, 1/k, at the time where the giant component of the associated random graph first exceeds k. Consequently we deduce a new and simple proof of Schramm's theorem on random transpositions, that giant cycles emerge at the same time as the giant component in the random graph. We also calculate the “window” for this transition and find that it is quite thin. Finally, we give a new proof of a result by the first author and Durrett that the random transposition process exhibits a certain slowdown transition. The proof makes use of a recent formula for the character decomposition of the number of cycles of a given size in a permutation, and the Frobenius formula for the character ratios.

Nous considérons le processus de transpositions aléatoires sur le graphe complet Kn. Nous utilisons la théorie des représentations pour donner une formule exacte et simple pour l'espérance du nombre de cycles de taille k à un temps t, en termes d'une fonction Beta incomplète. À l'aide de cette formule nous montrons que cette quantité saute de 0 à sa valeur d'équilibre au précisément au moment où la composante géante du graphe aléatoire associé devient plus grande que k. Nous en déduisons une nouvelle preuve du résultat de Schramm sur les transpositions aléatoires, qui montre que les cycles géants apparaîssent au même moment que la composant géante dans le graphe aléatoire. Nous calculons également la fenêtre de cette transition, qui est particulièrement étroite. Finalement nous obtenons une preuve nouvelle d'un résultat du premier auteur et de Durrett sur la décélération du processus de transpositions. La preuve repose sur une formule récemment établie donnant la décomposition en caractères du nombre de cycles d'une taille donnée dans une permutation, ainsi que la formule de Frobenius pour les rapports de caractères.

Classification : 60B15, 60K35, 05E10
Keywords: Random transpositions, interchange process, giant component, cycle decomposition, representation theory, slowdown transition, character ratios
Mots-clés : Processus de transposition, composante géante, décomposition en cycles, théorie des représentations, transition de décélération, caractères du groupe symétrique

Alon, Gil; Kozma, Gady The probability of long cycles in interchange processes, Duke Math. J., Volume 162 (2013), pp. 1567-1585 (ISSN: 0012-7094) | MR | Zbl | DOI

Berestycki, Nathanaël Emergence of giant cycles and slowdown transition in random transpositions and k-cycles, Electron. J. Probab., Volume 16 (2011), pp. no. 5, p. 152-173 (ISSN: 1083-6489) | MR | Zbl | DOI

Berestycki, Nathanaël; Durrett, Rick A phase transition in the random transposition random walk, Probab. Theory Related Fields, Volume 136 (2006), pp. 203-233 (ISSN: 0178-8051) | MR | Zbl | DOI

Berestycki, Nathanaël; Schramm, Oded; Zeitouni, Ofer Mixing times for random k-cycles and coalescence-fragmentation chains, Ann. Probab., Volume 39 (2011), pp. 1815-1843 (ISSN: 0091-1798) | MR | Zbl | DOI

Bollobás, Béla Random graphs, Cambridge Studies in Advanced Math., 73, Cambridge Univ. Press, Cambridge, 2001, 498 pages (ISBN: 0-521-80920-7; 0-521-79722-5) | MR | Zbl | DOI

Buffet, E.; Pulé, J. V. Polymers and random graphs, J. Statist. Phys., Volume 64 (1991), pp. 87-110 (ISSN: 0022-4715) | MR | Zbl | DOI

Caputo, Pietro; Liggett, Thomas M.; Richthammer, Thomas Proof of Aldous' spectral gap conjecture, J. Amer. Math. Soc., Volume 23 (2010), pp. 831-851 (ISSN: 0894-0347) | MR | Zbl | DOI

Diaconis, Persi Group representations in probability and statistics, IMS Lecture Notes—Monograph Series, 11, Institute of Mathematical Statistics, 1988 | MR | Zbl | DOI

Diaconis, Persi; Shahshahani, Mehrdad Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, Volume 57 (1981), pp. 159-179 (ISSN: 0044-3719) | MR | Zbl | DOI

van Dongen, P. G. J.; Ernst, M. H. Fluctuations in coagulating systems, J. Statist. Phys., Volume 49 (1987), pp. 879-926 (ISSN: 0022-4715) | DOI | MR

Erdős, Paul; Rényi, Alfréd On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., Volume 5 (1960), pp. 17-61 | MR | Zbl

Erdős, P.; Rényi, Alfréd On the evolution of random graphs, Bull. Inst. Internat. Statist., Volume 38 (1961), pp. 343-347 | MR | Zbl

Fulton, William; Harris, Joe Representation theory, Graduate Texts in Math., 129, Springer, New York, 1991, 551 pages (ISBN: 0-387-97527-6; 0-387-97495-4) | MR | Zbl | DOI

Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times, Amer. Math. Soc., Providence, RI, 2009, 371 pages (ISBN: 978-0-8218-4739-8) | MR | Zbl

Lubetzky, Eyal; Sly, Allan Explicit expanders with cutoff phenomena, Electron. J. Probab., Volume 16 (2011), pp. 419-435 (ISSN: 1083-6489) | MR | Zbl | DOI

Sagan, Bruce E. The symmetric group, Graduate Texts in Math., 203, Springer, New York, 2001, 238 pages (ISBN: 0-387-95067-2) | MR | Zbl | DOI

Schramm, Oded Compositions of random transpositions, Israel J. Math., Volume 147 (2005), pp. 221-243 (ISSN: 0021-2172) | MR | Zbl | DOI

Tóth, Bálint Improved lower bound on the thermodynamic pressure of the spin 1/2 Heisenberg ferromagnet, Lett. Math. Phys., Volume 28 (1993), pp. 75-84 (ISSN: 0377-9017) | MR | Zbl | DOI