Repository logo
 

Cutoff for Ramanujan graphs via degree inflation

Published version
Peer-reviewed

Change log

Authors

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