Source-linked AI summary
The phase transition in random graphs - a simple proof
Michael Krivelevich, Benny Sudakov
TL;DR
The paper addresses the Erdős–Rényi phase transition and seeks a simple, self-contained proof of its classical result and the Ajtai–Komlós–Szemerédi result. It uses depth-first search and extends the proof strategy to other settings, including a result on large components.
Problem
The paper seeks a simple, self-contained proof of the Erdős–Rényi phase-transition result and the Ajtai–Komlós–Szemerédi result.
Source: §1 · p. 2Method
The proof runs depth-first search on the random graph, and the paper applies essentially the same argument to random digraphs.
Source: §2 · p. 2Results
With p=(1+ε)/n, G(n,p) has with high probability a connected component containing at least εn vertices.
Source: §3 · p. 5Takeaways & Limitations
The proof strategy also yields a directed path and a directed cycle of length Θ(ε^2)n in random digraphs.
Source: §3 · p. 6The pseudorandom-graph extension assumes an (n,d,λ)-graph with λ=o(d).
Source: §3 · p. 7
Abstract
from arXiv · showhide
The classical result of Erdos and Renyi shows that the random graph G(n,p) experiences sharp phase transition around p=1/n - for any \epsilon>0 and p=(1-\epsilon)/n, all connected components of G(n,p) are typically of size O(log n), while for p=(1+\epsilon)/n, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime p=(1+\epsilon)/n, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games.
1 Introduction
The Erdős–Rényi random graph has a phase transition around p=1/n: below it, components are logarithmic in size, while above it a linear-size component emerges. This paper presents a simple, self-contained proof of that result and the known linear-path strengthening.
1 Introduction
- Below p=1/n, all connected components are at most logarithmic in n; above it, a linear-size component emerges with high probability.The linear-size component is usually called the giant component.Source: §1 · p. 1
- The Erdős–Rényi result has several proofs, including counting arguments and approaches using branching processes.The paper notes that the evolution of random graphs is now well understood.Source: §1 · p. 2
- Ajtai, Komlós and Szemerédi proved that in the supercritical regime the random graph typically contains a path of length linear in n.This strengthens the giant-component result by establishing a long path.Source: §1 · p. 2
- The note gives a simple, self-contained proof of the Erdős–Rényi result and the Ajtai, Komlós and Szemerédi result.The authors prioritize simplicity over deriving the best possible absolute constants.Source: §1 · p. 2
2 Main result
The proof couples depth-first search (DFS) on G(n,p) to independent Bernoulli query outcomes. Bounds on runs of positive answers then yield the subcritical component bound and, in the supercritical regime, a linear-length path.
2 Main result
- DFS uses sets S, T and U for completed, unvisited and active vertices; U is a stack that always spans a path.Each round moves one vertex between sets, and no edges remain possible between the current S and T because those pairs have been queried.Source: §2 · pp. 2–3
- A DFS epoch begins when a component's first vertex enters an empty U and ends when U empties again.Each epoch corresponds to one connected component.Source: §2 · pp. 2–3
- The proof feeds DFS independent Bernoulli(p) answers, so the query sequence has the random-graph distribution and positive answers move new vertices into U.The number of positive answers bounds the sizes of S∪U and U, linking the random sequence to component and path structure.Source: §2 · p. 3
- The lemma bounds the number of positive answers in any interval of length kn and also controls the total number of positives among the first N0 queries.These two properties support the small-component contradiction and the supercritical stack-size argument, respectively.Source: §2 · pp. 3–4
- With high probability, all connected components of G have size at most 7ε^-2 ln n vertices; a larger one would produce an interval of length at most kn with at least k positive answers.Such an interval contradicts Property 1 of Lemma 1.Source: §2 · pp. 3–4
- The passage states that G contains, with high probability, a path of length at least ε²n; the excerpt does not provide a supported probability parameter.Source: §2 · p. 4
3 Discussion
The discussion extends the DFS-based argument beyond the basic random-graph path result, including to digraphs, random subgraphs, and positional games. It also gives a giant-component bound and discusses how the results relate to cycle lengths and the critical threshold.
3 Discussion
- Theorem 1’s linear-length path result holds with exponentially high probability in the supercritical regime.The discussion also states that the ε-dependencies in both parts of Theorem 1 are of the correct order of magnitude.Source: §3 · p. 5
- The discussion reports a known subcritical largest-component size of Θ(ε^−2) log n and a supercritical longest-cycle length of Θ(ε²)n.The sprinkling argument relates a linear-length path to a nearly as long cycle after adding edges.Source: §3 · p. 5
- The argument remains valid for ε tending to zero, down to ε≫n^−1/3 log^1/3 n, nearly the critical window ε=Θ(n^−1/3).Sprinkling further edges with probability p′=o(n^−1) turns a linear path into a cycle of length at least (α−o(1))n when the original path has length αn.Source: §3 · p. 5
- For sufficiently small constant ε>0, the discussion proves that G(n,p) has a component of at least εn vertices.The proof uses DFS; its stack remains nonempty over the specified query interval, so the vertices added during that interval belong to one component.Source: §3 · pp. 5–6
- For p=(1+ε)/n, a random digraph has a directed path and cycle of length Θ(ε²)n, while random subgraphs of minimum-degree graphs have paths of length at least ε²n.The digraph result recovers Karp’s classical result.Source: §3 · pp. 6–7
- For an (n,d,λ)-graph with λ=o(d), its random subgraph at p=(1+ε)/d contains a path of length Θ(ε²)n.The edge-distribution estimate also supports sprinkling to close a long path into a long cycle.Source: §3 · pp. 7–8
- In L(n,b) with b=(1−ε)n, Maker can create a path of length Θ(ε²)n.The discussion contrasts paths with cycles: when Maker finishes with at most n−1 edges, Breaker can force a tree, and creating any cycle requires b≥(1+o(1))n/2.Source: §3 · p. 8