The supercritical giant component of G(n, p) (EPI-3) #
M. Krivelevich and B. Sudakov, The phase transition in random graphs: a simple proof, Random Structures & Algorithms 43 (2013) 131–138, arXiv:1201.6529.
The random graph G(n, p) is bond percolation on the complete graph: perc ⊤ ω with i.i.d.
Bernoulli(p) edge coins ω ~ coins p on a vertex type V with n = |V| (Epidemics.ReedFrost,
EPI-1). The edge probability p = (1 + ε) / n is written p * n = 1 + ε, which excludes n = 0.
The paper's "with high probability" is made quantitative as "with probability at least
1 - C / n", and its "ε > 0 a small enough constant" as ∃ ε₀ > 0, ∀ ε ∈ (0, ε₀].
exists_long_path: Theorem 1, part 2 (a path of length≥ ε² n / 5).exists_giant_component: Theorem 2 (a component with≥ ε n / 2vertices).exists_linear_component: the supercritical half of the Erdős–Rényi phase transition, as quoted in the paper's abstract, for everyε > 0.
The proof is the paper's: run the depth-first search of Epidemics.GiantDFS on perc ⊤ ω for
N₀ = ⌊θ n²⌋ queries (θ = ε / 2 in the paper). By the principle of deferred decisions
(prob_queryAnswers) its answers are i.i.d. Bernoulli(p), so by the Chernoff bounds of FND-3
(Lemma 1, part 2, prob_count_take_far, and its windowed form prob_not_good_le) the numbers of
positive answers are close to their means; then the deterministic properties of the search
(Epidemics.GiantAnalysis) force a long stack U (a path) and an epoch spanning ε n / 2
vertices. Both arguments are first proved for general parameters (core_path,
core_component), whose conditions are the paper's inequalities; the theorems follow by choosing
the parameters, and the version for every ε > 0 by taking θ small in terms of ε (instead of
θ = ε / 2).
The deterministic part of the proof of Theorem 2: on typical answers (Good), and under the
inequalities of the paper (hi: |S ∪ U| < n/3 at time N₀; hcontr: no epoch starts after
t₁; hc: enough positive answers after t₁), the current epoch of the search on perc ⊤ ω
lies in a component with at least c n vertices.
The paper's inequalities, for large n #
|S ∪ U| < n/3 at time N₀ (proof of Theorem 1): N₀ < (n/3 - 1 - (1 + δ) N₀ p)(2n - 5)/3
when N₀ ≤ θ n², N₀ p ≤ θ λ n and n is large.
Enough positive answers after t₁ (proof of Theorem 2):
c n ≤ (1 - δ) N₀ p - (1 + δ) t₁ p.
Theorem 2, for general parameters (Krivelevich–Sudakov, proof of Theorem 2): let
p n = λ, N₀ = ⌊θ n²⌋ queries, the window t₁ = ⌊η n²⌋ and the relative deviation δ, such that
(i) θ < (2/3) (1/3 - (1 + δ) λ θ) (so |S ∪ U| < n/3 at time N₀), (ii)
(1 - δ) λ (1 - λ θ) > 1 (so no epoch starts in [t₁, N₀]), and c < ((1 - δ) θ - (1 + δ) η) λ
(the positive answers in [t₁, N₀]). Then G(n, p) has a component with at least c n vertices
with probability at least 1 - C / n.
N₀ < (Xlo - (ℓ n + 1)) (n - Xlo) (proof of Theorem 1), for large n.
The deterministic part of the proof of Theorem 1, part 2: on typical answers, and under the
inequalities of the paper, the stack of the search on perc ⊤ ω at time N₀ is a path with at
least ℓ n edges.
Theorem 1, part 2, for general parameters (Krivelevich–Sudakov, proof of Theorem 1): let
p n = λ, N₀ = ⌊θ n²⌋ queries and the relative deviation δ such that (i)
θ < (2/3)(1/3 - (1 + δ) λ θ) (so |S ∪ U| < n/3 at time N₀), and (ii)
θ < ((1 - δ) λ θ - ℓ)(1 - (1 - δ) λ θ), θ < (2/3)(1/3 - ℓ) (so |U| > ℓ n at time N₀).
Then G(n, p) has a path with at least ℓ n edges with probability at least 1 - C / n.
Long path (Krivelevich–Sudakov, Theorem 1, part 2; Ajtai, Komlós and Szemerédi): for every
small enough ε > 0 there is C such that, for p = (1 + ε) / n, the random graph G(n, p)
(bond percolation perc ⊤ ω on the complete graph on n vertices, with i.i.d. Bernoulli(p)
edge coins ω) contains a path of length (number of edges) at least ε² n / 5 with probability
at least 1 - C / n.
Giant component (Krivelevich–Sudakov, Theorem 2): for every small enough ε > 0 there is
C such that, for p = (1 + ε) / n, the random graph G(n, p) (bond percolation perc ⊤ ω on
the complete graph on n vertices) has a connected component with at least ε n / 2 vertices with
probability at least 1 - C / n.
Supercritical phase (Erdős and Rényi, as stated in the abstract of Krivelevich–Sudakov):
for every ε > 0 there are c > 0 and C such that, for p = (1 + ε) / n, the random graph
G(n, p) has a connected component with at least c n vertices with probability at least
1 - C / n.