1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented Mar 29, 2013 at 3:36
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Andrew D. King
    Commented Mar 29, 2013 at 16:31
  • $\begingroup$ @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 $\endgroup$
    – vzn
    Commented Mar 29, 2013 at 16:58
  • $\begingroup$ Do you really expect someone can tell you a formula for the number? If you want asymptotics you should ask for asymptotics. $\endgroup$
    – Douglas Zare
    Commented Mar 30, 2013 at 1:31
  • $\begingroup$ @douglas are you saying a closed form formula is unlikely to exist, or hard to find, etc? $\endgroup$
    – vzn
    Commented Apr 12, 2013 at 18:06

0

Reset to default

You must log in to answer this question.