UNIVERSALITY OF CUTOFF FOR GRAPHS WITH AN ADDED RANDOM MATCHING

• 成果类型: Article
• 署名作者: Hermon, Jonathan; Sly, Allan; Sousi, Perla
• 署名单位: University of British Columbia; Princeton University; University of Cambridge
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/21-AOP1532
• 发表日期: 2022
• 页码: 203-240
• 关键词: random-walks

摘要

We establish universality of cutoff for simple random walk on a class of random graphs defined as follows. Given a finite graph G = (V, E) with vertical bar V vertical bar even we define a random graph G* = (V, E U E') obtained by picking E' to be the (unordered) pairs of a random perfect matching of V. We show that for a sequence of such graphs G(n) of diverging sizes and of uniformly bounded degree, if the minimal size of a connected component of G(n) is at least 3 for all n, then the random walk on G(n)* exhibits cutoff w.h.p. This provides a simple generic operation of adding some randomness to a given graph, which results in cutoff.