On universal 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^{r-r/\Delta })$ many edges. We exploit constructions of Alon and Capalbo to obtain universal $r$-uniform hypergraphs with the optimal number of edges $O(n^{r-r/\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.

12 pages, paper substantially rewritten, addition of new results

References in corpus (1)

• Almost-spanning universality in random graphs