A graph $G$ is $\textit{ universal}$ for a (finite) family $\mathcal{ H}$ of graphs if every $H \in \mathcal{ H}$ is a subgraph of $G$. For a given family $\mathcal{ H}$, the goal is to determine the smallest number of edges an $\mathcal{ 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\left( n^{ 2 - 1/(\lceil d \rceil + 1)} \right)$ edges which contains every $n$-vertex graph with density at most $d \in \mathbb{ Q}$ ($d \ge 1$), which is close to a lower bound $\Omega(n^{ 2 - 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 \in \mathbb{ N}$, we get an asymptotically optimal construction.
Categories: math.CO