Universality and tolerance

For any positive integers r and n, let H(r, n) denote the family of graphs on n vertices with maximum degree r, and let H(r, n, n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r, n)-universal graph must have Ω(n^2-2/r) edges. On the other hand, for any n ≥n₀(r), we explicitly construct H(r, n)-universal graphs G and Λ on n and 2n vertices, and with O(n^{2-Ω(1/r log r)}) and O(n^2-1/r log^1/r n)edges, respectively, such that we can efficiently find a copy of any H∈H(r, n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G = G(n, n, p), with p = cn^-1/2r log^1/2r n is fault-tolerant; for a large enough constant c, even after deleting any α-fraction of the edges of G, the resulting graph is still H(r, a(α)n, a(α)n)-universal for some a:[0, 1)→(0, 1].