Band Random Graphs: Connectivity, Geometry, and Transport
math.PR, math.CO
Submitted: 2026-10-30
Updated: 2026-10-30
Comments: 55 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: Let G(n,p,m) be the random subgraph of the cycle power C n m obtained by retaining each edge independently with probability p.
Terminology
Abstract
Let G(n,p,m) be the random subgraph of the cycle power C n m obtained by retaining each edge independently with probability p. We study connectivity, component geometry, and random walks throughout the regime n much less than m<n/2. We prove that p about(n)/(2m) is a sharp threshold for connectivity. If n(1-p) 2m toλ in(0, infinity), then the number of isolated vertices converges to Poisson(λ), and with high probability every other vertex lies in a single component C 1. In particular, the connectivity probability converges to e-λ. The component C 1 contains a cyclic chain of connected sets occupying all but an o(1) fraction of each consecutive block of length m, with Θ(m n) edges between consecutive sets. Its diameter has order n/m+ n/ n with high probability. For every fixed c>1, uniformly over p at least c n/(2m), the lazy-walk spectral gap is asymptotic in probability to that of C n m. In the same range, the mean hitting time of simple random walk satisfies, uniformly over distinct x,y, H G(x,y)= 2E(G) over d G(y) + r xy(n-r xy) over κ m +o Prob (n+ n squared over m squared), where r xy is cyclic distance between vertices x and y, d G(z) is the degree of vertex z and κ m=(m+1)(2m+1)/6. Thus, for this random graph model, connectivity has the Erdős--Rényi asymptotics with 2m possible neighbours, while distances, relaxation, and hitting times retain the geometry of the underlying cycle.
Sources
- Delocalization of One-Dimensional Random Band Matrices
- The Zigzag Strategy for Random Band Matrices
- Localization of One-Dimensional Random Band Matrices
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves