# How to estimate the growth of the probability that $G(n, M)$ contains a $k$-clique

Let $k\geq 3$ be a fixed positive integer. Define

$t_k(M)=\Pr[G(n, M) \text{contains a}\ k-\text{clique}]$, where $G(n, M)$ is the random graph uniformly distributed on all $n$-vertex graphs with $m$-edges. The question is how to estimate the growth of $t_k(M)$ with respect to M.

$t_k(M+1)=t_k(M)$ when $M$ is large (by Turan's theorem) or is small. So I am just interested in the case that $n^c\geq M\geq\frac{k(k+1)}{2}$, where $1< c< 2$ is a constant.

Is it true that $t_k(M+1)-t_k(M)\geq\frac{1}{poly(n)}$ or $\frac{t_k(M+1)}{t_k(M)}\geq 1+\frac{1}{poly(n)}$ when $M$ in the interval above?

Thanks.

• I believe the results will be false if $c$ is taken slightly larger than $2-2/(k-1)$ (the threshold for a random $G(n,m)$ to have a clique). For a graph from the $G(n,p)$ model in this range, there are concentration results saying that the probability you fail to have a clique decays much faster than polynomially (see for example Guy Wolfovitz's Theorem 2 at arxiv.org/abs/0912.3868 ), and the same sort of concentration should hold for $G(n,M)$. So the probability's already so close to $1$ that adding another edge can't change it much. This doesn't say much about smaller c though. – Kevin P. Costello Aug 31 '10 at 18:08

You might take a look at Chapter VII of Bollobas. In particular, Theorem VII.1.7 -- which is simple enough that he doesn't bother providing a proof -- states that the expected number of $k$-cliques in $G(n,M)$ is, setting $N={n \choose 2}$ and $K={k \choose 2}$, $${n \choose k} {n-K \choose M- K} {N \choose M}^{-1}.$$ Also, Theorem VII.3.7 states that if $M=o(n^{-2/(k-1)})$ then with probability tending to one, $G_{n,M}$ contains no $k$-clique, whereas if $M/n^{-2/(k-1)} \to \infty$ then with probability tending to one $G_{n,M}$ does contain a $k$-clique. I know this doesn't fully answer your question but it may help.
Incidentally, (you probably already realize that) it is a priori possible (though I don't think it is the case) that, for example, $t_k(M+1)-t_k(M) \geq \frac{1}{\mathrm{poly}(n)}$ for all ${k \choose 2}\leq M \leq \lceil \frac{(k-1)N}{k}\rceil$, since all we really know by Turán is that $$\sum_{M=K}^{\lceil(k-1)N/k\rceil} (t_k(M+1)-t_k(M)) = 1.$$