Palettes determine uniform Tur\'an density

Abstract

Tur\'an problems, which concern the minimum density threshold required for the existence of a particular substructure, are among the most fundamental problems in extremal combinatorics. We study Tur\'an problems for hypergraphs with an additional uniformity condition on the edge distribution. This kind of Tur\'an problems was introduced by Erd\H{o}s and S\'os in the 1980s but it took more than 30 years until the first non-trivial exact results were obtained when Glebov, Kr\'al' and Volec [Israel J. Math. 211 (2016), 349--366] and Reiher, R\"odl and Schacht [J. Eur. Math. Soc. 20 (2018), 1139--1159] determined the uniform Tur\'an density of $K_4^{(3)-}$. Subsequent results exploited the powerful hypergraph regularity method, developed by Gowers and by Nagle, R\"odl and Schacht about two decades ago. Central to the study of the uniform Tur\'an density of hypergraphs are palette constructions, which were implicitly introduced by R\"odl in the 1980s. We prove that palette constructions always yield tight lower bounds, unconditionally confirming present empirical evidence. This results in new and simpler approaches to determining uniform Tur\'an densities, which completely bypass the use of the hypergraph regularity method.

Locations

• arXiv (Cornell University) - View - PDF