¿Cuál es el tamaño mínimo posible de un $n$ -¿Gráfico universal?

Question

Supongamos que $\Gamma(V, E)$ es un gráfico simple finito. Llamemos a un grafo simple finito $\Gamma’(V’, E’)$ un subgrafo inducido de $\Gamma$ si $V’ \subset V$ y $E’ = (V’ \times V’) \cap E$ .

Llamemos a un gráfico simple finito $\Gamma$ $n$ -universal, si cualquier grafo simple finito en $n$ vértices es isomorfo a algún subgrafo inducido de $\Gamma$ .

¿Cuál es el mínimo número posible de vértices en un $n$ -¿Gráfico universal?

Sólo he conseguido encontrar un límite inferior para ese tamaño: $2n - 1$ ya que contiene $n$ -vértices inducidos por subgrafos llenos y vacíos, que no pueden tener más de un vértice común.

Sin embargo, no hay ningún límite superior que no sea el trivial $n2^{\frac{n(n-1)}{2}}$ es actualmente conocido por mí.

Answer 1

En "Asymptotically optimal induced universal graphs" de Noga Alon se demuestra que el tamaño mínimo posible de un $n$ -el gráfico universal es $(1 + o(1))2^{\frac{n - 1}{2}}$ .

Además, allí también se demuestra que si $\Gamma$ es un $n$ -vértices Grafo aleatorio de Erdos-Renyi con probabilidad de aristas $\frac{1}{2}$ , entonces es $k$ -universal con probabilidad $(1 - e^{-C_n^k 2^{-\frac{k(k-1)}{2}}})^2 + o(1)$