Number of all graphs that contain at least one $k$-clique

111 Views Asked by At

There are $n$ vertices and natural number $k$.

How many are there graphs that contain at least one $k$-clique?

I tried to find number of all homomorphism between complete graph $K_{k}$ and graph with $n$-vertices. But i don't know how to do this.

A few weeks ago i asked simillar question that its answer would imply solution for this problem, but i saw that using that method some graphs are counted more than once.

1

There are 1 best solutions below

0
On

Exact results don't seem to be known, even for the simplest nontrivial case $k=3$ (in the case $k=2$, the answer is $2^{\binom n2} - 1$, since all $n$-vertex graphs except the empty graph contain a copy of $K_2$).

For any $k \ge 1$, almost all of the $2^{\binom n2}$ $n$-vertex graphs contain a $k$-clique (that is, the fraction of $n$-vertex graphs that don't approaches $0$ as $n \to \infty$). It is more natural to count the graphs that are $K_k$-free, and subtract the resulting number from $2^{\binom n2}$ to get the answer you want.

Let $f_k(n)$ denote the number of $K_k$-free graphs on $n$ vertices. The $(k-1)$-partite Turán graph on $n$ vertices has approximately $\binom{k-1}{2}(\frac{n}{k-1})^2 = (1 - \frac1{k-1})\frac{n^2}{2}$ edges; this is exact when $k-1 \mid n$. This graph, and every subgraph of this graph, is $K_k$-free; this gives us $2^{(1 - \frac1{k-1})\frac{n^2}{2}}$ distinct $K_k$-free graphs already.

Erdös, Frankl and Rödl (The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent) show that this is asymptotically tight in the following sense: we have $$f_k(n) = 2^{(1 - \frac1{k-1} + o(1))\frac{n^2}{2}}$$ for fixed $k$ as $n \to \infty$. Here, $o(1)$ stands for a function approaching $0$ as $n\to \infty$. More is true: the same bound holds if we consider $H$-free graphs for any fixed graph $H$ with chromatic number $k$. So the answer to your question is that asymptotically, $$2^{\binom n2} - 2^{(1 - \frac1{k-1}+o(1))\frac{n^2}{2}}$$ of the $n$-vertex graphs contain at least one $K_k$.