Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree

Basic Information

• Paper ID: 2408.04597
• Title: Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree
• Authors: Sahar Diskin, Michael Krivelevich (Tel Aviv University)
• Classification: math.CO (Combinatorics), math.PR (Probability Theory)
• Submission Date: August 2024; Revised November 2025
• Paper Link: https://arxiv.org/abs/2408.04597

Abstract

This paper provides sufficient conditions for d-regular graphs G with growing degree to exhibit phase transition phenomena similar to classical Erdős-Rényi random graphs G(n,p) in their random subgraphs Gp when p·d≈1. For an n-vertex d-regular graph with d=ω(1) and p=(1+ε)/d, if G satisfies mild global edge expansion and good expansion control on small sets, then typically Gp contains a unique giant connected component of order y(ε)n (where y(ε) is the survival probability of a Galton-Watson tree with parameter Po(1+ε)), while all other connected components have order O(log n/ε²). The authors also prove this result is tight: if the expansion control on small sets is weakened, there exist d-regular graphs where the second-largest connected component has order Ω(d log(n/d))=ω(log n).

Research Background and Motivation

Research Problem

This paper studies supercritical percolation on regular graphs: given a host graph G and probability p∈0,1, obtain a percolation random subgraph Gp by independently retaining each edge of G with probability p. The core question is: which regular graphs G exhibit the Erdős-Rényi connected component phenomenon (ERCP), namely, at the supercritical stage p=(1+ε)/d, a unique giant connected component appears with all other components being logarithmic in order?

Problem Significance

1. Unified understanding of phase transitions: Erdős-Rényi proved in 1960 the phase transition phenomenon in classical random graphs G(n,p) when p·n≈1. This phenomenon has been independently proven on various special graphs (complete graphs, hypercubes, pseudorandom graphs, etc.), but with different proof techniques. This paper aims to provide a unified framework.
2. Characterizing universality classes: Identifying which graph structural properties determine the appearance of ERCP helps understand universality in percolation theory.
3. Theoretical completeness: Since certain graphs (e.g., disjoint unions of cliques) do not exhibit ERCP, precise boundary conditions must be characterized.

Limitations of Existing Methods

• Special structure dependence: The hypercube proof relies on its product structure and Harper isoperimetric inequalities; the pseudorandom graph proof relies on expansion mixing lemmas
• Scattered proof techniques: Different graph classes require completely different proof techniques, lacking unified perspective
• Unclear conditions: For general regular graphs, which expansion properties suffice to guarantee ERCP remains unclear
• Tightness unknown: Whether existing sufficient conditions are necessary remains undetermined

Research Motivation

The authors aim to characterize ERCP through pure expansion properties (rather than special structures), provide a unified proof framework, and prove tightness of conditions through counterexample constructions.

Core Contributions

1. Unified sufficient condition framework: Proposes sufficient conditions based on expansion properties (Theorem 1), covering cases with d≥log^α n, uniformly proving ERCP for complete graphs, hypercubes, d-regular expander graphs, random d-regular graphs, and other graph classes.
2. Three main theorems:
   • Theorem 1 (d≥log^α n): Requires mild global edge expansion (P1), small set vertex expansion (P2), and small set near-optimal edge expansion (P3)
   • Theorem 3 (d≥10log n/ε): Removes (P2), requiring only (P1) and strengthened (P2')
   • Theorem 4 (d=ω(1)): Removes (P2) and degree lower bound, but requires strengthened (P3) to larger sets
3. Tightness result (Theorem 2): Constructs counterexamples proving that small set expansion condition (P3) is tight in constant factor sense—if near-optimal edge expansion is required only for sets of size ≤εd log(n/d)/(100c₁), there exist graphs where the second-largest component is Ω(d log(n/d)).
4. Novel technical innovations:
   • Proving large connected components are "everywhere dense"
   • Double-exposure/sprinkling techniques
   • Gap lemma for connected component sizes
5. Unified proof paradigm: Provides pure expansion-based proofs independent of special structures (such as product structure or pseudorandomness).

Method Details

Task Definition

Input: d-regular graph G=(V,E), n=|V|, degree d=ω(1), percolation probability p=(1+ε)/d (ε>0 small constant)
Output: Prove that Gp has with high probability (whp) the following properties:

• There exists a unique giant component L₁ with |L₁|=(1+o(1))y(ε)n
• All other components have order O(log n/ε²)

where y(ε)∈(0,1) is the unique solution to y=1-exp{-(1+ε)y}, i.e., the survival probability of a Po(1+ε) branching process.

Core Assumption Conditions

Theorem 1 requires G to satisfy:

(P1) Global edge expansion: For all U⊆V, |U|≤n/2, we have e(U,U^C)≥c₁|U| (c₁>0 constant)

(P2) Small set vertex expansion: For all U⊆V, |U|≤c₂log n, we have |N(U)|≥c₃d|U| (c₂,c₃>0 constants)

(P3) Small set near-optimal edge expansion: For all U⊆V, |U|≤Cd log n, we have e(U,U^C)≥(1-ε³)d|U| (C sufficiently large constant)

Proof Architecture

Overall Strategy

Employs double-exposure technique: Set p₂=ε³/d, choose p₁ such that (1-p₁)(1-p₂)=1-p, so Gp and Gp₁∪Gp₂ have the same distribution. The proof consists of four main steps:

Step 1: Large connected components are everywhere dense (Section 3.1)

• Define "large component": VL(H)={v: |C_H(v)|≥7log n/ε²}
• Goal: Prove whp each vertex v has Ω(d log n) vertices from VL(Gp) within distance 1+log_d log n

Step 2: Connected component size gap (Lemma 3.4)

• Prove whp no component has order in 7log n/ε², Cd log n
• Requires delicate counting and probability estimates

Step 3: Large component merging (Section 3.2, Lemma 3.5)

• Prove whp all large components in Gp₁ merge into a single component after sprinkling Gp₂
• Key: Construct sufficiently many vertex-disjoint paths

Step 4: Volume concentration (Section 3.3, Lemma 3.8)

• Prove the total number of vertices in the large component concentrates near y(ε)n

Technical Details

Lemma 3.1: Fixed set component behavior

For sets S with |S|=c'd log n (c'=c₂c₃^(1+1/α)), prove:

