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.
