Bounding Ramsey numbers through large deviation inequalities | Zendy

Krivelevich Michael | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research