2023/11/09 by Noga Alon, Natalie Dodson, Alon, Noga +7 · 1 citation
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2311.05500
openalex publication_date 2023/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is universal for a (finite) family H of graphs if every H ∈ H is a subgraph of G. For a given family H, the goal is to determine the smallest number of edges an H-universal graph can have. With the aim of unifying a number of recent results, we consider a family of graphs with bounded density. In particular, we construct a graph with Od( n2 - 1/(\lceil d \rceil + 1) ) edges which contains every n-vertex graph with density at most d ∈ ℚ (d ≥ 1), which is close to a lower bound Ω(n2 - 1/d - o(1)) obtained by counting lifts of a carefully chosen (small) graph. When restricting the maximum degree of such graphs to be constant, we obtain a near-optimal universality. If we further assume d ∈ ℕ, we get an asymptotically optimal construction.