TY - GEN
T1 - Near-optimum universal graphs for graphs with bounded degrees (Extended abstract)
AU - Alon, Noga
AU - Capalbo, Michael
AU - Kohayakawa, Yoshiharu
AU - Rödl, Vojtěch
AU - Ruciński, Andrzej
AU - Szemerédi, Endre
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84923070422&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84923070422&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84923070422
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 170
EP - 180
BT - Approximation, Randomization, and Combinatorial Optimization
A2 - Trevisan, Luca
A2 - Jansen, Klaus
A2 - Goemans, Michel
A2 - Rolim, Jose D. P.
PB - Springer Verlag
T2 - 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
Y2 - 18 August 2001 through 20 August 2001
ER -