Induced Universal Hypergraphs
Noga Alon, Nadav Sherman · SIAM Journal on Discrete Mathematics · 2019
We prove that the minimum number of vertices of a hypergraph that contains every $d$-uniform hypergraph on $k$ vertices as an induced subhypergraph is $(1+o(1))2^{\binom{k}{d}/k}$. The proof relies on the probabilistic method and provides a nonconstructive solution. In addition we exhibit an explicit construction of a hypergraph on $\Theta(2^{\binom{k}{d}/k})$ vertices, containing every $d$-uniform hypergraph on $k$ vertices as an induced subhypergraph.