2022/09/16 by Kamčev, Nina, Letzter, Shoham, Pokrovskiy, Alexey · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2209.08134
The Turán density of an r-uniform hypergraph H, denoted π(H), is the limit of the maximum density of an n-vertex r-uniform hypergraph not containing a copy of H, as n → ∞. Denote by Cℓ the 3-uniform tight cycle on ℓ vertices. Mubayi and Rödl gave an ``iterated blow-up'' construction showing that the Turán density of C5 is at least 2√(3) - 3 ≈ 0.464, and this bound is conjectured to be tight. Their construction also does not contain Cℓ for larger ℓ not divisible by 3, which suggests that it might be the extremal construction for these hypergraphs as well. Here, we determine the Turán density of Cℓ for all large ℓ not divisible by 3, showing that indeed π(Cℓ) = 2√(3) - 3. To our knowledge, this is the first example of a Turán density being determined where the extremal construction is an iterated blow-up construction. A key component in our proof, which may be of independent interest, is a 3-uniform analogue of the statement ``a graph is bipartite if and only if it does not contain an odd cycle''.