A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli; Penny E. Haxell; Yoshiharu Kohayakawa

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 39, Issue: 1, page 191-206
  • ISSN: 0988-3754

Abstract

top
Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH.

How to cite

top

Donadelli, Jair, Haxell, Penny E., and Kohayakawa, Yoshiharu. "A note on the Size-Ramsey number of long subdivisions of graphs." RAIRO - Theoretical Informatics and Applications 39.1 (2010): 191-206. <http://eudml.org/doc/92755>.

@article{Donadelli2010,
abstract = { Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH. },
author = {Donadelli, Jair, Haxell, Penny E., Kohayakawa, Yoshiharu},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {The Size-Ramsey number; Ramsey theory; expanders; Ramanujan graphs; explicit constructions.},
language = {eng},
month = {3},
number = {1},
pages = {191-206},
publisher = {EDP Sciences},
title = {A note on the Size-Ramsey number of long subdivisions of graphs},
url = {http://eudml.org/doc/92755},
volume = {39},
year = {2010},
}

TY - JOUR
AU - Donadelli, Jair
AU - Haxell, Penny E.
AU - Kohayakawa, Yoshiharu
TI - A note on the Size-Ramsey number of long subdivisions of graphs
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 39
IS - 1
SP - 191
EP - 206
AB - Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH.
LA - eng
KW - The Size-Ramsey number; Ramsey theory; expanders; Ramanujan graphs; explicit constructions.
UR - http://eudml.org/doc/92755
ER -

References

top
  1. N. Alon and F.R.K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math.72 (1988) 15–19.  Zbl0657.05068
  2. N. Alon, Subdivided graphs have linear Ramsey numbers. J. Graph Theory18 (1994) 343–347.  Zbl0811.05046
  3. N. Alon and J.H. Spencer, The probabilistic method, 2nd edition, Ser. Discrete Math.Optim., Wiley-Interscience, John Wiley & Sons, New York, 2000. (With an appendix on the life and work of Paul Erdős.)  Zbl0996.05001
  4. J. Beck, On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory7 (1983) 115–129.  Zbl0508.05047
  5. J. Beck, On size Ramsey number of paths, trees and circuits. II. Mathematics of Ramsey theory, Springer, Berlin, Algorithms Combin.5 (1990) 34–45.  Zbl0735.05056
  6. V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter Jr., The Ramsey number of a graph with bounded maximum degree. J. Combin. Theory Ser. B34 (1983) 239–243.  Zbl0547.05044
  7. R. Diestel, Graph theory. Springer-Verlag, New York (1997). Translated from the 1996 German original.  
  8. P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, The size Ramsey number. Periodica Mathematica Hungarica9 (1978) 145–161.  Zbl0331.05122
  9. P. Erdős and R.L. Graham, On partition theorems for finite graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I. North-Holland, Amsterdam, Colloq. Math. Soc. János Bolyai10 (1975) 515–527.  
  10. R.J. Faudree and R.H. Schelp, A survey of results on the size Ramsey number, Paul Erdős and his mathematics, II (Budapest, 1999). Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest 11 (2002) 291–309.  Zbl1027.05069
  11. J. Friedman and N. Pippenger, Expanding graphs contain all small trees. Combinatorica7 (1987) 71–76.  Zbl0624.05028
  12. P.E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles. J. Combin. Theory Ser. B69 (1997) 210–218.  Zbl0867.05022
  13. P.E. Haxell and Y. Kohayakawa, The size-Ramsey number of trees. Israel J. Math.89 (1995) 261–274.  Zbl0822.05049
  14. P.E. Haxell, Y. Kohayakawa and T. Łuczak, The induced size-Ramsey number of cycles. Combin. Probab. Comput.4 (1995) 217–239.  Zbl0839.05073
  15. P.E. Haxell and T. Łuczak, Embedding trees into graphs of large girth. Discrete Math.216 (2000) 273–278.  Zbl0958.05030
  16. P.E. Haxell, T. Łuczak and P.W. Tingley, Ramsey numbers for trees of small maximum degree. Combinatorica22 (2002) 287–320. Special issue: Paul Erdős and his mathematics.  Zbl0997.05065
  17. T. Jiang, On a conjecture about trees in graphs with large girth. J. Combin. Theory Ser. B83 (2001) 221–232.  Zbl1023.05035
  18. Xin Ke, The size Ramsey number of trees with bounded degree. Random Structures Algorithms4 (1993) 85–97.  Zbl0778.05060
  19. Y. Kohayakawa, Szemerédi's regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997). Springer, Berlin (1997) 216–230.  Zbl0868.05042
  20. Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs. I. Random Structures Algorithms22 (2003) 359–434.  Zbl1022.05076
  21. Y. Kohayakawa and V. Rödl, Szemerédi's regularity lemma and quasi-randomness, in Recent advances in algorithms and combinatorics. CMS Books Math./Ouvrages Math. SMC, Springer, New York 11 (2003) 289–351.  Zbl1023.05108
  22. A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs. Combinatorica8 (1988) 261–277.  Zbl0661.05035
  23. G.A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii24 (1988) 51–60.  
  24. I. Pak, Mixing time and long paths in graphs, manuscript available at (June 2001).  URIhttp://www-math.mit.edu/~pak/research.html#r
  25. I. Pak, Mixing time and long paths in graphs, in Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328.  Zbl1056.05135
  26. O. Pikhurko, Asymptotic size Ramsey results for bipartite graphs. SIAM J. Discrete Math.16 (2002) 99–113 (electronic).  Zbl1029.05103
  27. O. Pikhurko, Size Ramsey numbers of stars versus 4-chromatic graphs. J. Graph Theory42 (2003) 220–233.  Zbl1013.05052
  28. L. Pósa, Hamiltonian circuits in random graphs. Discrete Math.14 (1976) 359–364.  Zbl0322.05127
  29. D. Reimer, The Ramsey size number of dipaths. Discrete Math.257 (2002) 173–175.  Zbl1012.05116
  30. V. Rödl and E. Szemerédi, On size Ramsey numbers of graphs with bounded degree. Combinatorica20 (2000) 257–262.  Zbl0959.05076
  31. E. Szemerédi, Regular partitions of graphs, in Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). CNRS, Paris (1978) 399–401.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.