In a random graph, every two vertices neighbor a clique with high probability

Question

Let $G\in G(n,p)$ be a random graph, and $k \in \mathbb{N}$ a constant . I want to prove that with high probability, every two vertices have a neighboring clique of size $k$, i.e. for every $v,u \in V(G)$, there are vertices $w_1,...,w_k \in V(G)$ such that $(w_i,w_j) \in E(G)$ for all $i,j$, and $(u,w_1),(u,w_2),...,(u,w_k),(v,w_1),(v,w_2),...,(v,w_k)\in E(G)$.$$ $$ Clearly for a fixed $u,v$, the probability that they neighbor a clique is $p^{{k \choose 2}+2k}$, but how do I pass from this to a general argument?

Answer 1

The statement

for a fixed $u,v$, the probability that they neighbor a clique is $p^{{k \choose 2}+2k}$

is actually not as clear as you make it out to be. This is, more precisely, the probability that, for a fixed $u$ and $v$, they border a specific clique you've picked out from the rest of $G(n,p)$. From here, if you multiply by the number of ways to pick such a clique, you could conclude that $$ p^{{k \choose 2}+2k} \binom{n-2}{k} $$ is the expected number of cliques that $u$ and $v$ border, but that is not too helpful. It goes to infinity with $n$: assuming $p, k$ are constant, this expression is $O(n^k)$. But this does not guarantee the existence of a clique with high probability.

---

However, the statement that every two vertices border a constant-size clique is actually not the best possible statement along those lines; if we use some high-powered concentration arguments, it becomes very easy to prove (and more is true).

For a fixed $u,v$, let $G_{uv}$ be the subgraph of $G$ consisting only of the common neighbors of $u$ and $v$. The number of vertices in $G_{uv}$ has the $\text{Binomial}(n-2, p^2)$ distribution, which is very closely concentrated around its mean $(n-2)p^2$; by a Chernoff-type bound, the probabability that it is below even $0.99p^2n$ is exponentially small in $n$. Since there are only $\binom n2$ pairs $(u,v)$ to consider, the union bound is enough to guarantee that with high probability, $G_{uv}$ has $O(n)$ vertices for any pair $(u,v)$.

Similarly, the number of cliques of size $k$ in $G_{uv}$ is very closely concentrated around its mean, and the probability that there are no such cliques is once again exponentially small. Unfortunately, the number of cliques is not binomial, so we need more powerful tools to prove this. Janson's inequality will work.

You can compare this to Bollobás's 1988 proof that $\chi(G(n,1/2)) \sim \frac{n}{2\log_2 n}$ with high probability. There, the key ingredient was to prove that with high probability, every subgraph of size $\frac{n}{\log^2 n}$ has a clique of size $(1+o(1))\log_2 n$. Here, you want a much weaker statement:

• We only have $O(n^2)$ subgraphs $G_{uv}$ to deal with, not all of them;
• They have linear size, so cliques will be easier to find;
• We are looking for a clique of constant, not logarithmic size.

So we can easily conclude that each $G_{uv}$ contains a clique of size $k$ with high probability, which completes the proof. (Also, each $G_{uv}$ contains a clique of size $(1+o(1))\log_2 n$ with high probability. We can't do better than that, because with high probability that's about how big the largest clique in $G(n,p)$ is, too.)