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

Question

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.

Answer 1

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. $$