The Ramsey Number for 3-Uniform Tight Hypergraph Cycles

Penny Haxell, Tomasz Łuczak, Yuejian Peng, V. Rödl, Andrzej Ruciński, Jozef Skokan

Abstract

Let C (3) n 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 (3) n is asymptotically equal to 4 n /3 if n is divisible by 3, and 2 n otherwise. The proof uses the regularity lemma for hypergraphs of Frankl and Rödl.

Locations

• London School of Economics and Political Science Research Online (London School of Economics and Political Science) - View - PDF
• Combinatorics Probability Computing - View