Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-27T08:03:35.166Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  15 March 2005

Jair Donadelli ,
Penny E. Haxell  and
Yoshiharu Kohayakawa
Jair Donadelli
Affiliation:
Departamento de Informática, Universidade Federal do Paraná, Centro Politécnico Caixa Postal 19081, 81531-980 Curitiba PR, Brasil; e-mail: 
Penny E. Haxell
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada; e-mail: 
Yoshiharu Kohayakawa
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo SP, Brasil; e-mail: 
Get access

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.

Keywords

The Size-Ramsey numberRamsey theoryexpandersRamanujan graphsexplicit constructions.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 39 , Issue 1: Imre Simon, the tropical computer scientist , January 2005 , pp. 191 - 206
Copyright
© EDP Sciences, 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alon, N. and Chung, F.R.K., Explicit construction of linear sized tolerant networks. Discrete Math. 72 (1988) 15–19. CrossRef
Alon, N., Subdivided graphs have linear Ramsey numbers. J. Graph Theory 18 (1994) 343–347. CrossRef
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.)
Beck, J., On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory 7 (1983) 115–129. CrossRef
J. Beck, On size Ramsey number of paths, trees and circuits. II. Mathematics of Ramsey theory, Springer, Berlin, Algorithms Combin. 5 (1990) 34–45.
Chvátal, V., Rödl, V., Szemerédi, E. and Trotter Jr, W.T.., The Ramsey number of a graph with bounded maximum degree. J. Combin. Theory Ser. B 34 (1983) 239–243. CrossRef
R. Diestel, Graph theory. Springer-Verlag, New York (1997). Translated from the 1996 German original.
Erdős, P., Faudree, R.J., Rousseau, C.C. and Schelp, R.H., The size Ramsey number. Periodica Mathematica Hungarica 9 (1978) 145–161. CrossRef
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.
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.
Friedman, J. and Pippenger, N., Expanding graphs contain all small trees. Combinatorica 7 (1987) 71–76. CrossRef
Haxell, P.E., Partitioning complete bipartite graphs by monochromatic cycles. J. Combin. Theory Ser. B 69 (1997) 210–218. CrossRef
Haxell, P.E. and Kohayakawa, Y., The size-Ramsey number of trees. Israel J. Math. 89 (1995) 261–274. CrossRef
Haxell, P.E., Kohayakawa, Y. and Łuczak, T., The induced size-Ramsey number of cycles. Combin. Probab. Comput. 4 (1995) 217–239. CrossRef
Haxell, P.E. and Łuczak, T., Embedding trees into graphs of large girth. Discrete Math. 216 (2000) 273–278. CrossRef
Haxell, P.E., Łuczak, T. and Tingley, P.W., Ramsey numbers for trees of small maximum degree. Combinatorica 22 (2002) 287–320. Special issue: Paul Erdős and his mathematics. CrossRef
Jiang, T., On a conjecture about trees in graphs with large girth. J. Combin. Theory Ser. B 83 (2001) 221–232. CrossRef
Xin, Ke, The size Ramsey number of trees with bounded degree. Random Structures Algorithms 4 (1993) 85–97.
Y. Kohayakawa, Szemerédi's regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997). Springer, Berlin (1997) 216–230.
Kohayakawa, Y. and Rödl, V., Regular pairs in sparse random graphs. I. Random Structures Algorithms 22 (2003) 359–434. CrossRef
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.
Lubotzky, A., Phillips, R. and Sarnak, P., Ramanujan graphs. Combinatorica 8 (1988) 261–277. CrossRef
Margulis, G.A., Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii 24 (1988) 51–60.
I. Pak, Mixing time and long paths in graphs, manuscript available at http://www-math.mit.edu/~pak/research.html#r (June 2001).
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.
Pikhurko, O., Asymptotic size Ramsey results for bipartite graphs. SIAM J. Discrete Math. 16 (2002) 99–113 (electronic). CrossRef
Pikhurko, O., Size Ramsey numbers of stars versus 4-chromatic graphs. J. Graph Theory 42 (2003) 220–233. CrossRef
Pósa, L., Hamiltonian circuits in random graphs. Discrete Math. 14 (1976) 359–364. CrossRef
Reimer, D., The Ramsey size number of dipaths. Discrete Math. 257 (2002) 173–175. CrossRef
Rödl, V. and Szemerédi, E., On size Ramsey numbers of graphs with bounded degree. Combinatorica 20 (2000) 257–262.
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.