
Samuel Hetterich

Olaf Parczyk

Yury Person
Keywords:
Universality, Hypergraphs
Abstract
A hypergraph $H$ is called universal for a family $\mathcal{F}$ of hypergraphs, if it contains every hypergraph $F \in \mathcal{F}$ as a copy. For the family of $r$uniform hypergraphs with maximum vertex degree bounded by $\Delta$ and at most $n$ vertices any universal hypergraph has to contain $\Omega(n^{rr/\Delta})$ many edges. We exploit constructions of Alon and Capalbo to obtain universal $r$uniform hypergraphs with the optimal number of edges $O(n^{rr/\Delta})$ when $r$ is even, $r \mid \Delta$ or $\Delta=2$. Further we generalize the result of Alon and Asodi about optimal universal graphs for the family of graphs with at most $m$ edges and no isolated vertices to hypergraphs.