Premium
Independence numbers of locally sparse graphs and a Ramsey type problem
Author(s) -
Alon Noga
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199610)9:3<271::aid-rsa1>3.0.co;2-u
Subject(s) - combinatorics , mathematics , ramsey's theorem , vertex (graph theory) , independence number , graph , constant (computer programming) , induced subgraph , discrete mathematics , independent set , computer science , programming language
Let G = ( V, E ) be a graph on n vertices with average degree t ≥ 1 in which for every vertex v ϵ 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}\over{\log (r+1)}}{{n}\over{t}}\log t$ log t , for some absolute positive 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. © 1995 John Wiley & Sons, Inc.