Bounds for Hypergraph Universality

Abstract

A graph $\hat{I}“$ is said to be universal for a class of graphs $\mathcal{H}$ if $\hat{I}“$ contains a copy of every $H\in \mathcal{H}$ as a subgraph. The number of edges required for a host graph $\hat{I}“$ to be universal for the class of $D$-degenerate graphs on $n$ vertices has been shown to be $O(n^{2-1/D}(\log n{)}^{2/D}(\log \log n{)}^5)$. We generalise this result to $r$-uniform hypergraphs, showing the following. Given $D,r\ge 2$ and $n$ sufficiently large, there exists a constant $C=C(D,r)$ such that there exists a graph with at most \[Cn^{r-1/D}(\log n)^{2/D}(\log\log n)^{2r+1}\] edges which is universal for the class of $D$-degenerate $r$-uniform hypergraphs on $n$ vertices. This is tight up to the polylogarithmic term.