MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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 ), 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. $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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