Date
Tue, 28 May 2013
Time
16:30 - 17:30
Location
SR2
Speaker
Po-Shen Loh
Organisation
CMU

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.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.