Let be the graph obtained from a given graph by subdividing each edge 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 , there exist graphs with edges that are Ramsey with respect to .
Mots-clés : The Size-Ramsey number, Ramsey theory, expanders, Ramanujan graphs, explicit constructions
@article{ITA_2005__39_1_191_0,
author = {Donadelli, Jair and Haxell, Penny E. and Kohayakawa, Yoshiharu},
title = {A note on the {Size-Ramsey} number of long subdivisions of graphs},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {191--206},
publisher = {EDP-Sciences},
volume = {39},
number = {1},
year = {2005},
doi = {10.1051/ita:2005019},
mrnumber = {2132587},
zbl = {1075.05054},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2005019/}
}
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 SP - 191 EP - 206 VL - 39 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2005019/ DO - 10.1051/ita:2005019 LA - en ID - ITA_2005__39_1_191_0 ER -
%0 Journal Article %A Donadelli, Jair %A Haxell, Penny E. %A Kohayakawa, Yoshiharu %T A note on the Size-Ramsey number of long subdivisions of graphs %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 191-206 %V 39 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2005019/ %R 10.1051/ita:2005019 %G en %F ITA_2005__39_1_191_0
Donadelli, Jair; Haxell, Penny E.; Kohayakawa, Yoshiharu. A note on the Size-Ramsey number of long subdivisions of graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 191-206. doi : 10.1051/ita:2005019. http://www.numdam.org/articles/10.1051/ita:2005019/
[1] and, Explicit construction of linear sized tolerant networks. Discrete Math. 72 (1988) 15-19. | Zbl
[2] , Subdivided graphs have linear Ramsey numbers. J. Graph Theory 18 (1994) 343-347. | Zbl
[3] and, 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 | Zbl
[4] , On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory 7 (1983) 115-129. | Zbl
[5] , On size Ramsey number of paths, trees and circuits. II. Mathematics of Ramsey theory, Springer, Berlin, Algorithms Combin. 5 (1990) 34-45. | Zbl
[6] ,, and, The Ramsey number of a graph with bounded maximum degree. J. Combin. Theory Ser. B 34 (1983) 239-243. | Zbl
[7] , Graph theory. Springer-Verlag, New York (1997). Translated from the 1996 German original. | MR | Zbl
[8] ,, and, The size Ramsey number. Periodica Mathematica Hungarica 9 (1978) 145-161. | Zbl
[9] and, 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
[10] and, 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
[11] and, Expanding graphs contain all small trees. Combinatorica 7 (1987) 71-76. | Zbl
[12] , Partitioning complete bipartite graphs by monochromatic cycles. J. Combin. Theory Ser. B 69 (1997) 210-218. | Zbl
[13] and, The size-Ramsey number of trees. Israel J. Math. 89 (1995) 261-274. | Zbl
[14] , and, The induced size-Ramsey number of cycles. Combin. Probab. Comput. 4 (1995) 217-239. | Zbl
[15] and, Embedding trees into graphs of large girth. Discrete Math. 216 (2000) 273-278. | Zbl
[16] , and, Ramsey numbers for trees of small maximum degree. Combinatorica 22 (2002) 287-320. Special issue: Paul Erdős and his mathematics. | Zbl
[17] , On a conjecture about trees in graphs with large girth. J. Combin. Theory Ser. B 83 (2001) 221-232. | Zbl
[18] Xin Ke, The size Ramsey number of trees with bounded degree. Random Structures Algorithms 4 (1993) 85-97. | Zbl
[19] , Szemerédi's regularity lemma for sparse graphs, Foundations of computational mathematics (Rio de Janeiro, 1997). Springer, Berlin (1997) 216-230. | Zbl
[20] and, Regular pairs in sparse random graphs. I. Random Structures Algorithms 22 (2003) 359-434. | Zbl
[21] and, 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
[22] , and, Ramanujan graphs. Combinatorica 8 (1988) 261-277. | Zbl
[23] , 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
[24] , Mixing time and long paths in graphs, manuscript available at http://www-math.mit.edu/~pak/research.html#r (June 2001).
[25] , Mixing time and long paths in graphs, in Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321-328. | Zbl
[26] , Asymptotic size Ramsey results for bipartite graphs. SIAM J. Discrete Math. 16 (2002) 99-113 (electronic). | Zbl
[27] , Size Ramsey numbers of stars versus 4-chromatic graphs. J. Graph Theory 42 (2003) 220-233. | Zbl
[28] , Hamiltonian circuits in random graphs. Discrete Math. 14 (1976) 359-364. | Zbl
[29] , The Ramsey size number of dipaths. Discrete Math. 257 (2002) 173-175. | Zbl
[30] and, On size Ramsey numbers of graphs with bounded degree. Combinatorica 20 (2000) 257-262. | Zbl
[31] , 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
Cité par Sources :
