Bounded Cutoff Window for the Non-backtracking Random Walk on Ramanujan Graphs

Evita Nestoridi; Peter Sarnak

doi:10.1007/s00493-023-00017-8

Bounded Cutoff Window for the Non-backtracking Random Walk on Ramanujan Graphs

Evita Nestoridi
, Peter Sarnak

Mathematics

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

Abstract

We prove that the non-backtracking random walk on Ramanujan graphs with large girth exhibits the fastest possible cutoff with a bounded window.

Original language	English (US)
Pages (from-to)	367-384
Number of pages	18
Journal	Combinatorica
Volume	43
Issue number	2
DOIs	https://doi.org/10.1007/s00493-023-00017-8
State	Published - Apr 2023

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

Almost diameter
Cutoff
Density hypothesis
Non-backtracking random walk
Window

Access to Document

10.1007/s00493-023-00017-8

Cite this

@article{501ad0ebe35d4840a88ee140434d55d7,

title = "Bounded Cutoff Window for the Non-backtracking Random Walk on Ramanujan Graphs",

abstract = "We prove that the non-backtracking random walk on Ramanujan graphs with large girth exhibits the fastest possible cutoff with a bounded window.",

keywords = "Almost diameter, Cutoff, Density hypothesis, Non-backtracking random walk, Window",

author = "Evita Nestoridi and Peter Sarnak",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive licence to J{\'a}nos Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2023",

month = apr,

doi = "10.1007/s00493-023-00017-8",

language = "English (US)",

volume = "43",

pages = "367--384",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "2",

}

TY - JOUR

T1 - Bounded Cutoff Window for the Non-backtracking Random Walk on Ramanujan Graphs

AU - Nestoridi, Evita

AU - Sarnak, Peter

PY - 2023/4

Y1 - 2023/4

N2 - We prove that the non-backtracking random walk on Ramanujan graphs with large girth exhibits the fastest possible cutoff with a bounded window.

AB - We prove that the non-backtracking random walk on Ramanujan graphs with large girth exhibits the fastest possible cutoff with a bounded window.

KW - Almost diameter

KW - Cutoff

KW - Density hypothesis

KW - Non-backtracking random walk

KW - Window

UR - https://www.scopus.com/pages/publications/85160843976

UR - https://www.scopus.com/pages/publications/85160843976#tab=citedBy

U2 - 10.1007/s00493-023-00017-8

DO - 10.1007/s00493-023-00017-8

M3 - Article

AN - SCOPUS:85160843976

SN - 0209-9683

VL - 43

SP - 367

EP - 384

JO - Combinatorica

JF - Combinatorica

IS - 2

ER -

Bounded Cutoff Window for the Non-backtracking Random Walk on Ramanujan Graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this