Uniform Turán Density—Palette Classification

ABSTRACT

In the 1980s, Erdős and Sós initiated the study of Turán hypergraph problems with a uniformity condition on the distribution of edges, that is, determining density thresholds for the existence of a hypergraph in a host hypergraph with edges uniformly distributed. In particular, Erdős and Sós asked to determine the uniform Turán densities of the hypergraphs and . After more than 30 years, the former was solved by Glebov, Král' and Volec [Israel J. Math. 211 (2016), 349–366] and Reiher, Rödl and Schacht [J. Eur. Math. Soc. 20 (2018), 1139–1159], while the latter still remains open. In these two cases and several additional cases, the tight lower bound is provided by a so‐called palette construction, that is, the existence of a palette that is not colorable with and that has the density equal to the uniform Turán density of . Lamaison [arXiv:2408.09643] has recently showed that the uniform Turán density of a 3‐uniform hypergraph is equal to the supremum of the densities of palettes that is not colorable with. We give a necessary and sufficient condition, which is easy to verify, on the existence of a 3‐uniform hypergraph colorable by each of palettes and not colorable by any palette . We also demonstrate how our result can be used to prove the existence of 3‐uniform hypergraphs with specific values of the uniform Turán density.