József Balogh, Boris Pittel · Random Structures and Algorithms · 2006
Abstract The k ‐parameter bootstrap percolation on a graph is a model of an interacting particle system, which can also be viewed as a variant of a cellular automaton growth process with threshold k ≥ 2. At the start, each of the graph vertices is active with probability p and inactive with probability 1 − p , independently of other vertices. Presence of active vertices triggers a bootstrap percolation process controlled by a recursive rule: an active vertex remains active forever, and a currently inactive vertex becomes active when at least k of its neighbors are active. The basic problem is to identify, for a given graph, p − and p + such that for p < p − ( p > p + resp.) the probability that all vertices are eventually active is very close to 0 (1 resp.). The bootstrap percolation process is a deterministic process on the space of subsets of the vertex set, which is easy to describe but hard to analyze rigorously in general. We study the percolation on the random d ‐regular graph, d ≥ 3, via analysis of the process on the multigraph counterpart of the graph. Here, thanks to a “principle of deferred decisions,” the percolation dynamics is described by a surprisingly simple Markov chain. Its generic state is formed by the counts of currently active and nonactive vertices having various degrees of activation capabilities. We replace the chain by a deterministic dynamical system, and use its integrals to show—via exponential supermartingales—that the percolation process undergoes relatively small fluctuations around the deterministic trajectory. This allows us to show existence of the phase transition within an interval [ p − ( n ), p + ( n )], such that (1) p ± ( n ) → p * = 1 − min y ∈(0,1) y /ℙ(Bin( d − 1,1 − y ) < k ); (2) p + ( n ) − p − ( n ) is of order n −1/2 for k < d − 1, and n , (ε n ↓ 0, ε n log n → ∞ ), for k = d − 1. Note that p * is the same as the critical probability of the process on the corresponding infinite regular tree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 30, 257–286, 2007
Cited by 175
Revista, Zen, MATH, 10 · Zenodo (CERN European Organization for Nuclear Research) · 2025
Expander graphs are sparse graphs possessing exceptionally strong connectivity, making them indispensable in theoretical computer science, network design, and pure mathematics. While the probabilistic existence of optimal expanders has been known for decades, explicit constructions remain complex. This paper provides a comprehensive conceptual framework for understanding how random regular graph constructions offer a practical and theoretically robust pathway to achieving near-optimal expander properties. We delineate the theoretical underpinnings of expander graphs, focusing on the spectral gap as a key quantifier of expansion capabilities. A detailed review of random graph models is presented, with particular emphasis on the configuration model for generating random regular graphs, and we synthesize their known probabilistic expansion properties from established literature. Through an analysis of existing theoretical and empirical findings, we illustrate that random regular graphs inherently exhibit high expansion, frequently approaching the theoretical Ramanujan bound with high probability for sufficiently large graphs. We explore the relationship between graph parameters, such as degree and number of vertices, and the resulting spectral characteristics, offering insights into how these construction methodologies can be leveraged to optimize expansion in practical settings. This work posits that while explicit constructions are mathematically intricate, random regular graphs provide a straightforward and effective means to generate graphs with excellent expander properties, thereby bridging the gap between theoretical existence and practical applicability. This paper contributes a cohesive framework for understanding and utilizing random regular graphs for designing robust and efficient network structures.
Cited by 0Open access
Revista, Zen, MATH, 10 · Zenodo (CERN European Organization for Nuclear Research) · 2025
Expander graphs are sparse graphs possessing exceptionally strong connectivity, making them indispensable in theoretical computer science, network design, and pure mathematics. While the probabilistic existence of optimal expanders has been known for decades, explicit constructions remain complex. This paper provides a comprehensive conceptual framework for understanding how random regular graph constructions offer a practical and theoretically robust pathway to achieving near-optimal expander properties. We delineate the theoretical underpinnings of expander graphs, focusing on the spectral gap as a key quantifier of expansion capabilities. A detailed review of random graph models is presented, with particular emphasis on the configuration model for generating random regular graphs, and we synthesize their known probabilistic expansion properties from established literature. Through an analysis of existing theoretical and empirical findings, we illustrate that random regular graphs inherently exhibit high expansion, frequently approaching the theoretical Ramanujan bound with high probability for sufficiently large graphs. We explore the relationship between graph parameters, such as degree and number of vertices, and the resulting spectral characteristics, offering insights into how these construction methodologies can be leveraged to optimize expansion in practical settings. This work posits that while explicit constructions are mathematically intricate, random regular graphs provide a straightforward and effective means to generate graphs with excellent expander properties, thereby bridging the gap between theoretical existence and practical applicability. This paper contributes a cohesive framework for understanding and utilizing random regular graphs for designing robust and efficient network structures.
Cited by 0Open access
Peyman Faizian, Md Atiqul Mollah, Xin Yuan et al. · IEEE Transactions on Parallel and Distributed Systems · 2017
The Random regular graph (RRG) has recently been proposed as an interconnect topology for future large scale data centers and HPC clusters. An RRG is a special case of directed regular graph (DRG) where each link is unidirectional and all nodes have the same number of incoming and outgoing links. In this work, we establish bounds for DRGs on diameter, average k-shortest path length, and a load balancing property with k-shortest path routing, and use these bounds to evaluate RRGs. The results indicate that an RRG with k-shortest path routing is not ideal in terms of diameter and load balancing. We further consider the Generalized De Bruijn Graph (GDBG), a deterministic DRG, and prove that for most network configurations, a GDBG is near optimal in terms of diameter, average k-shortest path length, and load balancing with a k-shortest path routing scheme. Finally, we use modeling and simulation to exploit the strengths and weaknesses of RRGs for different traffic conditions by comparing RRGs with GDBGs.
Cited by 15
M. Pino, José E. Román · arXiv (Cornell University) · 2023
We analyze the ergodic properties of a metallic wavefunction for the Anderson model in a disordered random-regular graph with branching number $k=2.$ A few q-moments $I_q$ associated with the zero energy eigenvector are numerically computed up to sizes $N=4\times 10^6.$ We extract their corresponding fractal dimensions $D_q$ in the thermodynamic limit together with correlated volumes $N_q$ that control finite-size effects. At intermediate values of disorder $W,$ we obtain ergodicity $D_q=1$ for $q=1,2$ and correlation volumes that increase fast upon approaching the Anderson transition $\log(\log(N_q))\sim W.$ We then focus on the extraction of the volume $N_0$ associated with the typical value of the wavefunction $e^{<\log|ψ|^2>},$ which follows a similar tendency as the ones for $N_1$ or $N_2.$ Its value at intermediate disorders is close, but smaller, to the so-called ergodic volume previously found via the super-symmetric formalism and belief propagator algorithms. None of the computed correlated volumes shows a tendency to diverge up to disorders $W\approx 15$, specifically none with exponent $ν=1/2$. Deeper in the metal, we characterize the crossover to system sizes much smaller than the first correlated volume $N_1\gg N.$ Once this crossover has taken place, we obtain evidence of a scaling in which the derivative of the first fractal dimension $D_1$ behaves critically with an exponent $ν=1.$
Cited by 0Open access
Soumik Ghosh, Dominik Hangleiter, Jonas Helsen · PRX Quantum · 2025
Graph states are fundamental objects in the theory of quantum information due to their simple classical description and rich entanglement structure. They are also intimately related to instantaneous quantum polynomial-time (IQP) circuits, which have applications in quantum pseudorandomness and quantum advantage. For us, they are a toy model to understand the relation between circuit connectivity, entanglement structure, and computational complexity. In the worst case, a strict dichotomy in the computational universality of such graph states appears as a function of the degree <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"> <a:mi>d</a:mi> </a:math> of a regular graph state [Ghosh , Phys. Rev. Lett. 131, 030601 (2023)]. In this paper, we study the average-case complexity of simulating random graph states of varying degree when measured in random product bases and give distinct evidence that a similar complexity-theoretic dichotomy exists in the average case. Specifically, we consider random <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"> <c:mi>d</c:mi> </c:math> -regular graph states and prove three distinct results: First, we show two families of IQP circuits of depth <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"> <e:mi>d</e:mi> </e:math> and show that they anticoncentrate for any <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"> <g:mn>2</g:mn> <g:mo><</g:mo> <g:mi>d</g:mi> <g:mo>=</g:mo> <g:mi>o</g:mi> <g:mo stretchy="false">(</g:mo> <g:msup> <g:mi>n</g:mi> <g:mrow> <g:mn>1</g:mn> <g:mo>/</g:mo> <g:mn>2</g:mn> </g:mrow> </g:msup> <g:mo stretchy="false">)</g:mo> </g:math> when measured in a random <k:math xmlns:k="http://www.w3.org/1998/Math/MathML" display="inline"> <k:mi>X</k:mi> </k:math> - <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline"> <m:mi>Y</m:mi> </m:math> plane product basis. This implies anticoncentration for random constant-regular graph states. Second, in the regime <o:math xmlns:o="http://www.w3.org/1998/Math/MathML" display="inline"> <o:mi>d</o:mi> <o:mo>=</o:mo> <o:mi mathvariant="normal">Θ</o:mi> <o:mo stretchy="false">(</o:mo> <o:msup> <o:mi>n</o:mi> <o:mi>c</o:mi> </o:msup> <o:mo stretchy="false">)</o:mo> </o:math> with <t:math xmlns:t="http://www.w3.org/1998/Math/MathML" display="inline"> <t:mi>c</t:mi> <t:mo>∈</t:mo> <t:mo stretchy="false">(</t:mo> <t:mn>0</t:mn> <t:mo>,</t:mo> <t:mn>1</t:mn> <t:mo stretchy="false">)</t:mo> </t:math> , we prove that random <x:math xmlns:x="http://www.w3.org/1998/Math/MathML" display="inline"> <x:mi>d</x:mi> </x:math> -regular graph states contain polynomially large grid graphs as induced subgraphs with high probability. This implies that they are universal resource states for measurement-based computation. Third, in the regime of high degree ( <z:math xmlns:z="http://www.w3.org/1998/Math/MathML" display="inline"> <z:mi>d</z:mi> <z:mo>∼</z:mo> <z:mi>n</z:mi> <z:mo>/</z:mo> <z:mn>2</z:mn> </z:math> ), we show that random graph states are not sufficiently entangled to be trivially classically simulable, unlike Haar-random states. Proving the three results requires different techniques—the analysis of a classical statistical-mechanics model using Krawtchouck polynomials, graph-theoretic analysis using the switching method, and analysis of the ranks of submatrices of random adjacency matrices, respectively.
Cited by 0Open access
Josep Dı́az, Alexis C. Kaporis, Graeme Kemkes et al. · Journal of Graph Theory · 2009
Abstract It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009
Cited by 5
Xu, Jeff · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2025
In this work, we give novel spectral norm bounds for graph matrix on inputs being random regular graphs. Graph matrix is a family of random matrices with entries given by polynomial functions of the underlying input. These matrices have been known to be the backbone for the analysis of various average-case algorithms and hardness. Previous investigations of such matrices are largely restricted to the Erdős-Rényi model, and tight matrix norm bounds on regular graphs are only known for specific examples. We unite these two lines of investigations, and give the first result departing from the Erdős-Rényi setting in the full generality of graph matrices. We believe our norm bound result would enable a simple transfer of spectral analysis for average-case algorithms and hardness between these two distributions of random graphs. As an application of our spectral norm bounds, we show that higher-degree Sum-of-Squares lower bounds for the independent set problem on Erdős-Rényi random graphs can be switched into lower bounds on random d-regular graphs. Our main conceptual insight is that existing Sum-of-Squares lower bounds analysis based on moment methods are surprisingly robust, and amenable for a light-weight translation. Our result is the first to address the general open question of analyzing higher-degree Sum-of-Squares on random regular graphs.
Cited by 0Open access
Soumya Bera, Giuseppe De Tomasi, Ivan M. Khaymovich et al. · Physical review. B./Physical review. B · 2018
We study the return probability for the Anderson model on the random regular graph and give evidence of the existence of two distinct phases: a fully ergodic and nonergodic one. In the ergodic phase, the return probability decays polynomially with time with oscillations, being the attribute of the Wigner-Dyson-like behavior, while in the nonergodic phase the decay follows a stretched exponential decay. We give a phenomenological interpretation of the stretched exponential decay in terms of a classical random walker. Furthermore, comparing typical and mean values of the return probability, we show how to differentiate an ergodic phase from a nonergodic one. We benchmark this method first in two random matrix models, the power-law random banded matrices, and the Rosenzweig-Porter matrices, which host both phases. Second, we apply this method to the Anderson model on the random regular graph to give further evidence of the existence of the two phases.
Cited by 101Open access
M. Pino, José E. Román · Physical review. B./Physical review. B · 2024
We study the metallic phase of the Anderson model in a random-regular graph, specifically the degree of ergodicity of the high-energy wave functions. We use the multifractal formalism to analyze numerical data for unprecedented large system sizes, obtaining a set of correlated volumes ${N}_{q}$ which control the finite-size effects of the wave function $q$ moment. Those volumes grow very fast, $ln[ln({N}_{q})]\ensuremath{\sim}W,$ with disorder strength but show no tendency to diverge, at least in an intermediate metallic regime. Close to the Anderson transitions, we characterize the crossover to system sizes much smaller than the first correlated volume. Once this crossover has taken place, we obtain evidence of a scaling in which the derivative of the first fractal dimension behaves critically with an exponent $\ensuremath{\nu}=1.$
Cited by 3
BERA, S, DE TOMASI, G, KHAYMOVICH, IM et al. · DSpace (IIT Bombay) · 2018
We study the return probability for the Anderson model on the random regular graph and give evidence of the existence of two distinct phases: a fully ergodic and nonergodic one. In the ergodic phase, the return probability decays polynomially with time with oscillations, being the attribute of the Wigner-Dyson-like behavior, while in the nonergodic phase the decay follows a stretched exponential decay. We give a phenomenological interpretation of the stretched exponential decay in terms of a classical random walker. Furthermore, comparing typical and mean values of the return probability, we show how to differentiate an ergodic phase from a nonergodic one. We benchmark this method first in two random matrix models, the power-law random banded matrices, and the Rosenzweig-Porter matrices, which host both phases. Second, we apply this method to the Anderson model on the random regular graph to give further evidence of the existence of the two phases.
Cited by 0
Dieter Mitsche, Michael Molloy, Paweł Prałat · Journal of Combinatorial Theory Series B · 2019
Cited by 0Open access
Kyra L. Kadhim (11261470), Ann M. Hermundstad (8697366), Kevin S. Brown (7464338) · Figshare · 2021
<p>Panels <b>A-C</b> show sample NCD matrices for Barabási-Albert pulse-coupled oscillator networks with 16 nodes. The mean degree in these networks was drawn randomly from a uniform distribution with range [3,15). According to both ISI and NCD-based categorization, <b>A</b> is a temporally-regular state, <b>B</b> is a chimera state, and <b>C</b> is a temporally-irregular state. Panels <b>D-F</b> show sample NCD matrices for states of 16-node Newman-Watts-Strogatz networks. Each node is connected to its two nearest neighbors and additional edges were added with probability drawn randomly from a uniform distribution with range [0.2,0.8). Similar to the first row, (<b>D</b>) is a temporally-regular state, (<b>E</b>) is a chimera state, and (<b>F</b>) is a temporally-irregular state.</p>
Cited by 0Open access
Zheng Choo · Oxford University Research Archive (ORA) (University of Oxford) · 2014
<p>We investigate the probability that a random walk covers a given edge in a connected regular network. For a complete graph or a circle graph, we obtain an explicit expression of the coverage probability by using the walk generating function. Alternatively, for any fixed connected regular network, we use the largest eigenvalue of the adjacency matrix of the network with the given edge removed from the original network to give a lower bound for the coverage probability. Finally, we give the results by Cooper and Frieze (2013) on the coverage probabilities of nice edges for random regular networks.</p> <p>The motivation of this project is to obtain properties of a network from a new perspective, which is through primes of a network using random walks. Primes are simple paths and simple cycles in a network, which can be seen as building blocks of a network. A network is uniquely determined by its set of primes.</p> <p>A network can be explored through a random walk on it, and the random walk can be used to detect primes of the network. A necessary condition for retrieving all the primes in a network is that a random walk visits all edges in the network. The approach of investigating the coverage probability of a given edge serves as a first step to investigate the coverage probabilities of primes.</p>
Cited by 0Open access
Tony Johansson · The Electronic Journal of Combinatorics · 2020
We consider a random walk process on graphs introduced by Orenshtein and Shinkar (2014). At any time, the random walk moves from its current position along a previously unvisited edge chosen uniformly at random, if such an edge exists. Otherwise, it walks along a previously visited edge chosen uniformly at random. For the random $r$-regular graph, with $r$ a constant odd integer, we show that this random walk process has asymptotic vertex and edge cover times $\frac{1}{r-2}n\log n$ and $\frac{r}{2(r-2)}n\log n$, respectively, generalizing a result of Cooper, Frieze and the author (2018) from $r = 3$ to any odd $r\geqslant 3$. The leading term of the asymptotic vertex cover time is now known for all fixed $r\geqslant 3$, with Berenbrink, Cooper and Friedetzky (2015) having shown that $G_r$ has vertex cover time asymptotic to $\frac{rn}{2}$ when $r\geqslant 4$ is even.
Cited by 0Open access
Mana Donganont · International Journal of Pure and Apllied Mathematics · 2014
Let G n,d be a random d-regular graph with n vertices. Given a fixed graph H. W denotes the number of induced copies of H in G n,d . In this paper, we use Stein-Chen method and Local approach to show that W can approximate by the Poisson distribution and give the bound of this approximation.
Cited by 0Open access
Mana Donganont · Greater South Information System · 2014
Let G n,d be a random d-regular graph with n vertices.Given a fixed graph H. W denotes the number of induced copies of H in G n,d .In this paper, we use Stein-Chen method and Local approach to show that W can approximate by the Poisson distribution and give the bound of this approximation.
Cited by 0Open access
Mana Donganont · International Journal of Pure and Apllied Mathematics · 2014
Let W be the number of copies of a fixed graph H in a random dregular graph G n,d . In this paper, we give the bound on Poisson approximation of W by using the Stein-Chen method.
Cited by 0Open access
Nayantara Bhatnagar, Allan Sly, Prasad Tetali · Electronic Journal of Probability · 2016
A key insight from statistical physics about spin systems on random graphs is the central role played by Gibbs measures on trees. We determine the local weak limit of the hardcore model on random regular graphs upto a density for the largest independent set that is bounded by and goes asymptotically to the condensation threshold. We show that the hardcore measure converges in probability locally in a strong sense to the free boundary condition Gibbs measure on the tree. As a consequence we show that the reconstruction threshold on the random graph, indicative of the onset of point to set spatial correlations, is equal to the reconstruction threshold on the $d$-regular tree for which we determine precise asymptotics. We expect that our methods will generalize to a wide range of spin systems for which the second moment method holds.
Cited by 1Open access
J. A. Fernley · ArXiv.org · 2025
The regular tree corresponds to the random regular graph as its local limit. For this reason the famous double phase transition of the contact process on regular tree has been seen to correspond to a phase transition on the large random regular graph, at least at the first critical value. In this article, we find a phase transition on that large finite graph at the second critical value: between linear reinfections and reinfections following a long healthy period.
Cited by 0Open access