Suppose $\Gamma(V, E)$ is a finite simple graph. Let’s call a finite simple graph $\Gamma’(V’, E’)$ an induced subgraph of $\Gamma$ iff $V’ \subset V$ and $E’ = (V’ \times V’) \cap E$.
Let’s call a finite simple graph $\Gamma$ $n$-universal, iff any finite simple graph on $n$ vertices is isomorphic to some induced subgraph of $\Gamma$.
What is the minimal possible number of vertices in an $n$-universal graph?
I managed only to find a lower bound for that size: $2n - 1$, as it contains $n$-vertex induced full and empty subgraphs, that can not have more than one common vertex.
However, no upper bound other than the trivial $n2^{\frac{n(n-1)}{2}}$ is currently known to me.
In "Asymptotically optimal induced universal graphs" by Noga Alon it is shown, that the minimal possible size of an $n$-universal graph is $(1 + o(1))2^{\frac{n - 1}{2}}$.
Moreover, it is also shown there, that if $\Gamma$ is an $n$-vertices Erdos-Renyi random graph with edge probability $\frac{1}{2}$, then it is $k$-universal with probability $(1 - e^{-C_n^k 2^{-\frac{k(k-1)}{2}}})^2 + o(1)$