Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Near-optimum Universal Graphs for Graphs with Bounded Degrees

Extended Abstract

  • Conference paper
  • First Online:

Abstract

Let\( \mathcal{H} \) be a family of graphs. We say thatG is\( \mathcal{H} \)-universal if, for eachH ∈\( \mathcal{H} \), the graphG contains a subgraph isomorphic toH. Let\( \mathcal{H} \) (k, n) denote the family of graphs onn vertices with maximum degree at mostk. For each fixedk and eachn sufficiently large, we explicitly construct an\( \mathcal{H} \) (k, n)-universal graphΓ(k, n) withO(n2 - 2/k (logn)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\( \mathcal{H} \)(k, n)-universal. So we use the probabilistic method to prove that anexplicit construction satisfies certain properties, rather than showing theexistence of a construction that satisfies these properties.

Partially supported by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.

Partially supported by MCT/CNPq through ProNEx Proj. 107/97 (Proc. CNPq 664107/1997-4), by CNPq (Proc. 300334/93-1, 468516/2000-0, and 910064/99-7), and by FAPESP (Proj. 96/04505-2).

Partially supported by NSF grants DMS 0071261 and INT 0072064.

Supported by KBN grant 2 P03A 032 16. Part of this research was done during the fifth author’s visit to Emory University.

Partially supported by the NSF.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. N. Alon and V. Asodi, Sparse universal graphs,Journal of Computational and Applied Mathematics, to appear.

    Google Scholar 

  2. N. Alon, M. Capalbo, Y. Kohayakawa, V. Rödl, A. Ruciński, and E. Szemerédi, Universality and tolerance,Proceedings of the 41st IEEE Annual Symposium on FOCS, pp. 14–21, 2000.

    Google Scholar 

  3. L. Babai, F. R. K. Chung, P. Erdos, R. L. Graham, J. Spencer, On graphs which contain all sparse graphs,Ann. Discrete Math., 12 (1982), pp. 21–26.

    MATH MathSciNet  Google Scholar 

  4. S. N. Bhatt, F. Chung, F. T. Leighton and A. Rosenberg, Universal graphs for bounded-degree trees and planar graphs,SI AM J. Disc. Math. 2 (1989), 145–155.

    Article MATH MathSciNet  Google Scholar 

  5. S. N. Bhatt and E. Leiserson, How to assemble tree machines,Advances in Computing Research, F. Preparata, ed., 1984.

    Google Scholar 

  6. M. Capalbo, A small universal graph for bounded-degree planar graphs,SODA (1999), 150–154.

    Google Scholar 

  7. F. R. K. Chung and R. L. Graham, On graphs which contain all small trees,J. Combin. Theory Ser. B, 24 (1978) pp. 14–23.

    Article MATH MathSciNet  Google Scholar 

  8. F. R. K. Chung and R. L. Graham, On universal graphs,Ann. New York Acad. Sci., 319 (1979) pp. 136–140.

    Article MathSciNet  Google Scholar 

  9. F. R. K. Chung and R. L. Graham, On universal graphs for spanning trees,Proc. London Math. Soc., 27 (1983) pp. 203–211.

    Article MATH MathSciNet  Google Scholar 

  10. F. R. K. Chung, R. L. Graham, and N. Pippenger, On graphs which contain all small trees II,Proc. 1976 Hungarian Colloquium on Combinatorics, 1978, pp. 213–223.

    Google Scholar 

  11. M. Capalbo and S. R. Kosaraju, Small universal graphs,STOC (1999), 741–749.

    Google Scholar 

  12. F. R. K. Chung, A. L. Rosenberg, and L. Snyder, Perfect storage representations for families of data structures,SI AM J. Alg. Disc. Methods., 4 (1983), pp. 548–565.

    Article MATH MathSciNet  Google Scholar 

  13. J. Friedman and N. Pippenger, Expanding graphs contain all small trees,Combi-natorica,7 (1987), pp. 71–76.

    MATH MathSciNet  Google Scholar 

  14. A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdos, inCombinatorial Theory and its Applications, Vol. II (P. Erdos, A. Rényi, and V. T. Sós, eds.), Colloq. Math Soc. J. Bolyai 4, North Holland, Amsterdam 1970, 601–623.

    Google Scholar 

  15. L. Lovász and M. D. Plummer,Matching Theory, North Holland, Amsterdam (1986).

    MATH  Google Scholar 

  16. V. Rödl, A note on universal graphs,Ars Combin., 11 (1981), 225–229.

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel

    Noga Alon

  2. Department of Mathematical Sciences, The Johns Hopkins University, 3400, N. Charles Street, Baltimore, MD

    Michael Capalbo

  3. Instituto de Matemática e Estatýstica, Universidade de São Paulo, Brazil

    Yoshiharu Kohayakawa

  4. Department of Mathematics and Computer Science, Emory University, Atlanta

    Vojtěch Rödl

  5. Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland

    Andrzej Ruciński

  6. Department of Computer Science, Rutgers University, NJ

    Endre Szemerédi

Authors
  1. Noga Alon

    You can also search for this author inPubMed Google Scholar

  2. Michael Capalbo

    You can also search for this author inPubMed Google Scholar

  3. Yoshiharu Kohayakawa

    You can also search for this author inPubMed Google Scholar

  4. Vojtěch Rödl

    You can also search for this author inPubMed Google Scholar

  5. Andrzej Ruciński

    You can also search for this author inPubMed Google Scholar

  6. Endre Szemerédi

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics, Massachusetts Institute of Technology, MIT, Cambridge, MA, 02139, USA

    Michel Goemans

  2. Institute for Computer Science and Applied Mathematics, University of Kiel, Olshausenstr. 40, 24098, Kiel, Germany

    Klaus Jansen

  3. Centre Universitaire d’Informatique, Université de Genéve, 24, Rue General Dufour, 1211, Genéve 4, Switzerland

    José D. P. Rolim

  4. Computer Science Division, University of California at Berkeley, 615 Soda Hall, Berkeley, CA, 94720-1776, USA

    Luca Trevisan

Rights and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Alon, N., Capalbo, M., Kohayakawa, Y., Rödl, V., Ruciński, A., Szemerédi, E. (2001). Near-optimum Universal Graphs for Graphs with Bounded Degrees. In: Goemans, M., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds) Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques. RANDOM APPROX 2001 2001. Lecture Notes in Computer Science, vol 2129. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44666-4_20

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp