UNIVERSALITY OF CUTOFF FOR GRAPHS WITH AN ADDED RANDOM MATCHING

Jonathan Hermon; Allan Sly; Perla Sousi

doi:10.1214/21-AOP1532

UNIVERSALITY OF CUTOFF FOR GRAPHS WITH AN ADDED RANDOM MATCHING

Jonathan Hermon, Allan Sly, Perla Sousi

Mathematics

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

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 |V | even we define a random graph G* = (V,E ∪ 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.

Original language	English (US)
Pages (from-to)	203-240
Number of pages	38
Journal	Annals of Probability
Volume	50
Issue number	1
DOIs	https://doi.org/10.1214/21-AOP1532
State	Published - Jan 2022

All Science Journal Classification (ASJC) codes

Statistics and Probability
Statistics, Probability and Uncertainty

Keywords

Cutoff
Entropy
Mixing time
Quasi trees
Random graph

Access to Document

10.1214/21-AOP1532

Cite this

@article{f1fa9f3da3ce4d0e862f37a180fd3eea,

title = "UNIVERSALITY OF CUTOFF FOR GRAPHS WITH AN ADDED RANDOM MATCHING",

abstract = "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 |V | even we define a random graph G* = (V,E ∪ 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 Gn of diverging sizes and of uniformly bounded degree, if the minimal size of a connected component of Gn is at least 3 for all n, then the random walk on G*n exhibits cutoff w.h.p.",

keywords = "Cutoff, Entropy, Mixing time, Quasi trees, Random graph",

author = "Jonathan Hermon and Allan Sly and Perla Sousi",

note = "Publisher Copyright: {\textcopyright} Institute of Mathematical Statistics, 2022",

year = "2022",

month = jan,

doi = "10.1214/21-AOP1532",

language = "English (US)",

volume = "50",

pages = "203--240",

journal = "Annals of Probability",

issn = "0091-1798",

publisher = "Institute of Mathematical Statistics",

number = "1",

}

TY - JOUR

T1 - UNIVERSALITY OF CUTOFF FOR GRAPHS WITH AN ADDED RANDOM MATCHING

AU - Hermon, Jonathan

AU - Sly, Allan

AU - Sousi, Perla

N1 - Publisher Copyright: © Institute of Mathematical Statistics, 2022

PY - 2022/1

Y1 - 2022/1

N2 - 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 |V | even we define a random graph G* = (V,E ∪ 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 Gn of diverging sizes and of uniformly bounded degree, if the minimal size of a connected component of Gn is at least 3 for all n, then the random walk on G*n exhibits cutoff w.h.p.

AB - 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 |V | even we define a random graph G* = (V,E ∪ 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 Gn of diverging sizes and of uniformly bounded degree, if the minimal size of a connected component of Gn is at least 3 for all n, then the random walk on G*n exhibits cutoff w.h.p.

KW - Cutoff

KW - Entropy

KW - Mixing time

KW - Quasi trees

KW - Random graph

UR - http://www.scopus.com/inward/record.url?scp=85125698614&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85125698614&partnerID=8YFLogxK

U2 - 10.1214/21-AOP1532

DO - 10.1214/21-AOP1532

M3 - Article

AN - SCOPUS:85125698614

SN - 0091-1798

VL - 50

SP - 203

EP - 240

JO - Annals of Probability

JF - Annals of Probability

IS - 1

ER -

UNIVERSALITY OF CUTOFF FOR GRAPHS WITH AN ADDED RANDOM MATCHING

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this