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?


  • $\begingroup$ 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. $\endgroup$ – 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. $$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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