CUTOFF FOR RANDOM LIFTS OF WEIGHTED GRAPHS

• 成果类型: Article
• 署名作者: Conchon-Kerjan, Guillaume
• 署名单位: Universite Paris Cite
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/21-AOP1534
• 发表日期: 2022
• 页码: 304-338
• 关键词: random-walks; Random Permutation

摘要

We prove the cutoff phenomenon for the random walk on random n-lifts of finite weighted graphs, even when the random walk on the base graph c of the lift is not reversible. The mixing time is w.h.p. t(mix) = h(-1) log n, where h is a constant associated to G, namely the entropy of its universal cover. Moreover, this mixing time is the smallest possible among all n-lifts of G. In the particular case where the base graph is a vertex with d/2 loops, d even, we obtain a cutoff for a d-regular random graph, as did Lubetzky and Sly in (Duke Math. J. 153 (2010) 475-510) (with a slightly different distribution on d-regular graphs, but the mixing time is the same).