On universal hypergraphs (Q727206)

Summary: 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 \textit{N. Alon} and \textit{M. Capalbo} [Random Struct. Algorithms 31, No. 2, 12--133 (2007; Zbl 1133.05095)] 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 \textit{N. Alon} and \textit{V. Asodi} [J. Comput. Appl. Math. 142, No.1, 1--11 (2002; Zbl 0997.05047)] about optimal universal graphs for the family of graphs with at most \(m\) edges and no isolated vertices to hypergraphs.