pith. sign in

arxiv: 1208.3276 · v3 · pith:X2LAV3VPnew · submitted 2012-08-16 · 🧮 math.CO

The critical window for the classical Ramsey-Tur\'an problem

classification 🧮 math.CO
keywords numberproblemscriticaledgesindependencewindowbollobfree
0
0 comments X
read the original 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 Erd\H{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 Erd\H{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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.