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

DOI10.1007/S00493-014-3025-3MaRDI QIDQ520045zbMATHOpenAlexFDO

Authors Jacob Fox, Po-Shen Loh, Yufei Zhao

Publication date 31 March 2017

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.3276

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The first application of Szemer'edi's powerful regularity method was the following celebrated Ramsey-Tur'an result proved by Szemer'edi 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, Bollob'as and ErdH{o}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 (1/8 - o(1)) N^2 edges. Starting with Bollob'as and ErdH{o}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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: The critical window for the classical Ramsey-Turán problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q520045)