Universality for graphs with bounded density

Abstract

A graph $G$ is $\text{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.

14 pages, updated version focusing on density, with new title and additional author