Cutoff for Ramanujan graphs via degree inflation
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Hermon, Jonathan https://orcid.org/0000-0002-2935-3999
Abstract
Recently Lubetzky and Peres showed that simple random walks on a sequence of d-regular Ramanujan graphs Gn = (Vn, En) of increasing sizes exhibit cutoff in total variation around the diameter lower bound d d−2 logd−1 |Vn|. We provide a different argument under the assumption that for some r(n) 1 the maximal number of simple cycles in a ball of radius r(n) in Gn is uniformly bounded in n.
Description
Keywords
cutoff, Ramanujan graphs, degree inflation
Journal Title
ELECTRONIC COMMUNICATIONS IN PROBABILITY
Conference Name
Journal ISSN
1083-589X
Volume Title
22
Publisher
Institute of Mathematical Statistics