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

DOI10.1007/S00493-014-3025-3zbMATH Open1374.05131arXiv1208.3276OpenAlexW2070834764MaRDI QIDQ520045FDOQ520045

Authors: Jacob Fox, Po-Shen Loh, Yufei Zhao 

Publication date: 31 March 2017

Published in: Combinatorica (Search for Journal in Brave)

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.

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

Recommendations

• A few remarks on Ramsey--Turán-type problems
• Two results on Ramsey-Turán theory
• Phase transitions in Ramsey-Turán theory
• Ramsey-Turán theory
• Two Conjectures in Ramsey--Turán Theory

zbMATH Keywords

regularity lemmaRamsey-Turán problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• A new proof of Szemerédi's theorem
• On sets of integers containing k elements in arithmetic progression
• Title not available (Why is that?)
• Ramsey-Turán theory
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Sets of Acquaintances and Strangers at any Party
• Quick approximation to matrices and applications
• On a Ramsey-Turán type problem
• Bounds for graph regularity and removal lemmas
• Regularity lemmas for graphs
• Dependent random choice
• Hypergraph packing and sparse bipartite Ramsey numbers
• On two problems in graph Ramsey theory
• On graphs with linear Ramsey numbers
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• A new proof of the graph removal lemma
• Density theorems for bipartite graphs and related Ramsey-type results
• A few remarks on Ramsey--Turán-type problems
• On the Ramsey-Turán numbers of graphs and hypergraphs
• Some exact Ramsey-Turán numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• More results on Ramsey-Turán type problems
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Title not available (Why is that?)
• The independence number of dense graphs with large odd girth
• Turán-Ramsey theorems and simple asymptotically extremal structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Die Brunn‐Minkowskische Ungleichung und ihr Spiegelbild sowie die isoperimetrische Eigenschaft der Kugel in der euklidischen und nichteuklidischen Geometrie. I

Cited In (9)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Two-colored Ramsey-Turán densities involving triangles
• Clique-factors in graphs with sublinear -independence number
• Two results on Ramsey-Turán theory
• Two Conjectures in Ramsey--Turán Theory
• Phase transitions in Ramsey-Turán theory
• On the Ramsey-Turán number with small \(s\)-independence number
• The Ramsey-Turán problem for cliques
• K4$K_4$‐free graphs have sparse halves

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)