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.



Probability of each edge in K-clique
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


$p^{4k-8-2t+2\binom{k-2}{2}-\binom{t}{2}}n^{2k-4-t}k^t$


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.


