Combinatorics, Probability and Computing

Paper

The Ramsey Number for 3-Uniform Tight Hypergraph Cycles

P. E. HAXELLa1*, T. ŁUCZAKa2, Y. PENGa3, V. RÖDLa4, A. RUCIŃSKIa2 and J. SKOKANa5§

a1 Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 (e-mail: pehaxell@math.uwaterloo.ca)

a2 Department of Discrete Mathematics, Adam Mickiewicz University, 61-614 Poznań, Poland (e-mail: tomasz@amu.edu.pl, andrzej@mathcs.emory.edu)

a3 Department of Mathematics and Computer Science, Indiana State University, Terre Haute, IN 47809, USA (e-mail: mapeng@isugw.indstate.edu)

a4 Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30032, USA (e-mail: rodl@mathcs.emory.edu)

a5 Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK (e-mail: jozef@member.ams.org)

Abstract

Let C(3)n denote the 3-uniform tight cycle, that is, the hypergraph with vertices v1, .–.–., vn and edges v1v2v3, v2v3v4, .–.–., vn−1vnv1, vnv1v2. We prove that the smallest integer N = N(n) for which every red–blue colouring of the edges of the complete 3-uniform hypergraph with N vertices contains a monochromatic copy of C(3)n is asymptotically equal to 4n/3 if n is divisible by 3, and 2n otherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rödl.

(Received February 23 2007)

(Revised December 02 2008)

(Online publication February 04 2009)

Footnotes

* Partially supported by NSERC.

Supported by NSF grants DMS-0300529 and DMS-0800070.

Corresponding author. Supported by the Polish Ministry grant N201036 32/2546.

§ Supported by NSF grant INT-0305793, NSA grant H98230-04-1-0035, and by FAPESP/CNPq grants (Proj. Temático–ProNEx Proc. FAPESP 2003/09925–5 and Proc. FAPESP 2004/15397-4).