Large Independent Sets from Local Considerations

Matija Bucić, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

Abstract

The following natural problem was raised independently by Erdős–Hajnal and Linial–Rabinovich in the early ’90 s. How large must the independence number α(G) of a graph G be whose every m vertices contain an independent set of size r? In this paper, we discuss new methods to attack this problem. The first new approach, based on bounding Ramsey numbers of certain graphs, allows us to improve the previously best lower bounds due to Linial–Rabinovich, Erdős–Hajnal and Alon–Sudakov. As an example, we prove that any n-vertex graph G having an independent set of size 3 among every 7 vertices has α(G) ≥ Ω (n5 / 12) . This confirms a conjecture of Erdős and Hajnal that α(G) should be at least n1/3+ε and brings the exponent halfway to the best possible value of 1/2. Our second approach deals with upper bounds. It relies on a reduction of the original question to the following natural extremal problem. What is the minimum possible value of the 2-density (The 2-density of a graph H is defined as m2(H):=maxH′⊆H,|H′|≥3e(H′)-1|H′|-2) of a graph on m vertices having no independent set of size r? This allows us to improve previous upper bounds due to Linial–Rabinovich, Krivelevich and Kostochka-Jancey. As part of our arguments, we link the problem of Erdős–Hajnal and Linial–Rabinovich and our new extremal 2-density problem to a number of other well-studied questions. This leads to many interesting directions for future research.

Original languageEnglish (US)
Pages (from-to)505-546
Number of pages42
JournalCombinatorica
Volume43
Issue number3
DOIs
StatePublished - Jun 2023

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • 2-density
  • Erdos-Rogers problem
  • Local to global phenomenon
  • Lovasz Local Lemma
  • Ramsey Theory

Fingerprint

Dive into the research topics of 'Large Independent Sets from Local Considerations'. Together they form a unique fingerprint.

Cite this