Near-optimum universal graphs for graphs with bounded degrees (Extended abstract)

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

Let H be a family of graphs. We say that G is H-universal if, for each H ∈H, the graph G contains a subgraph isomorphic to H. Let H(k, n) denote the family of graphs on n vertices with maximum degree at most k. For each fixed k and each n sufficiently large, we explicitly construct an H(k, n)-universal graph Γ(k, n) with O(n2−2/k(log n)1+8/k) edges. This is optimal up to a small polylogarithmic factor, as Ω(n2−2/k) is a lower bound for the number of edges in any such graph. En route, we use the probabilistic method in a rather unusual way. After presenting a deterministic construction of the graph Γ(k, n), we prove, using a probabilistic argument, that Γ(k, n) is H(k, n)-universal. So we use the probabilistic method to prove that an explicit construction satisfies certain properties, rather than showing the existence of a construction that satisfies these properties.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings
EditorsLuca Trevisan, Klaus Jansen, Michel Goemans, Jose D. P. Rolim
PublisherSpringer Verlag
Pages170-180
Number of pages11
ISBN (Electronic)3540424709
StatePublished - Jan 1 2015
Externally publishedYes
Event4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 - Berkeley, United States
Duration: Aug 18 2001Aug 20 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2129
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001
CountryUnited States
CityBerkeley
Period8/18/018/20/01

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Near-optimum universal graphs for graphs with bounded degrees (Extended abstract)'. Together they form a unique fingerprint.

Cite this