Let $k_0 \in k_0(n) \subset \mathbb{N}$ be such that
$${n \choose k_0} 2^{-{k_0 \choose 2}} < 1 < {n \choose k_0 – 1} 2^{-{k_0 – 1 \choose 2}}$$
and let $k = k_0 – 4$. Show that
$$\mathbb{P}\left[ G(n,1/2) \text{ contains every graph on $k$ vertices as an induced subgraph } \right] \overset{n \rightarrow \infty}\longrightarrow 1.$$
Remark: This problem is probably meant to be solved with Janson's inequality (for the version that I know see this picture from "Probabilistic Methods in Combinatorics" by Yufei Zhao below).
I think the right way to start goes like this: First we note that there are $2^{k \choose 2}$ possible graphs $H_i$ on $k$ vertices. To apply Janson's inequality we define the $A_i$ to the event that $G(n,1/2)$ does NOT contain the $i$-th graph $H_i$.
However, I am unsure how to compute $\mu$ and $\Delta$. For $\mu$ I can see that for any fixed graph $H$ on $k$ vertices we may partition $G(n,1/2)$ into $\lfloor n/k \rfloor$ $k$-components, which have probability $0 < q < 1$ of NOT containing $H$ and since all these components independently contain $H$ or not it holds
$$\mathbb{P}\left[\text{$G(n,1/2)$ does not contain $H$}\right] = q^{\lfloor n/k \rfloor} \overset{n \rightarrow \infty}\longrightarrow 0.$$
(Unrelated: We observe that therefore $\mathbb{P}\left[\text{$G(n,1/2)$ contains $H$}\right] \overset{n \rightarrow \infty}\longrightarrow 1$.) Thus I think we should be able to conclude that $\mu \rightarrow 0$.
However, I do not see what to do with $\Delta$. I am tempted to simply write
$$\mathbb{P}\left[A_i \land A_j \right] \le \mathbb{P} \left[ A_i \right] \longrightarrow 0,$$
but I do not think that we can do that since we do not use the condition on the $k_0(n)$ anywhere. What am I missing?
Best Answer
Consider $G = G(n, 1/2)$, we divide $V = V(G)$ into $k$ disjoint parts $V_i$ (WLOG, we assume that $k$ divides $n$), each of size $m := \frac{n}{k}$. Let $H$ be a labeled graph on $[k]$, and let $A = \{a_1, \ldots ,a_k\} \subseteq V$ where $a_i \in V_i$ for each $i \in [k]$. There are $m^k$ such $A$ in total. We say $A$ is a residence (i.e., isomorphism) of $H$ in $G$ if $a_i$ and $a_j$ are adjacent in $G$ iff $i$ and $j$ is connected in $H$. That is, $A$ is a residence of $H$ iff $G[A]$ is an induced subgraph of $G$ isomorphic to $H$. Therefore, the probability that $G$ contains no $H$ as an induced subgraph is at most the probability that there exists no such $A$ such that $A$ is a residence of $H$.
Now, for each $(i, j)$ pair such that $(i, j) \notin H$, then for each $(v, u)$ pair with $v \in V_i$ and $u \in V_j$, we reverse the connection between $v$ and $u$ and call the new graph $G^\prime$. By doing this, $A$ is a residence of $H$ in $G$ iff $A$ is a residence of $K_k$ in this modified graph $G^\prime$. Now let's consider the probability that there exists no such $A$ in $G^\prime$, note that $G^\prime$ still has the same probability, as $G$, following $G(n, 1/2)$, i.e., $G'$ can still be seen as a random graph sampled from $G(n, 1/2)$.
Above, what we do is to show that we can compute for $K_k$ only.
Let $\{A_i\}_{i \in I}$ be the set of all vertex sets $A \subseteq V$ consisting of exactly one vertex from each $V_i$, with $\lvert I \rvert = m^k$ as mentioned above. Let $B_i$ be the event that $A_i$ is a residence of $K_k$ in $G^\prime$, and let $X = \sum_{i \in I} X_i$, where $X_i$ is the indicator random variable for $B_i$.
We have $$\mu = \mathbb{E}[X] = m^k/2^{\binom{k}{2}}$$ and $$\Delta = \sum_{i \sim j} \Pr[B_i \wedge B_j] = \sum_{l = 2}^k \binom{k}{l} m^l (\binom{m}{2})^{k-l} (\frac{1}{2})^{2\binom{k}{2} - \binom{l}{2}} = \sum_{l = 2}^k m^k \binom{k}{l} (m-1)^{k-l} 2^{-2\binom{k}{2} + \binom{l}{2} + l - k},$$ where $l$ is the number of shared nodes between $B_i$ and $B_j$.
By the extended Janson inequality, we have $$\Pr[\bigwedge_{i \in I} \overline{B_i}] \leq e^{-\frac{\mu^2}{2\Delta}},$$ where \begin{align*} \frac{\mu^2}{2\Delta} = \frac{m^k}{2\sum_{l=2}^k \binom{k}{l} (m-1)^{k-l} 2^{\binom{l}{2} + l - k}} = \frac{1}{2\sum_{l=2}^k \binom{k}{l} (m-1)^{k-l} m^{-k} 2^{\binom{l}{2} + l - k}}. \end{align*}
We need to show that $2\sum_{l=2}^k \binom{k}{l} (m-1)^{k-l} m^{-k} 2^{\binom{l}{2}} \to 0$ as $n \to \infty$, where I believe we can use the given condition.