Geometric constructions for Ramsey–Turán theory

Abstract

Combining two classical notions in extremal combinatorics, the study of Ramsey–Turán theory seeks to determine, for integers $m\le n$ and $p\le q$, the number ${\mathsf{RT}}_p(n,K_q,m)$, which is the maximum size of an $n$-vertex $K_q$-free graph in which every set of at least $m$ vertices contains a $K_p$. Two major open problems in this area from the 80s ask: (1) whether the asymptotic extremal structure for the general case exhibits certain periodic behaviour, resembling that of the special case when $p=2$; (2) how to construct analogues of Bollobás–Erdős graphs with densities other than $\frac{1}{2}$. We refute the first conjecture by witnessing asymptotic extremal structures that are drastically different from the $p=2$ case, and address the second problem by constructing Bollobás–Erdős-type graphs using high-dimensional complex spheres with all rational densities. Some matching upper bounds are also provided.