The Turán Density of 4-Uniform Tight Cycles

One of the central problems studied in extremal combinatorics is determining the largest number of edges a large, uniform hypergraph can have while avoiding a fixed forbidden subgraph. The most fundamental problem is that of determining the Turán density of an \(r\)-uniform hypergraph \(H\), that is, the quantity \[\pi(H) := \lim_{n \to \infty} \binom{n}{r}^{-1} \mathrm{ex}(n, H),\] where \(\mathrm{ex}(n,H)\) is the largest number of edges in an \(r\)-uniform hypergraph on \(n\) vertices that does not contain \(H\) as a subgraph. The celebrated Erdős–Stone–Simonovits theorem states that the Turán density of every (\(2\)-uniform) graph \(H\) is \(1 - 1/(\chi(H)-1)\). In the case of hypergraphs with uniformity greater than two, no analogous simple formula is known. There are relatively few hypergraph families whose Turán density is known. In particular, the density of the \(3\)-uniform complete hypergraph with four vertices, first studied by Turán himself in the 1960s, remains unknown to this day.

One natural family of hypergraphs that is of interest in this context is the family of tight cycles. The \(r\)-uniform tight cycle of length \(\ell\), denoted by \(C_\ell^{(r)}\) has vertices \(v_1, \dotsc, v_\ell\) where each of the \(\ell\) consecutive \(r\)-tuples \(\{v_i, \dotsc, v_{i+\ell-1}\}\) forms an edge. When \(r\) divides \(\ell\), this hypergraph is \(r\)-partite and thus its Turán density is zero. A recent work of Kamčev, Letzter, and Pokrovskiy established that \(\pi(C_\ell^{(3)}) = 2\sqrt{3} - 3\) for all sufficiently large \(\ell\) not divisible by three.

The main result of this paper is that \(\pi(C_\ell^{(4)}) = 1/2\) for all sufficiently large \(\ell\) not divisible by four. This result, however, is not merely a computation of a density. A the heart of the matter lies an elegant structural characterisation of hypergraphs that do not have a homomorphic copy of any r-uniform cycle whose length is congruent to some fixed \(k\) modulo \(r\). It is a highly nontrivial generalisation of the well-known fact that a graph is bipartite if and only if it does not contain any close odd walks (i.e., homomorphic copies of an odd cycle). The characterisation cleverly reduces the determination of \(\pi(C_\ell^{(r)})\) to an extremal problem involving colourings of \((r-1)\)-tuples of vertices that obey local consistency constrains on every edge that turns out to be tractable (but by no means easy!) in the case \(r=4\).