On universal hypergraphs

MaRDI QIDQ727206zbMATH OpenFDO

Authors Samuel Hetterich, O. Parczyk, Yury Person

Publication date 6 December 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.03983, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p28

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

hypergraphsuniversality

Mathematics Subject Classification ID

Hypergraphs (05C65)

Abstract: A hypergraph $H$ is called universal for a family $mathcalF$ of hypergraphs, if it contains every hypergraph $FinmathcalF$ 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, $rmidDelta$ 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.

Review text

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.

Recommendations

• Induced universal hypergraphs
• scientific article; zbMATH DE number 1833411
• Sparse universal graphs for bounded‐degree graphs
• Spanning structures and universality in sparse hypergraphs
• The research of the existence of universal hypergraphs

Cites work

• Almost-spanning universality in random graphs
• An improved upper bound on the density of universal random graphs
• Approximate counting of regular hypergraphs
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• scientific article; zbMATH DE number 5764887 (Why is no real title available?)
• scientific article; zbMATH DE number 1833411 (Why is no real title available?)
• On Graphs Which Contain All Sparse Graphs
• Ramanujan graphs
• Spanning structures and universality in sparse hypergraphs
• Sparse universal graphs
• Sparse universal graphs for bounded‐degree graphs
• Universality of Random Graphs for Graphs of Maximum Degree Two
• Universality, tolerance, chaos and order

Cited in

(7)

• The research of the existence of universal hypergraphs
• Induced universal hypergraphs
• scientific article; zbMATH DE number 4117862 (Why is no real title available?)
• On unavoidable hypergraphs
• scientific article; zbMATH DE number 7101992 (Why is no real title available?)
• Universal and unavoidable graphs
• Some remarks on universal graphs

This page was built for publication: On universal hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727206)