betaFeedback

WorksMathematics

Combinatorial Properties of The Giant Under Supercritical Percolation

Abstract

We study combinatorial properties, such as diameter and long paths and cycles, of the giant component of percolated graphs. Such combinatorial properties are well studied for classical graphs such as pseudo-random graphs and the hypercube. We aim to obtain similar results for extensive families of dd-regular nn-vertex graphs. Specifically, assuming expansion properties of the host graph, we show a typical vertex expansion by a factor of 1/dlog⁡d1/d\log d in the giant component of the percolated subgraph. As a consequence, we obtain bounds on various combinatorial properties of the giant component. For example, a bound of O(dlog⁡2d+log⁡n)O\left(d\log^2 d+\log n\right) on the typical diameter of the giant component of the percolated subgraph. In addition, we construct graphs with very good vertex and edge expansion, but having large diameter, showing that the diameter of the percolated subgraph is not necessarily typically logarithmic in the number of the vertices of the graph. We also present good expanders such that their percolated subgraph typically contains a bad expanding set.

Introduction

Background and Motivation

In 1957, Broadbent and Hammersley [11] 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 [9], [26] and [30] for systematic coverage).

Given a host graph G=(V,E)G=(V,E) and probability p∈[0,1]p \in[0,1], in pp-bond percolation we form a random subgraph Gp⊆GG_p \subseteq G by retaining each edge of GG independently with probability pp. We call GpG_p the percolated graph.

The most well-studied example of the percolated graph is the binomial random graph Gn,pG_{n,p} when the host graph is the complete graph KnK_n. A classical result of Erdős and Rényi from 1960 [22] states that Gn,pG_{n,p} undergoes a fundamental phase transition with respect to its connected component structure when the expected average degree is around 11 (that is, n⋅p≈1n \cdot p \approx1): for any constant ϵ>0\epsilon> 0, when p=1−ϵnp=\frac{1-\epsilon}{n}, all the components are typically of order O(ϵ−2log⁡n)O\left(\epsilon^{-2}\log n\right), but when p=1+ϵnp=\frac{1+\epsilon}{n}, there typically exists a unique giant component L1L_1 in Gn,pG_{n,p} of order (1+o(1))γn(1+o(1))\gamma n, and all other components of Gn,pG_{n,p} are of order O(ϵ−2log⁡n)O\left(\epsilon^{-2}\log n\right), where

γ:=γ(ϵ)=2ϵ−O(ϵ2)(1)\gamma:= \gamma(\epsilon)=2\epsilon-O\left(\epsilon^2\right) \tag*{(1)}

is the survival probability of the Po⁡(1+ϵ)\operatorname{Po}(1+\epsilon) branching process. For more background on branching processes, see, for example, [5] and [20 Section 4.3.4].

Since then, the phase transition discovered by Erdős and Rényi has been established for several other families of graphs, including pseudo-random (n,d,λ)(n,d,\lambda)-graphs [25] and the dd-dimensional binary hypercube QdQ^d [1, 8, 33]. More precisely, if pp-bond percolation is performed with p=1+ϵdp = \frac{1+\epsilon}{d}, where ϵ>0\epsilon> 0 is a sufficiently small constant and dd is a sufficiently large integer, then, whp1, the percolated graph contains a unique giant component, where its size, and the size of the remaining components match the sizes of the corresponding supercritical random graph.

More recently, Diskin and Krivelevich [17] identified a general set of conditions on the host graph GG guaranteeing the same conclusion on the percolated graph GpG_p. In addition, Diskin, Erde, Kang, and Krivelevich [14] discovered another general set of properties of the host graph GG, under which whp GpG_p contains a unique giant component of the correct order and all remaining components are substantially smaller than the giant component. These results generalized the previous results where the host graph is KnK_n, an (n,d,λ)(n,d,\lambda)-graph, or QdQ^d. We give here the exact statements from [14, 17], using some standard notations defined at the beginning of § 2:

