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.

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

• scientific article; zbMATH DE number 5764887 (Why is no real title available?)
• scientific article; zbMATH DE number 1833411 (Why is no real title available?)
• 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
• 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

(6)

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

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)