Comparing with octopi (Q2028952): Difference between revisions

Given a graph \(G\) on \(n\) vertices, the interchange process on \(G\) is a random walk on \(S_n\) which chooses a random edge \((i,j)\) of \(G\) at each step and applies the transposition \((i,j)\) to the permutation in \(S_n\). The walk can either be discrete (with a probability of \(1/2\) of staying in place to avoid single steps always switching parity) or continuous (take steps according to a Poisson process). These graphs are of interest in interacting particle systems and quantum mechanics. The authors use the octopus inequality [\textit{P. Caputo} et al., J. Am. Math. Soc. 23, No. 3, 831--851 (2010; Zbl 1203.60145)] to prove bounds on the mixing behavior for general graphs \(G\), including a comparison to the mixing time for the complete graph \(K_n\). They also use representation theory of the symmetric group to bound the probability that the random walk reaches a large cycle in \(S_n\), and a related result for the quantum Heisenberg ferromagnet.