Theorem 1.1 (Theorem 1 of [14]). Let d=ωn(1)d = \omega_n(1), and let GG be a dd-regular nn-vertex graph. Let ϵ>0\epsilon> 0 be a small constant and let p=1+ϵdp = \frac{1+\epsilon}{d}. Then, there exists a constant C0:=C0(ϵ)>0C_0 := C_0(\epsilon) > 0, such that for every C≥C0C \ge C_0 the following holds. If for every U⊆V(G)U \subseteq V(G) with ∣U∣≤n2|U| \le\frac{n}{2}, we have eG(U,Uc)≥C∣U∣e_G(U,U^c) \ge C|U|, then with probability at least 1−od(1)−exp⁡(−Cnd)1-o_d(1)-\exp\left(-\frac{\sqrt{Cn}}{d}\right), the subgraph GpG_p contains a giant component L1L_1, satisfying

∣∣V(L1)∣−γ⋅n∣≤10nC1/20,\left| |V(L_1)|-\gamma\cdot n \right| \le\frac{10n}{C^{1/20}},

where γ:=γ(ϵ)\gamma:= \gamma(\epsilon) is as defined in (1). Furthermore, all other components in GpG_p are of size at most (1+od(1))10nC1/20(1+o_d(1))\frac{10n}{C^{1/20}}.

Theorem 1.2 (Theorem 1 of [17]). Let α,c1,c2,c3>0\alpha,c_1,c_2,c_3 > 0 be constants and let ϵ>0\epsilon> 0 be a sufficiently small constant. Let d,nd,n be sufficiently large integers such that d≥log⁡αnd \ge\log^\alpha n. Let GG be a dd-regular nn-vertex graph, and let p=1+ϵdp = \frac{1+\epsilon}{d}. Suppose there exists a sufficiently large C:=C(ϵ,c1,c2,c3,α)>0C := C(\epsilon,c_1,c_2,c_3,\alpha) > 0 that GG satisfies the following vertex and edge expansion properties.

(P1) For every U⊆V(G)U \subseteq V(G) with ∣U∣≤n2|U| \le\frac{n}{2}, eG(U,Uc)≥c1∣U∣e_G(U,U^c) \ge c_1|U|;

(P2) For every U⊆V(G)U \subseteq V(G) with ∣U∣≤c2log⁡n|U| \le c_2\log n, ∣NG(U)∣≥c3d∣U∣|N_G(U)| \ge c_3d|U|;

(P3) For every U⊆V(G)U \subseteq V(G) with ∣U∣≤Cdlog⁡n|U| \le Cd\log n, eG(U,Uc)≥(1−ϵ3)d∣U∣e_G(U,U^c) \ge(1-\epsilon^3)d|U|.

Then, whp there exists a unique giant component L1L_1 in GpG_p whose size is (1+o(1))γn(1+o(1))\gamma n, where γ:=γ(ϵ)\gamma:= \gamma(\epsilon) is as defined in (1), and all other components in GpG_p are of size O(log⁡nϵ2)O\left(\frac{\log n}{\epsilon^2}\right).

Remark 1.3. Although property (P3) in Theorem 1.2 is stated with 1−ϵ31-\epsilon^3, the proof of Theorem 1.2 in [17] actually relies only on the order of magnitude of ϵ3\epsilon^3. Consequently, the exact same argument holds under the slightly weaker assumption with 1−2ϵ31-2\epsilon^3, as the precise constant before ϵ3\epsilon^3 is flexible within their proof.

Later in this paper, we consider graphs satisfying properties (P1)-(P3) and apply Theorem 1.2 with p=1+ϵ−δdp = \frac{1+\epsilon-\delta}{d}, where δ:=δ(ϵ)>0\delta:= \delta(\epsilon) > 0 is a small constant in terms of ϵ\epsilon. The aforementioned mild relaxation of property (P3) to 1−2ϵ31-2\epsilon^3 allows us to apply Theorem 1.2 in our setting.

Theorem 1.1 provides, in a sense, a relatively weak sufficient condition on the host graph GG that guarantees the typical emergence of a unique giant component in the random subgraph GpG_p. Our first aim in this paper is to establish another relatively weak set of conditions on a dd-regular nn-vertex host graph GG (where d=ωn(1)d=\omega_n(1)), which are also tight and yield essentially the same conclusion as in Theorem 1.1 on the percolated graph GpG_p.

Theorem 1.2 in turn gives a full characterization of the typical sizes of the components of the percolated graph under supercritical percolation, establishing whp the unique giant component of the ‘correct’ order of γn\gamma n, as well as a large gap between the size of the giant component and the size of all other components, which is O(ϵ−2log⁡n)O(\epsilon^{-2}\log n), achieving essentially the same phenomenon Erdős and Rényi discovered for Gn,pG_{n,p}. Consequently, naturally this phenomenon is sometimes referred to as ERCP — Erdős-Rényi component phenomenon.

