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.