Rudransh Pratap Singh supervised by Dr. Shantanav Chakraborty received his Master of Science – Dual Degree in Computer Science and Engineering (CSD). Here’s a summary of his research work on Band Random Graphs: Connectivity, Geometry and Random Walks

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, connecting the model to random band matrices and localization-type questions in mathematical physics.

July 2026