Combinatorics Seminar
When: Sunday, December 30, 10am
Where: Schreiber 309
Speaker: Po-Shen Loh, Carnegie Mellon University
Title: The critical window for the Ramsey-Turan problem
Abstract:
The first application of Szemeredi's regularity method was
the following celebrated Ramsey-Turan result proved by Szemeredi
in 1972: any K_4-free graph on N vertices with independence number
o(N) has at most (1/8 + o(1)) N^2 edges. Four years later, Bollobas
and Erdos gave a surprising geometric construction, utilizing
the isodiametric inequality for the high dimensional sphere, of
a K_4-free graph on N vertices with independence number o(N) and
(1/8 - o(1)) N^2 edges. Starting with Bollobas and Erdos in 1976,
several problems have been asked on estimating the minimum possible
independence number in the critical window, when the number of
edges is about N^2 / 8.
These problems have received considerable attention and remained
one of the main open problems in this area. More generally, it
remains an important problem to determine if, for certain
applications of the regularity method, alternative proofs exist
which avoid using the regularity lemma and give better quantitative
estimates. In this work, we develop new regularity-free methods
which give nearly best-possible bounds, solving the various open
problems concerning this critical window.
Joint work with Jacob Fox and Yufei Zhao.