Modern Graph Theory — Homework 4

Loading…

Modern Graph Theory — Homework 4

Assignments: Mar 24th, 2026

Problem 1.

Prove: For any two probabilities

p_1 and p_2 such that p_1 \leq p_2 and for a monotone increasing graph property \mathcal{Q}, we have that

\mathbb{P}[G{n,p1} \in \mathcal{Q}] \leq \mathbb{P}[G{n,p2} \in \mathcal{Q}].

**Proof.** Let G_1 \sim G_{n,p_1} and G_2 \sim G_{n,p_2} be two random graphs on the same vertex set V = \{1, 2, \ldots, n\}. Since p_1 \leq p_2, we can write p_2 = p_1 + (p_2 - p_1) where 0 \leq p_2 - p_1 \leq 1 - p_1. For each potential edge e \in \binom{V}{2} , we generate independent random variables: X_e \sim \text{Bernoulli}(p_1) and Y_e \sim \text{Bernoulli}\left(\frac{p_2 - p_1}{1 - p_1}\right) independent of X_e, then we define Z_e = \max\{X_e, Y_e\}. Note that since p_2 \leq 1, we have \frac{p_2 - p_1}{1 - p_1} \leq 1. First, \mathbb{P}[X_e = 1] = p_1, so the graph G_1 with edges \{e : X_e = 1\} follows G_{n,p_1}. For Z_e, we have:

\mathbb{P}[Ze = 1] &= \mathbb{P}[Xe = 1 \text{ or } Ye = 1] \ &= 1 - \mathbb{P}[Xe = 0]\mathbb{P}[Ye = 0] \ &= 1 - (1-p1)\left(1 - \frac{p2 - p1}{1 - p1}\right) \ &= 1 - (1-p1)\cdot\frac{1 - p1 - (p2 - p1)}{1 - p1} \ &= 1 - (1 - p2) = p2.

Thus the graph G_2 with edges \{e : Z_e = 1\} follows G_{n,p_2}. By construction, X_e \leq Z_e for all e \in \binom{V}{2}, which means E(G_1) = \{e : X_e = 1\} \subseteq \{e : Z_e = 1\} = E(G_2). Therefore, G_1 is always a subgraph of G_2 in this coupling, i.e., G_1 \subseteq G_2. Since \mathcal{Q} is a monotone increasing graph property, we have G_1 \subseteq G_2 and G_1 \in \mathcal{Q} implies G_2 \in \mathcal{Q}, equivalently, the indicator satisfies \mathbf{1}_{\{G_1 \in \mathcal{Q}\}} \leq \mathbf{1}_{\{G_2 \in \mathcal{Q}\}} almost surely. For expectations:

\mathbb{P}[G1 \in \mathcal{Q}] = \mathbb{E}[\mathbf{1}{{G1 \in \mathcal{Q}}}] \leq \mathbb{E}[\mathbf{1}{{G2 \in \mathcal{Q}}}] = \mathbb{P}[G2 \in \mathcal{Q}].

In other word:

\mathbb{P}[G{n,p1} \in \mathcal{Q}] \leq \mathbb{P}[G{n,p2} \in \mathcal{Q}]

∎ **Problem 2.** Determine the threshold function p^*(n) for a random graph G_{n,p_n} to contain a triangle, and prove it. **Proof.** The threshold function for containing a triangle is p^*(n) = \frac{1}{n}. More precisely, if p_n \ll \frac{1}{n} (i.e., p_n = o(1/n)), then \mathbb{P}[G_{n,p_n} \text{ contains a triangle}] \to 0 as n \to \infty; and if p_n \gg \frac{1}{n} (i.e., p_n = \omega(1/n)), then \mathbb{P}[G_{n,p_n} \text{ contains a triangle}] \to 1 as n \to \infty. Let X_n be the number of triangles in G_{n,p_n}. There are \binom{n}{3} possible triangles (3-vertex subsets), each appearing with probability p_n^3 (all 3 edges must be present), so:

\mathbb{E}[Xn] = \binom{n}{3} pn^3 = \frac{n(n-1)(n-2)}{6} pn^3 \sim \frac{n^3 pn^3}{6}.

When p_n \ll 1/n , we have np_n = o(1), so \mathbb{E}[X_n] \sim \frac{(np_n)^3}{6} \to 0. By Markov's inequality, \mathbb{P}[X_n \geq 1] \leq \mathbb{E}[X_n] \to 0, thus \mathbb{P}[G_{n,p_n} \text{ contains a triangle}] \to 0. When p_n \gg 1/n , we have np_n \to \infty, so \mathbb{E}[X_n] \sim \frac{(np_n)^3}{6} \to \infty. To show \mathbb{P}[X_n \geq 1] \to 1, we use Chebyshev's inequality :

\mathbb{P}[Xn = 0] \leq \frac{\text{Var}(Xn)}{(\mathbb{E}[X_n])^2},

and we need to show \frac{\text{Var}(X_n)}{(\mathbb{E}[X_n])^2} \to 0. Let T_1, T_2, \ldots, T_m be all possible triangles where m = \binom{n}{3}, and let I_i be the indicator that triangle T_i is present. Then X_n = \sum_{i=1}^m I_i, and:

