The 3-colored Ramsey number of even cycles

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.

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

FAPESP[FAPESP 05/52494-0]

FAPESP[FAPESP 03/09925-5]

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

FAPESP[FAPESP 04/15397-4]

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

National Science Foundation (NSF)[INT-0305793]

National Science Foundation (NSF)