The Ramsey number for 3-uniform tight hypergraph cycles

Author(s)

Haxell‚ P. ; Luczak‚ T. ; Peng‚ Y. ; Rödl‚ V. ; Rucinski‚ A. ; Skokan‚ J.

• Document type: Journal article
• Source: COMBINATORICS PROBABILITY & COMPUTING; v. 18, n. 1-2, p. 165-203, 2009.

Abstract

Let C-n((3)) denote the 3-uniform tight cycle, that is, the hypergraph with vertices v(1),...,v(n) and edges v(1)v(2)v(3), v(2)v(3)v(4), ... ,v(n-1)v(n)v(1), v(n)v(1)v(2). 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-n((3)) 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 Rodl. (AU)

• FAPESP's process: 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures
• Grantee: Yoshiharu Kohayakawa
• Support Opportunities: PRONEX Research - Thematic Grants