Independence numbers of locally sparse graphs and a Ramsey type problem
✍ Scribed by Noga Alon
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 409 KB
- Volume
- 9
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
Let G = (V, E ) be a graph on n vertices with average degree t 2 1 in which for every vertex u E V the induced subgraph on the set of all neighbors of u is r-colorable. We show that the independence number of G is at least log t , for some absolute positive constant c. This strengthens a well-known result of Ajtai, Koml6s, and Szemertdi [l]. Combining their result with some probabilistic arguments, we prove the following Ramsey type theorem, conjectured by Erdos [4] in 1979. There exists an absolute constant c' > 0 so that in every graph on n vertices in which any set of L f i ] vertices contains at least one edge, there is some set of L f i ] vertices that contains at least c ' f i log n edges.