Premium
Bounding Ramsey numbers through large deviation inequalities
Author(s) -
Krivelevich Michael
Publication year - 1995
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/rsa.3240070204
Subject(s) - ramsey's theorem , combinatorics , bounding overwatch , mathematics , lemma (botany) , diagonal , graph , ramsey theory , upper and lower bounds , discrete mathematics , computer science , ecology , mathematical analysis , geometry , poaceae , artificial intelligence , biology
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.