Research work · 2026
Constraint Network and Structural Evolution B: Spectral Theory of Connectivity Phase Transitions in Random Interval Graphs—From Circle Covering to High-Dimensional Emergence
changzheng zhou, ZIQING zhou
Zenodo (CERN European Organization for Nuclear Research)
Abstract
Starting from the probabilistic ontology of random constraint networks, this paper rigorously constructs the product probability space for random interval graphs,transforming the random arc covering problem on the circle into a connectivityphase transition problem for interval graphs. Under the assumption of absolutelycontinuous measures, we prove the exact probabilistic equivalence between thecovering event and the graph connectivity event, and reinterpret Shepp’s classicalthreshold for random arc covering as a necessary and sufficient condition for theconnectivity phase transition of random interval graphs. By employing spectralgraph theory, we establish two-sided inequalities between the spectral gap of thenormalized Laplacian and the Cheeger constant, yielding tight geometric boundson the mixing time of lazy random walks. Using the covering potential functionas the scaling variable, we derive quantitative scaling laws for the critical spectralgap and mixing time. Furthermore, we extend the theory to random sphericalcap graphs on high-dimensional spheres. By defining a dimension-consistent effective cumulative measure, we obtain a unified connectivity threshold that strictlyreduces to the Shepp condition in two dimensions, thereby healing the scalingfracture between low and high dimensions. We discuss the necessity of threshold corrections due to high-dimensional measure concentration and sphere packingeffects. In the application to cognitive sampling, we propose a formal mappingprotocol from knowledge spaces to spherical cap graphs, define cognitive entropyto quantify the information cost of maintaining knowledge connectivity, and showthat non-uniform sampling raises the global connectivity threshold. The entiretheory rests on explicit measure-theoretic premises, providing a rigorous spectralframework for connectivity phase transitions in random geometric graphs and theirapplications in information science.