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

Jair Donadelli; Penny E. Haxell; Yoshiharu Kohayakawa

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

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

Abstract

top
Let T s H 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 T s H .

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 - Informatique Théorique et Applications 39.1 (2005): 191-206. <http://eudml.org/doc/245047>.

@article{Donadelli2005,
abstract = {Let $T_sH$ 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 $T_sH$.},
author = {Donadelli, Jair, Haxell, Penny E., Kohayakawa, Yoshiharu},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {The Size-Ramsey number; Ramsey theory; expanders; Ramanujan graphs; explicit constructions},
language = {eng},
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/245047},
volume = {39},
year = {2005},
}

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 - Informatique Théorique et Applications
PY - 2005
PB - EDP-Sciences
VL - 39
IS - 1
SP - 191
EP - 206
AB - Let $T_sH$ 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 $T_sH$.
LA - eng
KW - The Size-Ramsey number; Ramsey theory; expanders; Ramanujan graphs; explicit constructions
UR - http://eudml.org/doc/245047
ER -

References

top
  1. [1] N. Alon and F.R.K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math. 72 (1988) 15–19. Zbl0657.05068
  2. [2] N. Alon, Subdivided graphs have linear Ramsey numbers. J. Graph Theory 18 (1994) 343–347. Zbl0811.05046
  3. [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.) Zbl0767.05001MR1885388
  4. [4] J. Beck, On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory 7 (1983) 115–129. Zbl0508.05047
  5. [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. [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. B 34 (1983) 239–243. Zbl0547.05044
  7. [7] R. Diestel, Graph theory. Springer-Verlag, New York (1997). Translated from the 1996 German original. Zbl0873.05001MR1411445
  8. [8] P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, The size Ramsey number. Periodica Mathematica Hungarica 9 (1978) 145–161. Zbl0331.05122
  9. [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 Bolyai 10 (1975) 515–527. Zbl0324.05124
  10. [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. [11] J. Friedman and N. Pippenger, Expanding graphs contain all small trees. Combinatorica 7 (1987) 71–76. Zbl0624.05028
  12. [12] P.E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles. J. Combin. Theory Ser. B 69 (1997) 210–218. Zbl0867.05022
  13. [13] P.E. Haxell and Y. Kohayakawa, The size-Ramsey number of trees. Israel J. Math. 89 (1995) 261–274. Zbl0822.05049
  14. [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. [15] P.E. Haxell and T. Łuczak, Embedding trees into graphs of large girth. Discrete Math. 216 (2000) 273–278. Zbl0958.05030
  16. [16] P.E. Haxell, T. Łuczak and P.W. Tingley, Ramsey numbers for trees of small maximum degree. Combinatorica 22 (2002) 287–320. Special issue: Paul Erdős and his mathematics. Zbl0997.05065
  17. [17] T. Jiang, On a conjecture about trees in graphs with large girth. J. Combin. Theory Ser. B 83 (2001) 221–232. Zbl1023.05035
  18. [18] Xin Ke, The size Ramsey number of trees with bounded degree. Random Structures Algorithms 4 (1993) 85–97. Zbl0778.05060
  19. [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. [20] Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs. I. Random Structures Algorithms 22 (2003) 359–434. Zbl1022.05076
  21. [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. [22] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs. Combinatorica 8 (1988) 261–277. Zbl0661.05035
  23. [23] G.A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii 24 (1988) 51–60. Zbl0708.05030
  24. [24] I. Pak, Mixing time and long paths in graphs, manuscript available at http://www-math.mit.edu/~pak/research.html#r (June 2001). Zbl1056.05135
  25. [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. [26] O. Pikhurko, Asymptotic size Ramsey results for bipartite graphs. SIAM J. Discrete Math. 16 (2002) 99–113 (electronic). Zbl1029.05103
  27. [27] O. Pikhurko, Size Ramsey numbers of stars versus 4-chromatic graphs. J. Graph Theory 42 (2003) 220–233. Zbl1013.05052
  28. [28] L. Pósa, Hamiltonian circuits in random graphs. Discrete Math. 14 (1976) 359–364. Zbl0322.05127
  29. [29] D. Reimer, The Ramsey size number of dipaths. Discrete Math. 257 (2002) 173–175. Zbl1012.05116
  30. [30] V. Rödl and E. Szemerédi, On size Ramsey numbers of graphs with bounded degree. Combinatorica 20 (2000) 257–262. Zbl0959.05076
  31. [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. Zbl0413.05055

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.