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 lower bound $t_k(M+1)-t_k(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)}$ when $M$ in the interval above?

Thanks.

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.