Show that $p^*(n)=n^{-2/3}$ is the threshold function

Question

Show that $p^*(n)=n^{-2/3}$ is the threshold function for the property $G(n,p)$ contains at least $n/6$ pairwise vertex disjoint triangles. I'm considering the probability that some set of $n/2$ vertices is triangle free, but still stuck.

Answer 1

Below is my solution when I met the problem in a homework. And the main reference is

Alon, Noga, and Raphael Yuster. "Threshold functions for H-factors." Combinatorics, Probability and Computing 2.2 (1993): 137-144.

We claim that $p = n^{-2/3}$ is a threshold function for the given property. WLOG, we assume that $6$ divides $n$.

Lemma 2.1: There exists a positive constant $c$ such that almost surely $G(n, cn^{-2/3})$ contains less than $n/6$ pairwise vertex disjoint triangles.

Proof: Let $\{A_i : i \in I\}$ denote the set of all distinct labeled copies of $K_3$ in the complete labeled graph on $n$ vertices. Let $B_i$ be the event that $A_i \subset G(n, p)$, and let $X_i$ be the indicator random variable for $B_i$. Let $X = \sum_{i \in I} X_i$ be the number of distinct copies of $K_3$ in $G(n, p)$ (note that here we do not need the copies to be vertex disjoint). Suffice it to show that $X < n/6$ with high probability. It's easy to check that $$E[X] = \binom{n}{3} p^3 \leq c^3 n/6,$$ which can be upper bounded by $n/12$ with sufficiently small $c$, and implies that $E[X] = \Theta(n)$. For two copies $A_i$ and $A_j$ we say $i \sim j$ if they share one edge, and over all ordered pairs, let $$\Delta = \sum_{i \sim j} \Pr[B_i \wedge B_j].$$ As $Var[X] \leq E[X] + \Delta$, it remains to show that $\Delta = o(E^2[X])$ before using Chebyshev's Inequality to complete the proof. Actually, $$\Delta = \binom{n}{5} 5! p^5 \leq c^5 n^{5/3} = o(E^2[X]),$$ with sufficiently large $n$, completing the proof.

Lemma2.2: There exists a positive constant $C$ such that almost surely $G(n, Cn^{-2/3})$ contains at least $n/6$ pairwise vertex disjoint triangles.

Proof: Consider random graph $G(n/2, Cn^{-2/3})$, with the same notations used in the proof of Lemma $2.1$ (except that the number of vertices is $n/2$ now), we have $$\mu = E[X] \geq C^3n/16$$ and $$\Delta \leq C^5 n^{5/3}/32,$$ with sufficiently large $C$ and $n$. As $\Delta > \mu$ when $C$ and $n$ are sufficiently large, by the extended Janson inequality, we have $$\Pr[X=0] = \Pr[\bigwedge_{i \in I} \overline{B_i}] \leq e^{-\mu^2/2\Delta} \leq e^{-100n^{1/3}}.$$ Therefore, we conclude that almost surely $G(m, Cn^{-2/3})$ contains a triangle if $m \geq n/2$. From a random graph $G(n, p)$, with probability as least $(1 - e^{-100n^{1/3}})^{n/6}$, we can repeatedly do for $i \in [n/6]$,

[1] Find a triangle in the current graph on the remaining $n - 3(i-1)$ vertices

[2] Remove the $3$ vertices and all edges incident to them, now we essentially have $G(n-3i, Cn^{-2/3})$

Finally, we have $n/6$ pairwise vertex disjoint triangles with high probability, completing the proof of both the lemma and the whole problem.