### 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(n^{2−2/k}(log n)^{1+8/k}) edges. This is optimal up to a small polylogarithmic factor, as Ω(n^{2−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 language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms 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 |

Editors | Luca Trevisan, Klaus Jansen, Michel Goemans, Jose D. P. Rolim |

Publisher | Springer Verlag |

Pages | 170-180 |

Number of pages | 11 |

ISBN (Electronic) | 3540424709 |

State | Published - Jan 1 2015 |

Externally published | Yes |

Event | 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 - Berkeley, United States Duration: Aug 18 2001 → Aug 20 2001 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2129 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 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 |
---|---|

Country | United States |

City | Berkeley |

Period | 8/18/01 → 8/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

*Approximation, Randomization, and Combinatorial Optimization: Algorithms 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*(pp. 170-180). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2129). Springer Verlag.