Cycle structure of the interchange process and representation theory

[Structure des cycles dans le processus de transpositions et théorie des représentations]

Berestycki, Nathanaël ; Kozma, Gady

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

Abstract (VO)

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.

Résumé

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.

Détail

Publié le : 2015-09-04
DOI : 10.24033/bsmf.2686

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