Universality for graphs with bounded density

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 O d ( n 2 − 1 / ( ⌈ d ⌉ + 1 ) ) edges which contains every n -vertex graph with density at most d ∈ Q ( d ≥ 1 ), which is close to a Ω ( n 2 − 1 / d ) lower bound obtained by counting lifts of a carefully chosen (small) graph. When restricting the maximum degree of such graphs to be constant, we obtain near-optimal universality. If we further assume d ∈ N , we get an asymptotically optimal construction.