{
  "id": "1208.3276",
  "version": "v3",
  "published": "2012-08-16T03:16:00.000Z",
  "updated": "2014-09-23T14:03:41.000Z",
  "title": "The critical window for the classical Ramsey-Turán problem",
  "authors": [
    "Jacob Fox",
    "Po-Shen Loh",
    "Yufei Zhao"
  ],
  "comment": "34 pages",
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-09-15T14:44:28.000Z",
      "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. 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, Koml\\'os, Shokoufandeh, Simonovits, and Szemer\\'edi 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 Szemer\\'edi's result on the Ramsey-Tur\\'an problem. Contrary to this philosophy, we develop new regularity-free methods which give a linear dependence, which is tight, between the parameters in Szemer\\'edi's result on the Ramsey-Tur\\'an problem.",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2014-09-23T14:03:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05D10",
      "05C55",
      "05D40"
    ],
    "keywords": [
      "critical window",
      "classical ramsey-turán problem",
      "independence number",
      "ramsey-turan problem",
      "szemeredis result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1208.3276F"
    }
  }
}