Independence numbers of locally sparse graphs and a Ramsey type problem

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

Let G = (V,E) be a graph on n vertices with average degree t ≥ 1 in which for every vertex v E V the induced subgraph on the set of all neighbors of v is r-colorable. We show that the independence number of G is at least c/log(r + 1) n/t log t, for some absolute pos.tive constant c. This strengthens a well-known result of Ajtai, Komlós, and Szemerédi [1]. Combining their result with some probabilistic arguments, we prove the following Ramsey type theorem conjectured by Erdös [4] in 1979. There exists an absolute constant c' > 0 so that in every graph on n vertices in which any set of ⌊ √n ⌋ vertices contains at least one edge, there is some set of ⌊√n ⌋ vertices that contains at least c'√n log n edges.

Original languageEnglish (US)
Pages (from-to)271-278
Number of pages8
JournalRandom Structures and Algorithms
Volume9
Issue number3
DOIs
StatePublished - Oct 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Independence numbers of locally sparse graphs and a Ramsey type problem'. Together they form a unique fingerprint.

Cite this