Band Random Graphs: Connectivity, Geometry, and Transport
Abstract
Let G(n,p,m) be the random subgraph of the cycle power Cnm obtained by retaining each edge independently with probability p. We study connectivity, component geometry, and random walks throughout the regime log n≪ m<n/2. We prove that p∼(log n)/(2m) is a sharp threshold for connectivity. If n(1−p)2m→λ∈(0,∞), then the number of isolated vertices converges to Poisson(λ), and with high probability every other vertex lies in a single component C1. In particular, the connectivity probability converges to e−λ. The component C1 contains a cyclic chain of connected sets occupying all but an o(1) fraction of each consecutive block of length asymp m, with Θ(mlog n) edges between consecutive sets. Its diameter has order n/m+log n/loglog n with high probability. For every fixed c>1, uniformly over p≥ clog n/(2m), the lazy-walk spectral gap is asymptotic in probability to that of Cnm. In the same range, the mean hitting time of simple random walk satisfies, uniformly over distinct x,y, HG(x,y)=2|E(G)|/dG(y) +(rxy(n−rxy))/κm +oProb(n+n2/m2), where rxy is cyclic distance between vertices x and y, dG(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.
Related
- Maximum degree for random geometric graphs in the connectivity regime and beyond
- On the Local Resilience of Random Geometric Graphs With Respect to Connectivity and Long Cycles
- Inhomogeneous random graphs: how heavy tails reshape connectivity
- Optimal detection of geometry in random graphs and kernel matrices at critical thresholds
- Delocalization and Quantum Diffusion of Random Band Matrices in High Dimensions I: Self-energy Renormalization
BibTeX
@misc{chakraborty2026band,
title = {{Band Random Graphs: Connectivity, Geometry, and Transport}},
author = {Shantanav Chakraborty and Kyle Luh and Rudransh Pratap Singh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42107},
eprint = {2610.42107},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42107},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Band Random Graphs: Connectivity, Geometry, and Transport
AU - Shantanav Chakraborty
AU - Kyle Luh
AU - Rudransh Pratap Singh
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42107
UR - https://arxiv.org/abs/2610.42107
AB - 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 log n≪ m<n/2. We prove that p∼(log n)/(2m) is a sharp threshold for connectivity. If n(1−p)^2m→λ∈(0,∞), 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 asymp m, with Θ(mlog n) edges between consecutive sets. Its diameter has order n/m+log n/loglog n with high probability. For every fixed c>1, uniformly over p≥ clog 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)=2|E(G)|/d_G(y) +(r_xy(n−r_xy))/κ_m +o_Prob(n+n^2/m^2), 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.
ER -