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.  
  2. N. Alon, Subdivided graphs have linear Ramsey numbers. J. Graph Theory18 (1994) 343–347.  
  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.)  
  4. J. Beck, On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory7 (1983) 115–129.  
  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.  
  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.  
  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.  
  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.  
  11. J. Friedman and N. Pippenger, Expanding graphs contain all small trees. Combinatorica7 (1987) 71–76.  
  12. P.E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles. J. Combin. Theory Ser. B69 (1997) 210–218.  
  13. P.E. Haxell and Y. Kohayakawa, The size-Ramsey number of trees. Israel J. Math.89 (1995) 261–274.  
  14. P.E. Haxell, Y. Kohayakawa and T. Łuczak, The induced size-Ramsey number of cycles. Combin. Probab. Comput.4 (1995) 217–239.  
  15. P.E. Haxell and T. Łuczak, Embedding trees into graphs of large girth. Discrete Math.216 (2000) 273–278.  
  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.  
  17. T. Jiang, On a conjecture about trees in graphs with large girth. J. Combin. Theory Ser. B83 (2001) 221–232.  
  18. Xin Ke, The size Ramsey number of trees with bounded degree. Random Structures Algorithms4 (1993) 85–97.  
  19. Y. Kohayakawa, Szemerédi's regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997). Springer, Berlin (1997) 216–230.  
  20. Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs. I. Random Structures Algorithms22 (2003) 359–434.  
  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.  
  22. A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs. Combinatorica8 (1988) 261–277.  
  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.  
  26. O. Pikhurko, Asymptotic size Ramsey results for bipartite graphs. SIAM J. Discrete Math.16 (2002) 99–113 (electronic).  
  27. O. Pikhurko, Size Ramsey numbers of stars versus 4-chromatic graphs. J. Graph Theory42 (2003) 220–233.  
  28. L. Pósa, Hamiltonian circuits in random graphs. Discrete Math.14 (1976) 359–364.  
  29. D. Reimer, The Ramsey size number of dipaths. Discrete Math.257 (2002) 173–175.  
  30. V. Rödl and E. Szemerédi, On size Ramsey numbers of graphs with bounded degree. Combinatorica20 (2000) 257–262.  
  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.