UNIVERSALITY OF CUTOFF FOR GRAPHS WITH AN ADDED RANDOM MATCHING

Jonathan Hermon, Allan Sly, Perla Sousi

Research output: Contribution to journalArticlepeer-review

1 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 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. This provides a simple generic operation of adding some randomness to a given graph, which results in cutoff

Original languageEnglish (US)
Pages (from-to)203-240
Number of pages38
JournalAnnals of Probability
Volume50
Issue number1
DOIs
StatePublished - Jan 2022

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Cutoff
  • Entropy
  • Mixing time
  • Quasi trees
  • Random graph

Fingerprint

Dive into the research topics of 'UNIVERSALITY OF CUTOFF FOR GRAPHS WITH AN ADDED RANDOM MATCHING'. Together they form a unique fingerprint.

Cite this