2015/09/14 by Hetterich, Samuel, Parczyk, Olaf, Person, Yury · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1509.03983
A hypergraph H is called universal for a family F of hypergraphs, if it contains every hypergraph F ∈ F as a copy. For the family of r-uniform hypergraphs with maximum vertex degree bounded by Δ and at most n vertices any universal hypergraph has to contain Ω(nr-r/Δ) many edges. We exploit constructions of Alon and Capalbo to obtain universal r-uniform hypergraphs with the optimal number of edges O(nr-r/Δ) when r is even, r | Δ or Δ=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.