The main goal of our paper is to uncover the typical rich combinatorial properties of the giant component in this setting. We begin by establishing relatively strong vertex expansion, which in turn enables us to derive a range of further interesting combinatorial aspects, including the existence of long cycles, large clique minors, and a small diameter. We then investigate the tightness of these results and establish matching statements showing that our bounds are, in several respects, close to optimal. These results also show that the settings considered in Theorem 1 and Theorem 1.1, which do not establish the full ERCP, are not sufficient to guarantee whp the rich combinatorial properties of the giant component that hold under the setting of Theorem 1.2.

The inspiration for this study comes from several known results asserting rich combinatorial properties and aspects of the giant component of the percolated graph for well-known host graphs such as KnK_n, an (n,d,λ)(n,d,\lambda)-graph, or QdQ^d, where nn and d:=d(n)d := d(n) are sufficiently large integers. Let us elaborate on the known results for each host graph individually:

References

  1. [1]M. Ajtai, J. Komlós, and E. Szemerédi. Largest random component of a \(k\)-cube. Combinatorica, 2:1–7, 1982.DOI
  2. [2]N. Alon and V. D. Milman. λ1, isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory, Ser. B, 38:73–88, 1985.DOI
  3. [3]N. Alon and J. H. Spencer. The probabilistic method. Wiley-Intersci. Ser. Discrete Math. Optim. Hoboken, NJ: John Wiley & Sons, 4th edition, 2016.
  4. [4]M. Anastos, S. Diskin, L. Lichev, and M. Zhukovskii. Diameter and mixing time of the giant component in the percolated hypercube. Preprint, arXiv:2510.13348 [math.PR] (2025), 2025.arxiv.org/abs/2510.13348
  5. [5]K. B. Athreya and P. E. Ney. Branching processes, volume 196 of Grundlehren Math. Wiss. Springer, Cham, 1972.
  6. [6]I. Benjamini, G. Kozma, and N. Wormald. The mixing time of the giant component of a random graph. Random Struct. Algorithms, 45(3):383–407, 2014.arxiv.org/abs/math/0610459
  7. [7]A. Beveridge, A. Frieze, and C. McDiarmid. Random minimum length spanning trees in regular graphs. Combinatorica, 18(3):311–333, 1998.DOI
  8. [8]B. Bollobás, Y. Kohayakawa, and T. Łuczak. The evolution of random subgraphs on the cube. Random Struct. Algorithms, 3(1):55–90, 1992.
  9. [9]B. Bollobás and O. Riordan. Percolation. Cambridge: Cambridge University Press, 2006.
  10. [10]G. Brito, I. Dumitriu, and K. D. Harris. Spectral gap in random bipartite biregular graphs and applications. Comb. Probab. Comput., 31(2):229–267, 2022.DOI
  11. [11]S. B. Broadbent and J. M. Hammersley. Percolation processes. I: Crystals and mazes. Proc. Camb. Philos. Soc., 53:629–641, 1957.DOI
  12. [12]F. Chung and L. Lu. The diameter of sparse random graphs. Adv. Appl. Math., 26(4):257–279, 2001.
  13. [13]S. Diskin, J. Erde, M. Kang, and M. Krivelevich. Isoperimetric inequalities and supercritical percolation on high-dimensional graphs. Combinatorica, 44(4):741–784, 2024.arxiv.org/abs/2304.00016
  14. [14]S. Diskin, J. Erde, M. Kang, and M. Krivelevich. Percolation through isoperimetry. Ann. Inst. Henri Poincaré, Probab. Stat., 62(2):900–918, 2026.arxiv.org/abs/2308.10267
  15. [15]S. Diskin and M. Krivelevich. Expansion in supercritical random subgraphs of expanders and its consequences. Random Struct. Algorithms, 65(3):576–600, 2024.arxiv.org/abs/2205.04852
  16. [16]S. Diskin and M. Krivelevich. Components, large and small, are as they should be II: Supercritical percolation on regular graphs of constant degree. Int. Math. Res. Not., 2025(12):11, 2025. Id/No rnaf167.arxiv.org/abs/2408.04599
  17. [17]S. Diskin and M. Krivelevich. Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree. Trans. Am. Math. Soc., 379(10):7251–7270, 2026.arxiv.org/abs/2408.04597
  18. [18]S. Diskin, M. Krivelevich, and I. Markbreit. Supercritical Site Percolation on Regular Graphs. Preprint, arXiv:2603.19038 [math.CO] (2026), 2026.arxiv.org/abs/2603.19038
  19. [19]S. Diskin, L. Lichev, R. Ramanan Radhakrishnan, B. Sudakov, and L. Verhoeven. Anchored isoperimetry in percolation. Preprint, arXiv:2610.38941 [math.PR] (2026), 2026.arxiv.org/abs/2610.38941
  20. [20]R. Durrett. Probability. Theory and examples, volume 49 of Camb. Ser. Stat. Probab. Math. Cambridge: Cambridge University Press, 5th edition, 2019.
  21. [21]J. Erde, M. Kang, and M. Krivelevich. Expansion in supercritical random subgraphs of the hypercube and its consequences. Ann. Probab., 51(1):127–156, 2023.arxiv.org/abs/2111.06752
  22. [22]P. Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., Ser. A, 5:17–61, 1960.
  23. [23]D. Fernholz and V. Ramachandran. The diameter of sparse random graphs. Random Struct. Algorithms, 31(4):482–516, 2007.
  24. [24]N. Fountoulakis and B. A. Reed. The evolution of the mixing rate of a simple random walk on the giant component of a random graph. Random Struct. Algorithms, 33(1):68–86, 2008.DOI
  25. [25]A. Frieze, M. Krivelevich, and R. Martin. The emergence of a giant component in random subgraphs of pseudo-random graphs. Random Struct. Algorithms, 24(1):42–50, 2004.
  26. [26]G. Grimmett. Percolation, volume 321 of Grundlehren Math. Wiss. Berlin: Springer, 2nd edition, 1999.
  27. [27]M. Isaev, T. Makai, B. McKay, P. Prolat, J. Tan, and M. Zhukovskii. Canonical labelling of random regular graphs. Preprint, arXiv:2602.17567 [math.CO] (2026), 2026.arxiv.org/abs/2602.17567
  28. [28]S. Janson, T. Łuczak, and A. Ruciński. Random graphs. Wiley-Intersci. Ser. Discrete Math. Optim. New York, NY: Wiley, 2000.
  29. [29]K.-I. Kawarabayashi and B. Reed. A separator theorem in minor-closed classes. In Proceedings of the 51st annual IEEE symposium on foundations of computer science – FOCS 2010, Las Vegas, NV, USA, October 23–26, 2010, pages 153–162. Los Alamitos, CA: IEEE Computer Society, 2010.DOI
  30. [30]H. Kesten. Percolation theory for mathematicians, volume 2 of Prog. Probab. Stat. Birkhäuser, Boston, MA, 1982.
  31. [31]M. Krivelevich. Expanders – how to find them, and what to find in them. In Surveys in combinatorics 2019. Papers based on the 27th British combinatorial conference, University of Birmingham, Birmingham, UK, July 29 – August 2, 2019, pages 115–142. Cambridge: Cambridge University Press, 2019.arxiv.org/abs/1812.11562
  32. [32]M. Krivelevich. Long cycles in locally expanding graphs, with applications. Combinatorica, 39(1):135–151, 2019.arxiv.org/abs/1609.06851
  33. [33]M. Krivelevich. Component sizes in the supercritical percolation on the binary cube. Preprint, arXiv:2311.07210 [math.CO], 2023.arxiv.org/abs/2311.07210
  34. [34]M. Krivelevich and B. Sudakov. Pseudo-random graphs. In More sets, graphs and numbers. A salute to Vera Sós and András Hajnal, pages 199–262. Berlin: Springer. Budapest: János Bolyai Mathematical Society, 2006.DOI
  35. [35]O. Riordan and N. Wormald. The diameter of sparse random graphs. Comb. Probab. Comput., 19(5-6):835–926, 2010.
  36. [36]A. Sarid. The spectral gap of random regular graphs. Random Struct. Algorithms, 63(2):557–587, 2023.arxiv.org/abs/2201.02015
  37. [37]K. Tikhomirov and P. Youssef. The spectral gap of dense random regular graphs. Ann. Probab., 47(1):362–419, 2019.arxiv.org/abs/1610.01765

Paper details

vlnc:W_qsx5znpy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI tools

View statement
Looking for related papers…
Contents