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

character ratioscycle decompositiongiant componentinterchange processrandom transpositionsrepresentation theoryslowdown transition

Mathematics Subject Classification ID

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

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)

• Critical parameter of random loop model on trees
• 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
• Phase transition for the interchange and quantum Heisenberg models on the Hamming graph
• Sharp phase transition for random loop models on trees
• The mean-field quantum Heisenberg ferromagnet via representation theory
• Shuffling cards by spatial motion
• Quantum spins and random loops on the complete graph
• The interchange process on high-dimensional products
• Loop correlations in random wire models
• Existence of a phase transition of the interchange process on the Hamming graph
• The free energy in a class of quantum spin systems and interchange processes
• The probability of long cycles in interchange processes
• Random loop representations for quantum spin systems
• Heisenberg models and Schur-Weyl duality
• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles
• Many-body quantum systems. Abstracts from the workshop held September 10--15, 2023
• Directed spatial permutations on asymmetric tori
• Loop percolation versus link percolation in the random loop model

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)