\text{Var}(Xn) = \sum{i=1}^m \text{Var}(Ii) + \sum{i \neq j} \text{Cov}(Ii, Ij).

For the diagonal terms, \text{Var}(I_i) = p_n^3(1-p_n^3) \leq p_n^3, so \sum_i \text{Var}(I_i) \leq mp_n^3 = \mathbb{E}[X_n]. For the off-diagonal terms, two triangles T_i and T_j can share 0 edges (disjoint), 1 edge (forms a "diamond" with 4 vertices), or 2/3 edges (same triangle, excluded since i \neq j). For disjoint triangles (|V(T_i) \cap V(T_j)| \leq 1, so 0 shared edges), I_i and I_j are independent, so \text{Cov}(I_i, I_j) = 0. For triangles sharing exactly one edge (|V(T_i) \cap V(T_j)| = 2), there are O(n^4) such pairs (choose 4 vertices, then choose which edge is shared). For each such pair, both triangles appear if all 5 edges are present, so \mathbb{E}[I_i I_j] = p_n^5 and \mathbb{E}[I_i]\mathbb{E}[I_j] = p_n^6, giving \text{Cov}(I_i, I_j) = p_n^5 - p_n^6 = p_n^5(1-p_n) \leq p_n^5. The total contribution is O(n^4 p_n^5). Putting together the variance bound:

\text{Var}(Xn) \leq \mathbb{E}[Xn] + O(n^4 pn^5) = O(n^3 pn^3 + n^4 p_n^5).

Now compute:

\frac{\text{Var}(Xn)}{(\mathbb{E}[Xn])^2} \leq \frac{O(n^3 pn^3 + n^4 pn^5)}{(n^3 pn^3)^2} = O\left(\frac{1}{n^3 pn^3} + \frac{1}{n^2 p_n}\right).

When p_n = \omega(1/n), we have n^3 p_n^3 \to \infty so \frac{1}{n^3 p_n^3} \to 0, and n^2 p_n \to \infty so \frac{1}{n^2 p_n} \to 0. Therefore, \frac{\text{Var}(X_n)}{(\mathbb{E}[X_n])^2} \to 0, which implies \mathbb{P}[X_n = 0] \to 0, so \mathbb{P}[G_{n,p_n} \text{ contains a triangle}] = \mathbb{P}[X_n \geq 1] \to 1. In conclusion, we have proven that p^*(n) = 1/n is a threshold function for the property of containing a triangle:

\mathbb{P}[G{n,pn} \text{ contains a triangle}] \to \begin{cases} 0 & \text{if } pn \ll 1/n, \[0.5em] 1 & \text{if } pn \gg 1/n. \end{cases}

∎

PDF

Download the original write-up here.

Assignments: Mar 24th, 2026

Problem 1.

Prove: For any two probabilities

p_1 and p_2 such that p_1 \leq p_2 and for a monotone increasing graph property \mathcal{Q}, we have that

\mathbb{P}[G{n,p1} \in \mathcal{Q}] \leq \mathbb{P}[G{n,p2} \in \mathcal{Q}].

**Proof.** Let G_1 \sim G_{n,p_1} and G_2 \sim G_{n,p_2} be two random graphs on the same vertex set V = \{1, 2, \ldots, n\}. Since p_1 \leq p_2, we can write p_2 = p_1 + (p_2 - p_1) where 0 \leq p_2 - p_1 \leq 1 - p_1. For each potential edge e \in \binom{V}{2} , we generate independent random variables: X_e \sim \text{Bernoulli}(p_1) and Y_e \sim \text{Bernoulli}\left(\frac{p_2 - p_1}{1 - p_1}\right) independent of X_e, then we define Z_e = \max\{X_e, Y_e\}. Note that since p_2 \leq 1, we have \frac{p_2 - p_1}{1 - p_1} \leq 1. First, \mathbb{P}[X_e = 1] = p_1, so the graph G_1 with edges \{e : X_e = 1\} follows G_{n,p_1}. For Z_e, we have:

Thus the graph G_2 with edges \{e : Z_e = 1\} follows G_{n,p_2}. By construction, X_e \leq Z_e for all e \in \binom{V}{2}, which means E(G_1) = \{e : X_e = 1\} \subseteq \{e : Z_e = 1\} = E(G_2). Therefore, G_1 is always a subgraph of G_2 in this coupling, i.e., G_1 \subseteq G_2. Since \mathcal{Q} is a monotone increasing graph property, we have G_1 \subseteq G_2 and G_1 \in \mathcal{Q} implies G_2 \in \mathcal{Q}, equivalently, the indicator satisfies \mathbf{1}_{\{G_1 \in \mathcal{Q}\}} \leq \mathbf{1}_{\{G_2 \in \mathcal{Q}\}} almost surely. For expectations:

\mathbb{P}[G1 \in \mathcal{Q}] = \mathbb{E}[\mathbf{1}{{G1 \in \mathcal{Q}}}] \leq \mathbb{E}[\mathbf{1}{{G2 \in \mathcal{Q}}}] = \mathbb{P}[G2 \in \mathcal{Q}].

