Bounding Ramsey numbers through large deviation inequalities

Abstract

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(K r , K k ), 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 K 4 ‐free graph G on n vertices in which every cn 3/5 log 1/2 n vertices span a copy of K 3 . © 1995 John Wiley & Sons, Inc.