On $k$-uniform tight cycles: the Ramsey number for $C_{kn}^{(k)}$ and an approximate Lehel's conjecture

Abstract

A $k$-uniform tight cycle is a $k$-graph with a cyclic ordering of its vertices such that its edges are precisely the sets of $k$ consecutive vertices in that ordering. We show that, for each $k\ge 3$, the Ramsey number of the $k$-uniform tight cycle on $kn$ vertices is $(1+o(1))(k+1)n$. This is an extension to all uniformities of previous results for $k=3$ by Haxell, Łuczak, Peng, Rödl, Ruciński, and Skokan and for $k=4$ by Lo and the author and confirms a special case of a conjecture by the former set of authors. Lehel's conjecture, which was proved by Bessy and Thomassé, states that every red-blue edge-coloured complete graph contains a red cycle and a blue cycle that are vertex-disjoint and together cover all the vertices. We also prove an approximate version of this for $k$-uniform tight cycles. We show that, for every $k\ge 3$, every red-blue edge-coloured complete $k$-graph on $n$ vertices contains a red tight cycle and a blue tight cycle that are vertex-disjoint and together cover $n-o(n)$ vertices.

20 pages, to appear in Combinatorica