Nov 1, 3:30pm, Wean 8220

Po-Shen Loh, Carnegie Mellon University

The critical window for the Ramsey-Turan problem

Po-Shen Loh, Carnegie Mellon University

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 isoperimetric 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. In
this work, we give nearly best-possible bounds, solving the various
open problems concerning this critical window.

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 their survey on the regularity method, Komlos, Shokoufandeh, Simonovits, and Szemeredi surmised that the regularity method is likely unavoidable for applications where the extremal graph has densities in the regular partition bounded away from 0 and 1. In particular, they thought this should be the case for Szemeredi's result on the Ramsey-Turan problem. Contrary to this philosophy, we develop new regularity-free methods which give a linear dependence, which is tight, between the parameters in Szemeredi's result on the Ramsey-Turan problem.

Joint work with Jacob Fox and Yufei Zhao.