Cycle structure of the interchange process and representation theory

MaRDI QIDQ5255627zbMATH OpenFDO

Authors Nathanaël Berestycki, Gady Kozma

Publication date 16 June 2015

Full work available at URL https://arxiv.org/abs/1205.4753

zbMATH Keywords

representation theorygiant componentcycle decompositioninterchange processrandom transpositionscharacter ratiosslowdown transition

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial aspects of representation theory (05E10) Random walks on graphs (05C81) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15)

Abstract: Consider the process of random transpositions on the complete graph. 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.

Recommendations

• The probability of long cycles in interchange processes
• The random k cycle walk on the symmetric group
• Cycle structure of the elements of centralizers of permutations from the symmetric group
• Limiting processes with dependent increments for measures on symmetric group of permutations
• The cycle structure of random permutations without macroscopic cycles
• Likelihood orders for the \(p\)-cycle walks on the symmetric group
• Permutations without long or short cycles
• Rapidly mixing random walks and bounds on characters of the symmetric group
• Comparing with octopi
• Asymptotic estimates for the number of permutations without short cycles

Cited in

(20)

• Strongly correlated random interacting processes. Abstracts from the workshop held January 28 -- February 3, 2018
• Comparing with octopi
• The random transposition dynamics on random regular graphs and the Gaussian free field
• Random loop representations for quantum spin systems
• Loop percolation versus link percolation in the random loop model
• Existence of a phase transition of the interchange process on the Hamming graph
• Phase transition for the interchange and quantum Heisenberg models on the Hamming graph
• Critical parameter of random loop model on trees
• Shuffling cards by spatial motion
• Directed spatial permutations on asymmetric tori
• Loop correlations in random wire models
• The probability of long cycles in interchange processes
• The free energy in a class of quantum spin systems and interchange processes
• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
• Sharp phase transition for random loop models on trees
• The mean-field quantum Heisenberg ferromagnet via representation theory
• Quantum spins and random loops on the complete graph
• Heisenberg models and Schur-Weyl duality
• The interchange process on high-dimensional products
• Many-body quantum systems. Abstracts from the workshop held September 10--15, 2023

This page was built for publication: Cycle structure of the interchange process and representation theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5255627)