Universality and tolerance

Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rodl, Andrzej Ruciński, Endre Szemerédi

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


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 Ω(n2-2/r) edges. On the other hand, for any n ≥n0(r), we explicitly construct H(r, n)-universal graphs G and Λ on n and 2n vertices, and with O(n2-Ω(1/r log r)) and O(n2-1/r log1/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 log1/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].

Original languageEnglish (US)
Pages (from-to)14-21
Number of pages8
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this