In other word:

\mathbb{P}[G{n,p1} \in \mathcal{Q}] \leq \mathbb{P}[G{n,p2} \in \mathcal{Q}]

∎ **Problem 2.** Determine the threshold function p^*(n) for a random graph G_{n,p_n} to contain a triangle, and prove it. **Proof.** The threshold function for containing a triangle is p^*(n) = \frac{1}{n}. More precisely, if p_n \ll \frac{1}{n} (i.e., p_n = o(1/n)), then \mathbb{P}[G_{n,p_n} \text{ contains a triangle}] \to 0 as n \to \infty; and if p_n \gg \frac{1}{n} (i.e., p_n = \omega(1/n)), then \mathbb{P}[G_{n,p_n} \text{ contains a triangle}] \to 1 as n \to \infty. Let X_n be the number of triangles in G_{n,p_n}. There are \binom{n}{3} possible triangles (3-vertex subsets), each appearing with probability p_n^3 (all 3 edges must be present), so:

\mathbb{E}[Xn] = \binom{n}{3} pn^3 = \frac{n(n-1)(n-2)}{6} pn^3 \sim \frac{n^3 pn^3}{6}.

When p_n \ll 1/n , we have np_n = o(1), so \mathbb{E}[X_n] \sim \frac{(np_n)^3}{6} \to 0. By Markov's inequality, \mathbb{P}[X_n \geq 1] \leq \mathbb{E}[X_n] \to 0, thus \mathbb{P}[G_{n,p_n} \text{ contains a triangle}] \to 0. When p_n \gg 1/n , we have np_n \to \infty, so \mathbb{E}[X_n] \sim \frac{(np_n)^3}{6} \to \infty. To show \mathbb{P}[X_n \geq 1] \to 1, we use Chebyshev's inequality :

\mathbb{P}[Xn = 0] \leq \frac{\text{Var}(Xn)}{(\mathbb{E}[X_n])^2},

and we need to show \frac{\text{Var}(X_n)}{(\mathbb{E}[X_n])^2} \to 0. Let T_1, T_2, \ldots, T_m be all possible triangles where m = \binom{n}{3}, and let I_i be the indicator that triangle T_i is present. Then X_n = \sum_{i=1}^m I_i, and:

\text{Var}(Xn) = \sum{i=1}^m \text{Var}(Ii) + \sum{i \neq j} \text{Cov}(Ii, Ij).

For the diagonal terms, \text{Var}(I_i) = p_n^3(1-p_n^3) \leq p_n^3, so \sum_i \text{Var}(I_i) \leq mp_n^3 = \mathbb{E}[X_n]. For the off-diagonal terms, two triangles T_i and T_j can share 0 edges (disjoint), 1 edge (forms a "diamond" with 4 vertices), or 2/3 edges (same triangle, excluded since i \neq j). For disjoint triangles (|V(T_i) \cap V(T_j)| \leq 1, so 0 shared edges), I_i and I_j are independent, so \text{Cov}(I_i, I_j) = 0. For triangles sharing exactly one edge (|V(T_i) \cap V(T_j)| = 2), there are O(n^4) such pairs (choose 4 vertices, then choose which edge is shared). For each such pair, both triangles appear if all 5 edges are present, so \mathbb{E}[I_i I_j] = p_n^5 and \mathbb{E}[I_i]\mathbb{E}[I_j] = p_n^6, giving \text{Cov}(I_i, I_j) = p_n^5 - p_n^6 = p_n^5(1-p_n) \leq p_n^5. The total contribution is O(n^4 p_n^5). Putting together the variance bound:

\text{Var}(Xn) \leq \mathbb{E}[Xn] + O(n^4 pn^5) = O(n^3 pn^3 + n^4 p_n^5).

Now compute:

\frac{\text{Var}(Xn)}{(\mathbb{E}[Xn])^2} \leq \frac{O(n^3 pn^3 + n^4 pn^5)}{(n^3 pn^3)^2} = O\left(\frac{1}{n^3 pn^3} + \frac{1}{n^2 p_n}\right).

When p_n = \omega(1/n), we have n^3 p_n^3 \to \infty so \frac{1}{n^3 p_n^3} \to 0, and n^2 p_n \to \infty so \frac{1}{n^2 p_n} \to 0. Therefore, \frac{\text{Var}(X_n)}{(\mathbb{E}[X_n])^2} \to 0, which implies \mathbb{P}[X_n = 0] \to 0, so \mathbb{P}[G_{n,p_n} \text{ contains a triangle}] = \mathbb{P}[X_n \geq 1] \to 1. In conclusion, we have proven that p^*(n) = 1/n is a threshold function for the property of containing a triangle:

\mathbb{P}[G{n,pn} \text{ contains a triangle}] \to \begin{cases} 0 & \text{if } pn \ll 1/n, \[0.5em] 1 & \text{if } pn \gg 1/n. \end{cases}

∎

PDF

Download the original write-up here.

Modern Graph Theory — Homework 4

Search

Modern Graph Theory — Homework 4

Assignments: Mar 24th, 2026

PDF

Assignments: Mar 24th, 2026

PDF