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

Alon, N. and Capalbo, M. and Kohayakawa, Y. and Rödl, V. and Ruciński, A. and Szemerédi, Endre (2015) Near-optimum universal graphs for graphs with bounded degrees (Extended abstract). In: Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. Lecture Notes in Computer Science (2129). Springer, Berlin; Heidelberg; New York, pp. 170-180. ISBN 978-3-540-42470-3

Preview

Text 61_1_u.pdf Download (208kB) | Preview

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. © Springer-Verlag Berlin Heidelberg 2001

Actions (login required)

Edit Item