2025/11/28 by Peter Allen, Julia Böttcher, Allen, Peter +2
Computer Science · Mathematics · #05C65 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2511.23341
openalex publication_date 2025/11/28 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28
A graph Γ is said to be universal for a class of graphs H if Γ contains a copy of every H ∈ H as a subgraph. The number of edges required for a host graph Γ to be universal for the class of D-degenerate graphs on n vertices has been shown to be O(n2-1/D(log n)2/D(loglog n)5). We generalise this result to r-uniform hypergraphs, showing the following. Given D, r ≥ 2 and n sufficiently large, there exists a constant C = C(D, r) such that there exists a graph with at most Cnr-1/D(log n)2/D(loglog n)2r+1 edges which is universal for the class of D-degenerate r-uniform hypergraphs on n vertices. This is tight up to the polylogarithmic term.