For $c \in R$ and $k \in N$, $k \geq 3$ let $p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$.

I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy of a $k$-Clique with probability $1-\frac{1}{n^\epsilon}$ for some $\epsilon >0$

My approach has so far been to formulate the problem in such a way so that Janson's inequality can be applied. However it quickly becomes messy since all sizes of intersections of k-Cliques has to be considered.

  • $\begingroup$ This is not a research-level question, being a standard exercise. I vote to close as being off-topic for MO. $\endgroup$
    – Boris Bukh
    Nov 5, 2014 at 13:39

1 Answer 1


The way you're suggesting will work fine; just don't try to be careful with estimations (otherwise it does get messy).

Given a pair of vertices $u,v$, condition on their being adjacent. Reveal all the edges leaving $u$ and $v$; with exponentially good probability in $p^2n$ you find at least $p^2n/2$ common neighbours. Reveal the edges within these common neighbours and estimate the probability you find no $K_{k-2}$. This is a standard use of Janson's inequality, which you can find in for example the Janson-Luczak-Rucinski book.

To spell out the details, you need to show the sum over intersecting pairs of cliques of the existence probability is small compared to the expected number of cliques which is $p^{\binom{k-2}{2}}(p^2 n/2)^{k-2}$. So let the intersection be in $t$ vertices (where $t$ is between two and $k-3$) and the number of ways of getting such an intersection is at most $(p^2 n)^{2k-4-t}k^t$, while the probability of any such pair existing is $p^{2\binom{k-2}{2}-\binom{t}{2}}$. So you are looking at something at most


and it's easy to check that this is much smaller than the expectation by choice of $p$.

You need $p^{\binom{k-2}{2}}(p^2 n/2)^{k-2}$ to be of order $\log n$ in order to get polynomial concentration (and once you get it changing $p$ by a constant factor will give you any polynomial you like) so your $c$ can be taken to be $2/(k-2)(k+1)$. Then you have polynomially small probability that your chosen edge wasn't in any $K_k$, and union bound over the $n^2$ pairs gives the desired result, indeed with 'for some $\varepsilon>0$' replaced by 'for every $\varepsilon>0$' if you choose $c>2/(k-2)(k+1)$.

In general, when you use Janson's inequality and you do not care about constant factors in $p$ (as is usually the case) you do not need to do any careful estimation, any crude upper bound for constants will work.

  • $\begingroup$ I vote down as MO should not be a place where a solutions to standard exercises are given. $\endgroup$
    – Boris Bukh
    Nov 5, 2014 at 13:40
  • $\begingroup$ I don't think this can be a set exercise as surely anyone giving this as an exercise question would ask the student to prove the better concentration result I sketched (the one asked for isn't all that practically useful!)? But otherwise I agree. $\endgroup$
    – Peter
    Nov 5, 2014 at 16:43
  • $\begingroup$ My point is not so much that assisting a cheating student is unethical, but that the questions that are not on the level appropriate for MathOverflow (as defined in Help Center) should not be encouraged by being answered. $\endgroup$
    – Boris Bukh
    Nov 5, 2014 at 19:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.