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.
@article{10_37236_5562,
author = {Samuel Hetterich and Olaf Parczyk and Yury Person},
title = {On universal hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {4},
doi = {10.37236/5562},
zbl = {1351.05162},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5562/}
}
TY - JOUR
AU - Samuel Hetterich
AU - Olaf Parczyk
AU - Yury Person
TI - On universal hypergraphs
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/5562/
DO - 10.37236/5562
ID - 10_37236_5562
ER -
%0 Journal Article
%A Samuel Hetterich
%A Olaf Parczyk
%A Yury Person
%T On universal hypergraphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/5562/
%R 10.37236/5562
%F 10_37236_5562
Samuel Hetterich; Olaf Parczyk; Yury Person. On universal hypergraphs. The electronic journal of combinatorics, Tome 23 (2016) no. 4. doi: 10.37236/5562
