The binomial Random Graph - Probabilistic Combinatorics

10 The binomial Random Graph

G (n, p)

We are interested in sliding $p$ from $0$ to $1$ . At what point do certain structures emerge?

Questions:

When do we expect to see a triangle?
When do we expect $G (n, p)$ to be connected?
When does $G (n, p)$ have a component that spans $Ω (n)$ vertices?
When does $G (n, p)$ have a Hamiltonian cycle?

Fix some $H$ . When do we expect $G \supset H$ , $G \sim G (n, p)$ ?

Definition 10.1 (m). For $H$ a graph, define

m (H) = \max {\frac{e (F)}{| F |} : F \subset H, | F | \geq 1} .

Example. $H = K_{3}$ , $m (K_{3}) = 1$ .

Theorem 10.2 (Bollobás, 80s). Assuming that:

$H$ a graph
$G \sim G (n, p)$

Then

\lim_{n \to \infty} ℙ (G \supset H) = {\begin{matrix} 1 & when p n^{\frac{1}{m (H)}} \to \infty \\ 0 & when p n^{\frac{1}{m (H)}} \to 0 \end{matrix}

Proof. We use a second moment argument. Let

X # of copies of H in G,

where $G \sim G (n, p)$ . Then

𝔼 X = Θ (n^{| H |} \cdot p^{e (H)}) .

Since $Var X = 𝔼 X^{2} - {(𝔼 X)}^{2}$ , we will compute $𝔼 X^{2}$ .

\begin{array}{l} 𝔼 X^{2} & = {(\sum_{H} 𝟙_{H \subset G})}^{2} \\ = \sum_{H_{1}, H_{2}} ℙ (H_{1} \subset G, H_{2} \subset G) \\ \leq {(𝔼 X)}^{2} + (𝔼 X) + \sum_{\emptyset \neq F ⊊ H} \sum_{\begin{array}{c} H_{1}, H_{2} \\ H_{1} \cap H_{2} = F \end{array}} p^{2 e (H) - e (F)} \\ \leq {(𝔼 X)}^{2} + (𝔼 X) + C \sum_{\emptyset F ⊊ H} n^{2 | H | - | F |} p^{2 e (H) - e (F)} \\ \leq {(𝔼 X)}^{2} + (𝔼 X) + C n^{2 | H |} p^{2 e (H)} \sum_{F} \frac{1}{n^{| F |} p^{e (F)}} \end{array}

Now note

{(\frac{1}{n p^{\frac{e (F)}{| F |}}})}^{| F |} \leq {(\frac{1}{n p^{m (H)}})}^{| F |} \to 0

when $p n^{\frac{1}{m (H)}} \to \infty$ . So

𝔼 X^{2} = (1 + o (1)) {(𝔼 X)}^{2} + 𝔼 X . □

10.1 The Giant Component

Proposition 10.3. Let $𝜀 > 0$ . If $G \sim G (n, p)$ , then

\lim_{n \to \infty} ℙ (G is connected) = {\begin{matrix} 1 & p \geq (1 + 𝜀) \frac{\log n}{n} \\ 0 & p \leq (1 - 𝜀) \frac{\log n}{n} \end{matrix}

and

\lim_{n \to \infty} ℙ (G \supset H) = {\begin{matrix} 1 & p^{m (H)} n ≫ 1 \\ 0 & p^{m (H)} n ≪ 1 \end{matrix}

Remark. This “threshold” for $p$ looks different from what we saw from the threshold of containing a given $H$ – it has a “sharp” jump from $0$ to $1$ .

Definition 10.4 (c1). For a graph $G$ , let

c_{1} (G) = # vertices in the largest connected component .

Theorem 10.5 (Erdös-Renyi). Let $𝜀 > 0$ . If $G \sim G (n, p)$ then

c_{1} (G) = {\begin{matrix} O_{𝜀} (\log n) & if p \leq \frac{1 - 𝜀}{n} \\ Ω_{𝜀} (n) & if p \geq \frac{1 + 𝜀}{n} \end{matrix}

Definition 10.6 (DFS-sequence). Let $G$ be a graph. I define the DFS-sequence from $G$

X_{1}, X_{2}, X_{3}, X_{4}, \dots \in {0, 1}

as follows. We process the graph using a Depth first search. We also imagine $V (G)$ have an order on them. As we saw before, we maintain a partition $V (G) = A \cup B \cup P$ where $P$ is a path.

We start with $A = V (G)$ , $B = \emptyset$ , $P = \emptyset$ . We then repeat the following:

(1) If $P$ is empty, move a vertex from $A$ to $P$ .
(2) If $P$ is not empty, let $x$ be the last vertex of $P$ , and now query the edges from $x$ to $A$ in order until I get a “yes”.
Now move the neighbour of $v$ to the end of $P$ and append to our DFS sequence the outcomes of the queries.

If $v$ has no neighbour in $A$ , then move $v$ to $B$ and append all the “no” outcomes to the DFS-sequence.

Note.

We don’t query an edge more than once.
We don’t query all edges in $G$ . But if $u v \in G$ is not queried, then $u, v$ are in the same component.

Lemma 10.7. Let $G$ be a graph on $n$ vertices, with a component of size $k$ . Let $X_{1}, X_{2}, \dots$ be the DFS-sequence. Then there exists $t$ such that

\sum_{i = t}^{t + k n} X_{i} \geq k - 1 .

Proof. Let $C = {x_{1}, \dots, x_{k}}$ be a component of size $k$ , $C \subset V (G)$ . Say we first encounter $x_{1}$ at time $t$ . From time $t$ up until $C \subset B$ , we only query edges incident to $v \in C$ . So we make at most

(\binom{k}{2}) + k (n - k) \leq k n

exposures. And during this time we must have seen $\geq k - 1$ $1$ ’s since $V (C)$ is a component. □

Lemma 10.8. For $𝜀 > 0$ , let $p = \frac{1 - 𝜀}{n}$ . Then if $G \sim G (n, p)$ ,

c_{1} (G) \leq \frac{8 \log n}{𝜀^{2}} .

Proof. Let $X_{1}, X_{2}, \dots$ be the corresponding DFS-sequence. Since we never query an edge more than once in the definition of the DFS-sequence, we have that $X_{1}, X_{2}, X_{3}, \dots$ is a sequence of iid random variables, with each being $X_{i} \sim Ber (p)$ .

So let

Y_{t} = \sum_{i = t}^{t + k n} X_{i}

for $t \leq n^{2}$ .

We will use Chernoof’s inequality:

Let $X \sim Bin (n, p)$ defined by

ℙ (X = k) = (\binom{n}{k}) p^{k} {(1 - p)}^{n - k} .

Then for $0 \leq t \leq p n$ ,

ℙ (| X - p n | \geq t) \leq 2 \exp (- \frac{t^{2}}{3 p n}) .

Note $Y_{t} \sim Bin (k n, p)$ so

ℙ (Y_{t} \geq k - 1) \leq ℙ (| Y_{t} - p k n | \geq 𝜀 k - 1) \leq 2 \exp (- \frac{{(𝜀 k - 1)}^{2}}{3 k}) \leq \exp (- \frac{𝜀^{2} k}{3.5}) .

Note that if $k \geq \frac{8}{𝜀^{2}} \log n$ , then the above is $\leq n^{- 2 - c}$ . Then union bound over all $\leq n^{2}$ choices for $t$ to see no such $Y_{t}$ satisfies $Y_{t} \geq k - 1$ . □

Theorem 10.9 (Ajtai, Komlós, Szemeredi). For $0 < 𝜀 < \frac{1}{3}$ , if $G \sim G (n, p)$ where $p = \frac{1 + 𝜀}{n}$ , then $G \supset P_{l}$ where $l \geq 𝜀^{5} n$ .

Lemma 10.10. Let $G$ be an $n$ vertex graph with DFS-sequence $X_{1}, X_{2}, \dots$ and

\sum_{i = 1}^{T} X_{i} \geq p T - 𝜀^{5} n,

where $T = 𝜀^{k} n^{2}$ . Then $G \supset P_{l}$ where $l \geq 𝜀^{5} n$ .

Proof. If at time $T$ we have $| B | \geq \frac{n}{3}$ , then since $| V (P) | \leq 𝜀^{5} n$ , assuming for contradiction $P_{l} ⁄ \subset G$ , for all steps. Then there must have been some step $\leq T$ in the algorithm where $| A | \geq \frac{n}{3}$ and $| B | \geq \frac{n}{3}$ . Then

𝜀^{2} n^{2} = T \geq | A | | B | \geq \frac{n^{2}}{9},

contradiction.

So we may assume $| B | \leq \frac{n}{3}$ . So we can assume at time $T$ that the algorithm is still running. We have

𝜀^{5} n + | B | \geq | V (P) | + | B | \geq \sum_{i = 1}^{T} X_{i} = (*)

since, each time we see $X_{i} = 1$ we move a vertex from $A$ into $V (P) \cup B$ , and it never returns. Now

(*) \geq p T - 𝜀^{5} n \geq \frac{(1 + 𝜀) 𝜀^{3} n^{2}}{n} - 𝜀^{5} n \geq \frac{(1 + 𝜀^{2}) T}{n} + 𝜀^{5} n .

So combining we have

\frac{n}{3} \geq | B | \geq \frac{(1 + 𝜀^{2}) T}{n} .

Also note

| A | = (n - | B | - | V (P) |)

\begin{array}{l} T & \geq | A | | B | \\ \geq (n - | B | - 𝜀^{5} n) | B | \\ \geq (n - \frac{(1 + 𝜀^{2}) T}{n} - 𝜀^{5} n) \frac{(1 + 𝜀^{2}) T}{n} \\ \geq (1 - 2 𝜀^{3}) (1 + 𝜀^{2}) T \\ > T \end{array}

contradiction. □

Reminder of Chernoff bound:

Lemma 10.11. Let $X \sim Bin (n, p)$ . Then, for $0 \leq t \leq p n$ , we have

ℙ (| X - 𝔼 X | \geq t) \leq 2 \exp (- \frac{t^{2}}{3 p n}) .

Proof of Theorem 10.9. Let $G \sim G (n, p)$ , where $p = \frac{(1 + 𝜀)}{n}$ , for $0 < 𝜀 < \frac{1}{3}$ . Let $X_{1}, X_{2}, X_{3}, \dots$ DFS-sequence. This is a sequence of iid Bernoulli random variables with probability $p$ . So set $T = 𝜀^{2} n^{2}$ and note

\begin{array}{l} ℙ (\sum_{i = 1}^{T} X_{i} < p T - 𝜀^{5} n) & \leq ℙ (| \sum_{i = 1}^{T} X_{i} - p T | > 𝜀^{5} n) \\ \leq 2 \exp (- \frac{𝜀^{10} n^{2}}{3 (1 + 𝜀) 𝜀^{3} n}) \\ \to 0 \end{array}

since $𝜀^{5} n < p T = (1 + 𝜀) 𝜀^{3} n$ . So apply Lemma 10.10 to see that with probability $1 - o (1)$ , $G \supset P_{l}$ , where $l \geq 𝜀^{5} n$ . □

Theorem 10.12. Let $𝜀 \to 0$ . Let $w$ be some function with $w \to \infty$ . Let $G \sim G (n, p)$ . Then

c_{1} (G) = {\begin{matrix} \frac{\log (𝜀^{3} n)}{𝜀^{2}} & 𝜀 < \frac{n^{- \frac{1}{3}}}{w} \\ Θ (n^{\frac{2}{3}} & 𝜀 = Θ (n^{- \frac{1}{3}}) \\ (2 + o (1)) 𝜀 n & 𝜀 = w \cdot n^{- \frac{1}{3}} \end{matrix}