CUTOFF FOR REWIRING DYNAMICS ON PERFECT MATCHINGS

• 成果类型: Article
• 署名作者: Olesker-taylor, S. A. M.
• 署名单位: University of Bath
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1825
• 发表日期: 2023
• 页码: 641-676
• 关键词: random-walks; mixing times; graphs; models

摘要

We establish cutoff for a natural random walk (RW) on the set of per-fect matchings (PMs), based on rewiring. An n-PM is a pairing of 2n ob-jects. The k -PM RW selects k pairs uniformly at random, disassociates the corresponding 2k objects, then chooses a new pairing on these 2k objects uniformly at random. The equilibrium distribution is uniform over all n-PMs. The 2-PM RW was first introduced by Diaconis and Holmes (Proc. Natl. Acad. Sci. USA 95 (1998) 14600-14602; Electron. J. Probab. 7 (2002) no. 6), seen as a RW on phylogenetic trees. They established cutoff in this case. We establish cutoff for the k-PM RW whenever 2 < k << n. If k >> 1, then the mixing time is nk log n to leading order.Diaconis and Holmes (Electron. J. Probab. 7 (2002) no. 6) relate the 2 -PM RW to the random transpositions card shuffle. Ceccherini-Silberstein, Scarabotti and Tolli (J. Math. Sci. 141 (2007) 1182-1229; Harmonic Analysis on Finite Groups: Representation Theory, Gelfand Pairs and Markov Chains (2008) Cambridge Univ. Press) establish the same result using representation theory. We are the first to handle k > 2. We relate the PM RW to conjugacy-invariant RWs on the permutation group by introducing a cycle structure for PMs, then build on work of Berestycki, Schramm, , Sengul and Zeitouni (Israel J. Math. 147 (2005) 221-243; Ann. Probab. 39 (2011) 1815-1843; Probab. Theory Related Fields 173 (2019) 1197-1241) on such RWs.