12
$\begingroup$

Let $f(n)$ denote the minimum number of vertices in a graph $G$ which contains every graph on $n$ vertices (up to isomorphism) as an induced subgraph. I want to estimate $f(n)$. A simple counting argument gives a lower bound : there are essentially $2^{C(n,2)}/n!$ isomorphism classes of graphs on $n$ vertices, while a graph with $N$ vertices contains $C(N,n) \approx N^{n}/n!$ induced subgraphs of size $n$. From this we can deduce that, for example, \begin{eqnarray*} \liminf_{n\rightarrow \infty} f(n) ^{1/n} \geq \sqrt{2}. \end{eqnarray*} Can we replace the inequality by an equality here ? I assume the answer is known, though I didn't find it after some basic googling. I know that the liminf above is $O(1)$, for example this follows from the main result of [1]. Indeed, it follows from [1] and the standard probabilistic argument for lower-bounding Ramsey numbers that there is some $c > 0$ for which the random graph $G(c^n, 1/2)$ almost surely, as $n \rightarrow \infty$, contains every graph on $n$ vertices as an induced subgraph. I assume the best-possible $c$ here is not known, since any $c < 4$ would yield an improvement on the best-known upper bound for Ramsey numbers.

[1] H.I. Prömel and V. Rödl, Non-Ramsey graphs are $c \log n$-universal, J. Combin. Theory Series A 88 (1999), 379-384.

$\endgroup$
2
  • 3
    $\begingroup$ Chris Godsil's answer over at Mathunderflow shows that the size of a graph which contains each $n$-vertex graph as an induced subgraph is exponential in $n$. See math.stackexchange.com/questions/75209/… $\endgroup$
    – Tony Huynh
    Apr 7, 2012 at 13:19
  • 5
    $\begingroup$ Vu has shown that there is a graph on $2^{n+2}$ vertices that contains all graphs on $n$ vertices as an induced subgraph. (Combinatorica 16 (1996), 295-299). I suspect that the answer to your question is not known. $\endgroup$ Apr 7, 2012 at 13:23

1 Answer 1

4
$\begingroup$

@Tony and Chris : Thanks for your very helpful comments. I had a look at Vu's paper and it references an earlier paper

B. Bollobas and A. Thomason, Graphs which contain all small graphs, Europ. J. Combinatorics 2 (1981), 13-15.

There it is proven (according to the review on MathSciNet, I could not find the original paper online) that almost every graph on approximately $n^2 2^{n/2}$ vertices is what they call $n$-full, i.e.: contains every graph on $n$ vertices as an induced subgraph. This answers all my questions : my function $f(n)^{1/n}$ does indeed tend to $\sqrt{2}$, and $G(c^n,1/2)$ is almost surely $n$-full for any $c > \sqrt{2}$. It was incorrect of me to suggest, when I posed the question, that the latter fact would have any consequences for estimating Ramsey numbers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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