Hypergraph universality via branching random walks

Abstract

Given a family of hypergraphs $\mathcal{H}$, we say that a hypergraph $\Gamma$ is $\mathcal{H}$-universal if it contains every $H\in \mathcal{H}$ as a subgraph. For $D,r\in \mathbb{N}$, we construct an $r$-uniform hypergraph with $\Theta \left(n^{r-r/D}{\log }^{r/D}(n)\right)$ edges which is universal for the family of all $r$-uniform hypergraphs with $n$ vertices and maximum degree at most $D$. This almost matches a trivial lower bound $\Omega (n^{r-r/D})$ coming from the number of such hypergraphs. On a high level, we follow the strategy of Alon and Capalbo used in the graph case, that is $r=2$. The construction of $\Gamma$ is deterministic and based on a bespoke product of expanders, whereas showing that $\Gamma$ is universal is probabilistic. Two key new ingredients are a decomposition result for hypergraphs of bounded density, based on Edmond's matroid partitioning theorem, and a tail bound for branching random walks on expanders.

15 pages