CUTOFF FOR RANDOM WALK ON RANDOM GRAPHS WITH A COMMUNITY STRUCTURE

• 成果类型: Article
• 署名作者: Hermon, Jonathan; Sarkovic, Andela; Sousi, Perla
• 署名单位: University of British Columbia; University of Cambridge
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/25-AAP2166
• 发表日期: 2025
• 页码: 2080-2127
• 关键词: mixing times

摘要

We consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has an internal degint >= 3 and an outgoing degout number of half-edges. Given a stochastic matrix Q, we pick a random perfect matching of the half-edges subject to the constraint that each vertex v has degint(v) neighbours inside its community and the proportion of outgoing half-edges from community i matched to a half-edge from community j is Q(i, j). Assuming the number of communities is constant and they all have comparable sizes, we prove the following dichotomy: simple random walk on the resulting graph exhibits cutoff if and only if the product of the Cheeger constant of Q times log n (where n is the number of vertices) diverges. In (Ann. Appl. Probab. 30 (2020) 1824-1846), Ben-Hamou established a dichotomy for cutoff for a nonbacktracking random walk on a similar random graph model with two communities. We prove that the same characterisation of cutoff holds for simple random walk.