# 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

## Access Full Article

top## Abstract

top## How to cite

topDonadelli, 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- N. Alon and F.R.K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math.72 (1988) 15–19. Zbl0657.05068
- N. Alon, Subdivided graphs have linear Ramsey numbers. J. Graph Theory18 (1994) 343–347. Zbl0811.05046
- 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
- J. Beck, On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory7 (1983) 115–129. Zbl0508.05047
- 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
- 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
- R. Diestel, Graph theory. Springer-Verlag, New York (1997). Translated from the 1996 German original.
- 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
- 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.
- 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
- J. Friedman and N. Pippenger, Expanding graphs contain all small trees. Combinatorica7 (1987) 71–76. Zbl0624.05028
- P.E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles. J. Combin. Theory Ser. B69 (1997) 210–218. Zbl0867.05022
- P.E. Haxell and Y. Kohayakawa, The size-Ramsey number of trees. Israel J. Math.89 (1995) 261–274. Zbl0822.05049
- P.E. Haxell, Y. Kohayakawa and T. Łuczak, The induced size-Ramsey number of cycles. Combin. Probab. Comput.4 (1995) 217–239. Zbl0839.05073
- P.E. Haxell and T. Łuczak, Embedding trees into graphs of large girth. Discrete Math.216 (2000) 273–278. Zbl0958.05030
- 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
- T. Jiang, On a conjecture about trees in graphs with large girth. J. Combin. Theory Ser. B83 (2001) 221–232. Zbl1023.05035
- Xin Ke, The size Ramsey number of trees with bounded degree. Random Structures Algorithms4 (1993) 85–97. Zbl0778.05060
- 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
- Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs. I. Random Structures Algorithms22 (2003) 359–434. Zbl1022.05076
- 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
- A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs. Combinatorica8 (1988) 261–277. Zbl0661.05035
- 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.
- I. Pak, Mixing time and long paths in graphs, manuscript available at (June 2001). URIhttp://www-math.mit.edu/~pak/research.html#r
- 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
- O. Pikhurko, Asymptotic size Ramsey results for bipartite graphs. SIAM J. Discrete Math.16 (2002) 99–113 (electronic). Zbl1029.05103
- O. Pikhurko, Size Ramsey numbers of stars versus 4-chromatic graphs. J. Graph Theory42 (2003) 220–233. Zbl1013.05052
- L. Pósa, Hamiltonian circuits in random graphs. Discrete Math.14 (1976) 359–364. Zbl0322.05127
- D. Reimer, The Ramsey size number of dipaths. Discrete Math.257 (2002) 173–175. Zbl1012.05116
- V. Rödl and E. Szemerédi, On size Ramsey numbers of graphs with bounded degree. Combinatorica20 (2000) 257–262. Zbl0959.05076
- 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 ?

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