Cutoff for Simple Random Walk on Preferential Attachment Graphs
Abstract
We consider simple random walk on the sequential affine preferential attachment graphs with fixed parameters m≥2 and δ≥0. We prove the walk has total-variation cutoff, and for every fixed ε∈(0,1), tmix(n)(ε) =(log n)/νd +Oℙ (√(log n)), where ν>0 is the walk speed and d>0 is the entropy per level of harmonic measure on the Pólya--point tree, the local weak limit of the graph. Thus cutoff occurs at the entropic time. Entropic cutoff was previously established for a range of random graph models including configuration models under mild degree assumptions and on Erdős--Rényi random graphs for typical starting points. We extend the harmonic-measure approach to preferential attachment, accounting for its age-dependent structure and hubs of polynomial degree. The local weak limit, the Pólya--point tree, provides a more tractable setting for analyzing the walk. The proof combines regeneration estimates on the local limit tree, a quantitative graph--tree coupling on the mixing-time scale, and control of hub excursions. We show that shortly before the cutoff time its distribution is close in total variation distance to a measure with small L∞ distance from stationarity. When m≥2, the spectral gap is bounded away from zero with high probability which completes the upper-bound coupling argument.
Related
- Cutoff for random Cayley graphs of finite groups
- Spatial preferential attachment models: robustness revisited
- Persistent Hubs and Sharp Asymptotics in Eigenvector Preferential Attachment Trees
- How Robust is Scale-Free Structure? Phase Transitions in Preferential Attachment Model under Attack?
- Asymptotic Normality of the Hill Estimator in Linear Preferential Attachment
BibTeX
@misc{sly2026cutoff,
title = {{Cutoff for Simple Random Walk on Preferential Attachment Graphs}},
author = {Allan Sly and Seoyeon Yang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00717},
eprint = {2611.00717},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00717},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Cutoff for Simple Random Walk on Preferential Attachment Graphs
AU - Allan Sly
AU - Seoyeon Yang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00717
UR - https://arxiv.org/abs/2611.00717
AB - We consider simple random walk on the sequential affine preferential attachment graphs with fixed parameters m≥2 and δ≥0. We prove the walk has total-variation cutoff, and for every fixed ε∈(0,1), t_mix^(n)(ε) =(log n)/νd +O_ℙ (√(log n)), where ν>0 is the walk speed and d>0 is the entropy per level of harmonic measure on the Pólya--point tree, the local weak limit of the graph. Thus cutoff occurs at the entropic time. Entropic cutoff was previously established for a range of random graph models including configuration models under mild degree assumptions and on Erdős--Rényi random graphs for typical starting points. We extend the harmonic-measure approach to preferential attachment, accounting for its age-dependent structure and hubs of polynomial degree. The local weak limit, the Pólya--point tree, provides a more tractable setting for analyzing the walk. The proof combines regeneration estimates on the local limit tree, a quantitative graph--tree coupling on the mixing-time scale, and control of hub excursions. We show that shortly before the cutoff time its distribution is close in total variation distance to a measure with small L^∞ distance from stationarity. When m≥2, the spectral gap is bounded away from zero with high probability which completes the upper-bound coupling argument.
ER -