Graph containing every n-vertex graph as an induced subgraph

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.

• 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/… Apr 7, 2012 at 13:19
• 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. Apr 7, 2012 at 13:23

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.