Band Random Graphs: Connectivity, Geometry, and Transport

arXiv:2610.42107 · math.PR, math.CO · Submitted 2026-10-30 · Read on arXiv

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

Related papers