Optimal high dimension geometric construction for Ramsey-Turan theory

Abstract: Combining two classical notions in extremal graph theory, the study of Ramsey-Turan theory seeks to determine, for integers $m\le n$ and $p \leq q$, the number $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) to construct analogues of the Bollobas-Erdos graph with densities other than powers of $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 Bollobas-Erdos-type graphs with any rational density up to $\frac{1}{2}$ using high dimension complex sphere.

Joint work with Christian Reiher, Maryam Sharifzadeh and Katherine Staden.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).