Supercritical Site Percolation on Regular Graphs

Sahar Diskin, Michael Krivelevich, Itay Markbreit · 2026

Read Supercritical Site Percolation on Regular Graphs by Sahar Diskin, Michael Krivelevich, Itay Markbreit (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-19038.txt.

Introduction

Diskin and co-authors study site percolation on regular graphs in the just-above-threshold range. They give tight terms for when a single giant cluster emerges in the kept sites. That cluster holds a set share of all sites, while the rest stay tiny. Their results cover the hypercube and pseudo-random graphs. They settle two open questions for those cases. They also weigh how site percolation matches and differs from the edge form. Both fixed and growing degree cases are covered in the work.

Catalog record

CREATORSahar Diskin, Michael Krivelevich, Itay Markbreit
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79808
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.19038

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Supercritical Site Percolation on Regular Graphs Sahar Diskin, Michael Krivelevich, Itay Markbreit Abstract We consider site (vertex) percolation on d d -regular graphs, for both constant-degree and growing-degree cases. We give sufficient, and relatively tight, conditions for the emergence of the “Erdős-Rényi component phenomenon” in the supercritical regime p = 1 + ϵ d − 1 p=\frac{1+\epsilon}{d-1} : namely, the appearance of a unique giant component of order n / d n/d in the percolated subgraph, with all other components being of size O ⁡ ( log ⁡ n ) O(\log n) . Our main results apply both to the d d -dimensional hypercube and to pseudo-random graphs, and resolve two open questions in these cases. We further discuss differences (and similarities) between bond (edge) percolation setting and site percolation setting. 1 Introduction and Main Results Given a host graph G=(V,E) and probability p\in[0,1] , in p -site-percolation we form a random subset V_{p}\subseteq V by including each vertex v\in V in V_{p} independently and with probability p , and consider the subgraph G[V_{p}] . A tightly related model, which has perhaps been more studied between the two, is the p -bond-percolation . There, one forms a random subgraph G_{p} of a host graph G=(V,E) by retaining each edge of G with probability p . When the probability p is clear from the context, we omit it and write site percolation and bond percolation. In 1957, Broadbent and Hammersley [ 10 ] initiated the study of percolation theory in order to model the flow of fluid through a medium with randomly blocked channels. Since then, the theory of percolation has been studied extensively (see [ 8 ] , [ 20 ] and [ 25 ] for systematic coverage). We first review some results in the bond percolation setting. The classical binomial random graph G_{n,p} is an instance of bond percolation (indeed, (K_{n})_{p}\cong G_{n,p} ). A classical result of Erdős and Rényi from 1960 [ 17 ] states that G_{n,p} undergoes a fundamental phase transition with respect to its component structure when the expected average degree is around 1 (that is, n\cdot p\approx 1 ). Formally, for an integer d\geq 3 and p\in(0,1) , let q\coloneqq q(p) be the unique solution in (0,1) of the equation: \displaystyle q=(1-p+pq)^{d-1}. This is the extinction probability of a Galton-Watson tree with offspring distribution Bin(d-1,p) (see, for example, [ 5 ] and [ 16 , Section 4.3.4] ). Consider the probability y\coloneqq y(p) that the root of an infinite d -regular tree belongs to an infinite cluster after p -bond-percolation. Then, y is given by \begin{split}y&=\sum_{i=1}^{d}\binom{d}{i}p^{i}(1-p)^{d-i}(1-q^{i})=\sum_{i=1}^{d}\binom{d}{i}p^{i}(1-p)^{d-i}-\sum_{i=1}^{d}\binom{d}{i}(pq)^{i}(1-p)^{d-i}\\ &=1-(1-p+pq)^{d}=1-q(1-p)-pq^{2}.\end{split} Let us note that when d tends to infinity and p=\frac{1+\epsilon}{d-1} , for small constant \epsilon>0 , then y\coloneqq y(\epsilon) is asymptotically equal to the unique solution in (0,1) of 1-y=\exp(-(1+\epsilon)y) . We can now explain the result of Erdős and Rényi. They showed that when p=\frac{1-\epsilon}{n} , typically all components of G_{n,p} are of size O(\log n/\epsilon^{2}) , and when p=\frac{1+\epsilon}{n} , there typically exists a unique giant component L_{1} in G_{n,p} of order (1+o(1))y(\epsilon)n , and all other components of G_{n,p} are of size O(\log n/\epsilon^{2}) (which is exactly the same order as in the subcritical regime). The phenomenon Erdős and Rényi discovered for bond percolation on the complete graph K_{n} was extended to other (families of) graphs, such as bond percolation on pseudo-random (n,d,\lambda) -graphs [ 19 ] and on the hypercube Q^{d} [ 1 , 6 ] (see also [ 30 ] ). Recently, Diskin and Krivelevich [ 14 , 15 ] found that assuming optimal vertex and edge expansions up to sizes O(\log n) and O(d\log n) , respectively, together with a very mild ‘global’ edge expansion, are sufficient to typically have a unique giant component in the percolated subgraph of order y(\epsilon)n , and all other components are of typical order of O(\log n/\epsilon^{2}) , where p=\frac{1+\epsilon}{d-1} . They also showed that these conditions are tight in a certain well-defined quantitative sense. In this paper, we consider the p -site-percolation setting and aim to extend the bond percolation results to the site percolation setting. In the site percolation setting, the anticipated result is slightly different from the aforementioned bond percolation result. We now formulate the phenomenon we aim to establish. First, we observe that the probability that the root of an infinite d -regular tree is in the infinite cluster after site percolation is the same, up to the sampling of the root itself, as the probability that the root is in an infinite cluster after bond percolation. Therefore, if we define x:=x(p) to be the probability that the root of an infinite d -regular tree belongs to an infinite cluster after p -site-percolation, then x=p\cdot y=p-pq(1-p)-p^{2}q^{2}. (1) It can be seen that when d tends to infinity and p=\frac{1+\epsilon}{d-1} , for small constant \epsilon>0 , then the asymptotic behavior of x is x=\frac{2\epsilon-O\left(\epsilon^{2}\right)}{d} . We say that a d -regular host graph G on n vertices exhibits the Erdős-Rényi component phenomenon (ERCP), if given a sufficiently small constant \epsilon>0 and p=\frac{1+\epsilon}{d-1} , G[V_{p}] possesses whp 1 1 1 With high probability, that is, with probability tending to one as n tends to infinity. the following properties: a unique giant component of asymptotic order x\cdot n emerges, and all other components have order O\left(\frac{\log(n/d)}{\epsilon^{2}}\right) . Note that we focus on the supercritical regime in this paper since the subcritical regime, where p=\frac{1-\epsilon}{d-1} , is completely solved in this context. Indeed, Diskin and Krivelevich [ 12 ] showed that in this regime whp all components in G[V_{p}] are of size O\left(\frac{\log(n/d)}{\epsilon^{2}}\right) (see also [ 29 ] ). Let us mention a few prominent cases where ERCP has been partially established: for the d -dimensional Hamming torus [ 32 ] , for pseudo-random (n,d,\lambda) -graphs [ 12 , 29 ] and for the binary hypercube Q^{d} [ 7 ] it was shown that whp there is a unique giant component (in the percolated subgraph) of asymptotic order x\cdot n . For the binary hypercube Q^{d} , Bollobás, Kohayakawa, and Łuczak [ 7 ] further showed that all other components of Q^{d}[V_{p}] are of size at most d^{10} . This result has been improved in [ 13 ] , showing that all other components of Q^{d}[V_{p}] are of typical size of O\left(d/\epsilon^{5}\right) , thus nearly establishing ERCP in full. The purpose of this paper is to establish sufficient, and relatively tight, conditions under which ERCP will hold in full. Note that in fact these conditions will capture the aforementioned cases (and thereby resolve open problems in their context). We show that a very mild ‘global’ edge expansion, together with some control on the ‘local’ expansion of the graph, provide sufficient conditions for a d -regular graph G to exhibit ERCP (Theorem 1 and Theorem 4 ). In addition, in the case where d\coloneqq d(n) tends to infinity, we show in Theorem 3 that the conditions of Theorem 1 are relatively tight. Interestingly, achieving the same phenomenon in site- and bond-percolation necessitates different ‘local’ assumptions. We also give a concrete statement handling (n,d,\lambda) -graphs in full (Theorem 2 ). Before stating our results, we note that in the growing-degree case, we write p=\frac{1+\epsilon}{d} instead of p=\frac{1+\epsilon}{d-1}

Read the complete text