The 3-colored Ramsey number of even cycles

Autor(es)

Benevides, Fabricio Siqueira ^{[1, 2]} ; Skokan, Jozef ^{[3, 4]}

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil

^[2] Univ Memphis, Memphis, TN 38152 - USA

^[3] London Sch Econ, Dept Math, London WC2A 2AE - England

^[4] Univ Illinois, Dept Math, Urbana, IL 61801 - USA

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL THEORY SERIES B; v. 99, n. 4, p. 690-708, JUL 2009.
• Citações Web of Science: 19

Resumo

Denote by R(L, L, L) the minimum integer N such that any 3-coloring of the edges of the complete graph on N vertices contains a monochromatic copy of a graph L. Bondy and Erdos conjectured that when L is the cycle C(n) on n vertices, R(C(n), C(n), C(n)) = 4n - 3 for every odd n > 3. Luczak proved that if n is odd, then R(C(n), C(n), C(n)) = 4n + o(n), as n -> infinity, and Kohayakawa, Simonovits and Skokan confirmed the Bondy-Erdos conjecture for all sufficiently large values of n. Figaj and Luczak determined an asymptotic result for the `complementary' case where the cycles are even: they showed that for even n, we have R(C(n), C(n), C(n)) = 2n + o(n), as n -> infinity. In this paper, we prove that there exists n I such that for every even n >= n(1), R(C(n), C(n), C(n)) = 2n. (C) 2009 Elsevier Inc. All rights reserved. (AU)

• Processo FAPESP: 05/52494-0 - Problemas estruturais e numéricos na Teoria de Ramsey para grafos
• Beneficiário: Fabricio Siqueira Benevides
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 04/15397-4 - Aplicacoes de quase-aleatoriedade em combinatoria.
• Beneficiário: Jozef Skokan
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático