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

Donadelli, Jair ; Haxell, Penny E. ; Kohayakawa, Yoshiharu

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005), p. 191-206 / Harvested from Numdam

Résumé

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$.

Détail

Publié le : 2005-01-01

MR 2132587 | Zbl 1075.05054

DOI : https://doi.org/10.1051/ita:2005019
Classification:  05C55,  05D40

Bibliographie

[1] N. Alon and F.R.K. Chung, Explicit construction of linear sized tolerant networks. Discrete Math. 72 (1988) 15-19. | Zbl 0657.05068

[2] N. Alon, Subdivided graphs have linear Ramsey numbers. J. Graph Theory 18 (1994) 343-347. | Zbl 0811.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.) | MR 1885388 | Zbl 0767.05001

[4] J. Beck, On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory 7 (1983) 115-129. | Zbl 0508.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. | Zbl 0735.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. B 34 (1983) 239-243. | Zbl 0547.05044

[7] R. Diestel, Graph theory. Springer-Verlag, New York (1997). Translated from the 1996 German original. | MR 1411445 | Zbl 0873.05001

[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. | Zbl 0331.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 Bolyai 10 (1975) 515-527. | Zbl 0324.05124

[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. | Zbl 1027.05069

[11] J. Friedman and N. Pippenger, Expanding graphs contain all small trees. Combinatorica 7 (1987) 71-76. | Zbl 0624.05028

[12] P.E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles. J. Combin. Theory Ser. B 69 (1997) 210-218. | Zbl 0867.05022

[13] P.E. Haxell and Y. Kohayakawa, The size-Ramsey number of trees. Israel J. Math. 89 (1995) 261-274. | Zbl 0822.05049

[14] P.E. Haxell, Y. Kohayakawa and T. Łuczak, The induced size-Ramsey number of cycles. Combin. Probab. Comput. 4 (1995) 217-239. | Zbl 0839.05073

[15] P.E. Haxell and T. Łuczak, Embedding trees into graphs of large girth. Discrete Math. 216 (2000) 273-278. | Zbl 0958.05030

[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. | Zbl 0997.05065

[17] T. Jiang, On a conjecture about trees in graphs with large girth. J. Combin. Theory Ser. B 83 (2001) 221-232. | Zbl 1023.05035

[18] Xin Ke, The size Ramsey number of trees with bounded degree. Random Structures Algorithms 4 (1993) 85-97. | Zbl 0778.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. | Zbl 0868.05042

[20] Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs. I. Random Structures Algorithms 22 (2003) 359-434. | Zbl 1022.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. | Zbl 1023.05108

[22] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs. Combinatorica 8 (1988) 261-277. | Zbl 0661.05035

[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. | Zbl 0708.05030

[24] I. Pak, Mixing time and long paths in graphs, manuscript available at http://www-math.mit.edu/~pak/research.html#r (June 2001).

[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. | Zbl 1056.05135

[26] O. Pikhurko, Asymptotic size Ramsey results for bipartite graphs. SIAM J. Discrete Math. 16 (2002) 99-113 (electronic). | Zbl 1029.05103

[27] O. Pikhurko, Size Ramsey numbers of stars versus 4-chromatic graphs. J. Graph Theory 42 (2003) 220-233. | Zbl 1013.05052

[28] L. Pósa, Hamiltonian circuits in random graphs. Discrete Math. 14 (1976) 359-364. | Zbl 0322.05127

[29] D. Reimer, The Ramsey size number of dipaths. Discrete Math. 257 (2002) 173-175. | Zbl 1012.05116

[30] V. Rödl and E. Szemerédi, On size Ramsey numbers of graphs with bounded degree. Combinatorica 20 (2000) 257-262. | Zbl 0959.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. | Zbl 0413.05055