• (a) No U⊆S exists such that ∪{u∈U}C(u) has order in c'd log n/ε³, 2c'd log n/ε³
• (b) No large subset U⊆S (|U|≥(1-ε²)c'd log n) exists such that ∪{u∈U}C(u) has order ≤Cd log n

Proof technique:

• Use forest counting (Lemma 2.3): At most (ed)^(k-1) trees on k vertices
• Utilize (P3): Boundary has at least (1-ε³)kd edges that must not be in Gp
• Probability estimate: (edp)^(k-1)(1-p)^((1-ε³)kd) ≤ exp{-ε²k/4}

Lemma 3.3: Everywhere density

Prove whp each v∈V has ≥ε²c'd log n vertices from VL(Gp) within distance ≤1+log_d log n.

Proof path:

1. By (P2), |B_G(v, log_d log n)|≥c₂c₃^(log_d log n) log n≥c₂c₃^(1/α) log n
2. Applying (P2) again, |B_G(v, 1+log_d log n)|≥c₃d·c₂c₃^(1/α) log n=c'd log n
3. For Sv⊆B_G(v, 1+log_d log n), |Sv|=c'd log n, by Corollary 3.2 we get |Sv∩VL(Gp)|≥ε²c'd log n
4. Union bound over all v completes the proof

Lemma 3.5: Large component merging

Let W=VL(Gp₁). For any partition of W respecting component structure W=A⊔B, we need to find a path from A to B in Gp₂.

Construction process (assuming |A|≤|B|):

1. Define A₀=A, B₀=B, recursively construct Ai, Bi (i=1,...,r, r=1+log_d log n):
   • Ai contains vertices with ≥ε²c'd/(5r) neighbors to Ai₋₁
   • Bi defined similarly
2. Claim 3.6: V=A'⊔B', where A'=∪Ai, B'=∪Bi
3. Expose edges from A' to B' in Gp₂, by (P1) and Lemma 2.4 obtain matching M, |M|≥ε⁶c₁|A|/d
4. Recursively extend endpoints of M through paths in Gp₂ to A₀=A
5. Similarly extend from B' to B, finally connecting A and B

Probability estimate:

• Each step failure probability ≤exp{-ε⁸c'|Mi,A'|/(5r)}
• Final path count ≥(ε⁸c'c₁/(5r))^(r+1)|A|/d
• Partition count ≤n^(|A|/(Cd log n))
• Union bound: ≤2n·exp{-(ε⁸c'c₁/(7r))^(2r+1)C log n}=o(1)

Lemma 3.4: Gap lemma

Prove whp no connected set K exists with |K|∈7log n/ε², Cd log n and E_{Gp₁}(K,K^C)=∅.

Key estimate:

• Tree T on k vertices: at most n(ed)^(k-1) choices
• By (P3): e(V(T), V\V(T))≥(1-ε³)kd
• Pall edges in Gp and boundary edges not in Gp₁≤n(edp)^(k-1)exp{-p₁(1-ε³)dk}
• ≤n exp{k(1+log(1+ε)-(1+ε-3ε³))}≤n exp{-ε²k/3}=o(1/n)

Lemma 3.8: Volume concentration

Let W be the set of vertices in connected components of Gp with order ≥14log n/ε².

Expectation calculation:

• Fix v, explore via BFS, dominated by Bin(d,p) branching process
• P|C_(v)|≥14log n/ε²≤(1+o(1))y(ε) (upper bound)
• Modify BFS to stop at √d steps, dominated by Bin(d-√d,p)
• P|C_(v)|≥√d≥(1-o(1))y(ε) (lower bound)
• By Lemma 3.7, EW=(1+o(1))y(ε)n

Concentration:

• Edge exposure martingale, each edge changes |W| by at most 28log n/ε²
• By Azuma-Hoeffding (Lemma 2.2): P||W|-EW|≥n^(2/3)≤2exp{-n^(4/3)/(O(ndp·log²n/ε⁴))}=o(1)

Technical Innovation Points

1. New proof of everywhere density: Independent of product structure, purely through ball growth and vertex expansion
2. Recursive path construction strategy: Under sprinkling probability p₂=ε³/d, path length r=O(log_d log n) may have small appearance probability p₂^r, cleverly resolved through recursive matching and set construction Ai
3. Precise constants in gap lemma: The gap from 7log n/ε² to Cd log n is crucial for subsequent arguments, constant choices intimately related to p₂=ε³/d (connected to Taylor expansion of log(1+x))
4. Tightness construction (Theorem 2): Via c'₁-regular graph H (satisfying global expansion) plus (n',d',λ')-graphs within color classes, isolating color classes in Gp

Experimental Setup

This is a pure theoretical mathematics paper containing no computational experiments. All results are rigorous mathematical proofs.

Application Examples (as "verification")

The paper demonstrates how Theorem 1 and its variants recover known results:

1. Complete graph Kn: Recovers Erdős-Rényi classical result via Theorem 3
2. Pseudorandom (n,d,λ)-graphs (λ=o(d)): Expansion mixing lemma verifies (P3), Theorem 3/4 applies
3. Random d-regular graphs: Whp are (n,d,Ω(√d))-graphs satisfying all conditions
4. Hypercube Qd: Harper isoperimetric inequality gives e(U,U^C)≥|U|(d-log₂|U|), satisfying (P1) and (P3); small set vertex expansion follows from Harper results
5. High-dimensional product graphs: Satisfy conditions via Harper-type inequalities
6. Duplicube: Satisfies Harper-type inequalities, answers Benjamini-Zhukovskii question

Experimental Results

Summary of Main Results

Theorem 1 (polylogarithmic degree): d≥log^α n implies (P1)+(P2)+(P3) ⇒ ERCP

Theorem 3 (high degree): d≥10log n/ε implies (P1)+(P2') ⇒ ERCP, where (P2') requires e(U,U^C)≥(1-ε³)d|U| for |U|≤min{Cd log n, ε⁵n}

Theorem 4 (low degree): d=ω(1) with (P1)+strong (P3) (|U|≤(d log n)^(5log log n)) ⇒ ERCP

Theorem 2 (tightness): There exist d-regular graphs G satisfying:

• (P1) holds
• For |U|≤log(n/d)/(40c₁), |N(U)|≥d|U|
• For |U|≤ε³d log(n/d)/(100c₁), e(U,U^C)≥(1-ε³)d|U|
• But whp second-largest component ≥εd log(n/d)/(30c₁)=ω(log n)

Necessity Analysis of Conditions

• Necessity of (P1): 17 proved global expansion too weak may yield giant component of order o(n)
• Tightness of (P3): Theorem 2 proves tightness in constant factor sense
• Necessity of (P2): Open problem (Problem 6.1), but Theorems 3 and 4 show removability in some cases

Comparison with Existing Results

Related Work

Historical Development

1. Erdős-Rényi (1960): Established phase transition theory for G(n,p)
2. Broadbent-Hammersley (1957): Introduced percolation model
3. Ajtai-Komlós-Szemerédi (1982): Proved ERCP for hypercubes, first used "everywhere dense" strategy
4. Bollobás-Kohayakawa-Łuczak (1992): Alternative hypercube proof

Constant Degree Cases

• Alon-Benjamini-Stacey (2004): High girth expanders have giant components
• Krivelevich-Lubetzky-Sudakov (2020): Giant component has order y(ε)n, but second-largest can reach |V|^a (any a<1)
• Diskin-Krivelevich (2025, 18): Sister paper of this work, handles constant degree case

Degree Sequences and Randomness

• Van der Hofstad (2023, 32): Universal bounds for giant components with given degree sequences
• Lichev-Mitsche-Perarnau (2024): Threshold characterization for degree sequence random graphs
• Alimohammadi-Borgs-Saberi (2023): Large set expansion determines local structure and giant components

Paper Positioning

This is the first work providing unified sufficient-necessary condition characterization based on pure expansion properties for regular graphs with growing degree, with tightness proof.

Conclusions and Discussion

Main Conclusions

1. For d-regular graphs with growing degree, mild global edge expansion plus good expansion control on small sets (size O(d log n)) suffice to guarantee ERCP
2. Small set expansion conditions are tight in constant factor sense
3. Provides unified proof framework independent of special structures (product, pseudorandomness, etc.)

Limitations

1. Necessity of vertex expansion (P2) unresolved: Problem 6.1 asks whether graphs exist satisfying (P1) and (P3) but not exhibiting ERCP?
2. Constant dependence: Constants in theorems depend on ε, c₁, c₂, c₃, α; specific dependencies not fully optimized
3. Quantitative tightness: Theorem 2 gives qualitative tightness, but precise constant matching admits improvement
4. Degree range: d=ω(1) but d=o(log n) requires Theorem 4's strong assumptions

Future Directions

1. Problem 6.1: Characterize necessity of (P2)
2. Quantitative trade-off between global and local expansion: Paper indicates stronger (P1) allows weaker (P3); precise characterization of this trade-off
3. Other graph classes: Can permutahedron 13 be handled by similar framework?
4. Algorithmic applications: Can expansion conditions be used for efficient sampling or approximation algorithms?
5. Generalization to non-regular graphs: 13,15,30 show irregular graphs may not exhibit ERCP; can more refined conditions be given?

In-Depth Evaluation

Strengths

1. Theoretical depth:
   • Provides unified mathematical framework avoiding case-by-case analysis
   • Tightness result (Theorem 2) proves conditions nearly optimal
   • Technical innovations (everywhere density, recursive path construction) have independent value
2. Proof techniques:
   • Elegant application of double-exposure technique (p₂=ε³/d choice related to Taylor expansion)
   • Precise constant control in gap lemma
   • Careful probability estimates (e.g., forest counting in Lemma 3.1)
3. Broad applicability:
   • Recovers multiple classical results (complete graphs, hypercubes, pseudorandom graphs)
   • Resolves open problems (duplicube ERCP)
   • Provides explicit conditions for random d-regular graphs
4. Writing clarity:
   • Clear structure: background → main results → proofs → tightness → applications
   • Explicit proof strategy: four-step approach easy to follow
   • Well-developed notation system

Weaknesses

1. Condition complexity:
   • Interaction of three properties (P1)(P2)(P3) not sufficiently intuitive
   • Interdependence of constants c₁, c₂, c₃, C not explicitly given
   • Verifying whether graphs satisfy conditions may be difficult in practice
2. Open problems:
   • Necessity of (P2) unresolved, theoretical picture incomplete
   • Theorem 2 construction proves tightness but constant matching imprecise
3. Technical limitations:
   • For d=ω(1) but d=o(log n) requires Theorem 4's strong assumptions (set size to (d log n)^(5log log n))
   • Proof technique highly dependent on regularity assumption, generalization to non-regular graphs difficult
4. Application guidance:
   • How to efficiently verify (P2)(P3) for given graphs?
   • Lacks algorithmic or computational discussion

Impact

1. Contribution to field:
   • Provides new unified perspective for percolation theory
   • May inspire research on other random graph models
   • Sister paper 18 extends to constant degree, forming complete theory
2. Practical value:
   • Provides theoretical foundation for network robustness analysis
   • Can be used to design networks with good percolation properties
   • Expansion properties widely applicable in computer science
3. Reproducibility:
   • Pure theoretical proofs, completely reproducible
   • Proof techniques detailed, key lemmas fully proved
   • Theorem 2 construction can be practically implemented

Applicable Scenarios

1. Theoretical research:
   • Random graph theory
   • Percolation theory
   • Graph expansion properties
   • Universality class research in phase transitions
2. Network science:
   • Network robustness analysis (node/edge failures)
   • Epidemic spreading models (percolation corresponds to spreading)
   • Social network connectivity analysis
3. Combinatorial optimization:
   • Graph partitioning problems
   • Expander graph construction
   • Randomized algorithm design

Key References

1. 20 Erdős-Rényi (1960): Foundational work on random graph phase transitions
2. 1 Ajtai-Komlós-Szemerédi (1982): Hypercube percolation, first "everywhere dense" use
3. 22 Frieze-Krivelevich-Martin (2004): ERCP for pseudorandom graphs
4. 29 Krivelevich-Lubetzky-Sudakov (2020): Giant components in high girth expanders
5. 32 Van der Hofstad (2023): Universal bounds for giant components
6. 17 Diskin et al. (2024): Authors' prior work on isoperimetric inequalities and percolation
7. 18 Diskin-Krivelevich (2025): Sister paper (constant degree case)

Overall Assessment: This is a high-quality theoretical mathematics paper providing profound unified framework for percolation theory. Technically rigorous and innovative, results broadly applicable, tightness analysis completes theoretical picture. Main regret is unresolved necessity of (P2), but this leaves valuable direction for future research. This work has significant impact on combinatorics and probability theory, with potential connections to network science.