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

### Authors:

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

### 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.

- Record ID
- UAM9d0b198cf500416e8702a2ae03e865e4
- Author
- Pages
- 170-180
- Book
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Lecture Notes in Computational Vision and Biomechanics, 2015, 170-180 p., ISBN 3540424709
- ASJC Classification
- ; ; ; ; ; ; ;
- Language
- en English
- Score (nominal)
- 0
- Score
- = 0.0, 19-03-2020, MonographChapterAuthor
- Publication indicators
- = 10.000; : 2015 = 0.618

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM9d0b198cf500416e8702a2ae03e865e4/

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perishopening in a new tab system.

Back