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

consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges.

looking for a formula that counts the number of these graphs that have a $k$-clique but not a $(k+1)$-clique.

looked at some of the Erdos-Renyi random graph theory and related formulas but did not see this case covered so far. an estimate may be ok. also if this is used in a paper somewhere, that would be useful to know.

edit as Erdos-Renyi theory & a comment points out the critical point for detection of a $k$-clique is at $k=\log(n)$ where the probability goes from $P<0.5$ to $P>0.5$. it would be very interesting if there was a formula that could be derived independent of these regions (once called "subcritical, critical, supercritical"), but am seeking the answer for $k \approx \log(n)$ in particular.

background/motivation: question inspired by similar constructions in theoretical computer science circuit theory proofs/theorems.

share|cite|improve this question
Asymptotically, for fixed $k\ge 2$, almost all $K_{k+1}$-free graphs have $K_k$. But except for $k=2$, which is obvious, I'm not even sure that has been proved. – Brendan McKay Mar 29 '13 at 3:36
Parallel to Brendan's comment, if $k$ is larger than order $\log(n)$, the probability of $\omega(G)$ being $k+1$ is vanishingly small compared to the probability of $\omega(G)$ being $k$. I recommend looking at Chapter 7 of Random Graphs by Janson, Luczak and Rucinski. Note that since you have half the edges, looking at the size of a maximum stable set is equivalent to looking at the size of a maximum clique. You should also look at Section 1.4 if you are unfamiliar with the asymptotic equivalence of $G(n,p)$ and $G(n,m)$. – Andrew D. King Mar 29 '13 at 16:31
@andrew thanks. yes from Erdos-Renyi theory, $\log(n)$ is the so-called "critical point" where existence of k-cliques switches from low (P<0.5) to high (P>0.5) probability, and am looking for the answer in exactly that region where P=0.5. should have mentioned that in the question. will edit – vzn Mar 29 '13 at 16:58
Do you really expect someone can tell you a formula for the number? If you want asymptotics you should ask for asymptotics. – Douglas Zare Mar 30 '13 at 1:31
@douglas are you saying a closed form formula is unlikely to exist, or hard to find, etc? – vzn Apr 12 '13 at 18:06

Your Answer


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

Browse other questions tagged or ask your own question.