Abstract
Random graph theory studies how global structure emerges from simple local rules. The classical
Erd˝os-R´enyi model is the most prominent example: every pair of vertices is connected independently
with the same probability. This model has a remarkably complete theory and displays sharp transitions
for the appearance of components, cycles, a giant component, and connectivity. Nevertheless, many
mathematical and physical networks are not well represented by a completely homogeneous model. In
systems with an underlying geometry, edges are often constrained by spatial locality. Particles interact
mainly with nearby particles, lattice Hamiltonians are often local or quasi-local, communication links
may be restricted by distance, and random walks on such networks inherit the geometry of the ambient
space.
This thesis introduces a new model in which randomness and geometry coexist: the periodic
band random graph. The vertices are placed on the discrete cycle Zn, two vertices are eligible to be
connected only when their cyclic distance is at most a bandwidth parameter m, and each eligible edge
is then retained independently with probability p
The first main result of the thesis is a sharp connectivity threshold for this model. Since each
vertex has exactly 2m admissible neighbours in the deterministic host graph, the probability that a
fixed vertex is isolated is (1 − p)
2m. This suggests that isolated vertices disappear when
pconn(n) ∼
log n
2m
.
We prove that this is the correct sharp threshold: below this scale, isolated vertices persist with high
probability, while above this scale the graph is connected with high probability.
The proof above the threshold is not a purely mean-field argument. In the Erd˝os-R´enyi graph, the
number of possible edges between a set and its complement depends only on the size of the set. In
the band random graph, it also depends on the shape and location of the set along the cycle. Long
intervals have much smaller boundaries than scattered sets of the same size. To overcome this, we
use a geometric block-decomposition argument: large connected pieces are built inside consecutive
intervals, neighbouring pieces are joined across their interfaces, and all small leftover sets are shown to
attach to the resulting connected chain.
We also analyze the graph just below the connectivity threshold. When
p =
log n − c
2m
, c > 0,
the graph is disconnected, but the disconnectedness is caused only by isolated vertices. More precisely,
the number Niso of isolated vertices converges in distribution to a Poisson random variable with mean
e
c
, and with high probability there is a unique giant component C1 satisfying
|C1| = n − Niso.
Thus every non-isolated vertex lies in the giant component. Moreover, unlike in the homogeneous Erd˝os-R´enyi model, this giant component has an explicit geometric structure: it contains an ordered
chain of large connected pieces inside consecutive m-blocks of the cycle, joined across neighbouring
interfaces.
The thesis also studies the random walk on the band random graph. The underlying cycle geometry
creates bottlenecks which persist even after the graph becomes connected. These bottlenecks are
reflected in the spectral gap of the lazy random walk. We show that, in the regime considered here,
the lazy spectral gap has order
γlazy(G) = Θ
m2
n2
and consequently obtain the corresponding mixing-time estimate. Finally, using electrical-network
methods, effective resistance, and explicit flow constructions, we prove that the maximal hitting time
of the simple random walk has order
Hmax(PG) = Θ
max
n
2
m2
, n .
The first term reflects diffusive motion around the cycle with step range m, while the second term
is the natural order of the time needed to hit a specified vertex when the stationary distribution is
close to uniform.
Overall, the thesis shows that the periodic band random graph is a useful model for studying
how independent randomness interacts with deterministic geometry. On the graph-theoretic side,
the model retains part of the Erd˝os-R´enyi connectivity picture: isolated vertices still determine the
sharp connectivity threshold. On the random-walk side, however, the behaviour is controlled by the
one-dimensional band structure, which produces the spectral-gap and hitting-time scales described
above.
The model also suggests a broader spectral direction. If AH denotes the adjacency matrix of the
deterministic host graph C
m
n
, then the adjacency matrix of the sampled graph can be written as
AG = pAH +
p
2mp(1 − p) W,
where W is a centered random band matrix supported on the same band. Thus AG is the sum of a
full-rank deterministic band operator and a random band fluctuation. While this thesis focuses mainly
on connectivity and random walks, the bulk and edge spectra of AG remain largely open and are a
natural direction for future work, connec