file.pdf (434.94 kB)
Download file

The critical window for the classical Ramsey-Turán problem

Download (434.94 kB)
journal contribution
posted on 01.09.2014, 00:00 authored by Jacob Fox, Po-Shen Loh, Yufei Zhang

The first application of Szemerédi’s powerful regularity method was the following celebrated Ramsey-Turán result proved by Szemerédi in 1972: any K 4-free graph on n vertices with independence number o(n) has at most (18+o(1))n2 edges. Four years later, Bollobás and Erdős 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 (18−o(1))n2 edges. Starting with Bollobás and Erdős 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 paper, we give nearly best-possible bounds, solving the various open problems concerning this critical window.

History

Publisher Statement

The final publication is available at Springer via http://dx.doi.org/10.1007/s00493-014-3025-3

Date

01/09/2014

Usage metrics

Exports