Cutoff for Simple Random Walk on Preferential Attachment Graphs

arXiv:2611.00717 · math.PR · Submitted 2026-10-31 · Read on arXiv

math.PR

Submitted: 2026-10-31

Updated: 2026-10-31

License: http://creativecommons.org/licenses/by/4.0/

The gist: We consider simple random walk on the sequential affine preferential attachment graphs with fixed parameters m at least2 and δ at least0.

Terminology

Abstract

We consider simple random walk on the sequential affine preferential attachment graphs with fixed parameters m at least2 and δ at least0. We prove the walk has total-variation cutoff, and for every fixed epsilon in(0,1), [t mix(n)(epsilon) = n over νd +O P! (sqrt 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 infinity distance from stationarity. When m at least2, the spectral gap is bounded away from zero with high probability which completes the upper-bound coupling argument.

Sources

Related papers