Bounding Ramsey numbers through large deviation inequalities
Author:
- 1 September 1995
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 7 (2) , 145-155
Abstract
We develop a new approach for proving lower bounds for various Ramsey numbers, based on using large deviation inequalities. This approach enables us to obtain the bounds for the off‐diagonal Ramsey numbers R(Kr, Kk), r ≤ k, that match the best known bounds, obtained through the local lemma. We discuss also the bounds for a related Ramsey‐type problem and show, for example, that there exists a K4‐free graph G on n vertices in which every cn3/5 log1/2 n vertices span a copy of K3. © 1995 John Wiley & Sons, Inc.Keywords
This publication has 7 references indexed in Scilit:
- Ks-Free Graphs Without Large Kr-Free SubgraphsCombinatorics, Probability and Computing, 1994
- Graphs without large triangle free subgraphsDiscrete Mathematics, 1991
- Counting extensionsJournal of Combinatorial Theory, Series A, 1990
- Representations of integers as the sum of k termsRandom Structures & Algorithms, 1990
- Poisson approximation for large deviationsRandom Structures & Algorithms, 1990
- Asymptotic lower bounds for Ramsey functionsDiscrete Mathematics, 1977
- The Construction of Certain GraphsCanadian Journal of Mathematics, 1962