Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
5  
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
1  
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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.