Premium
Book Ramsey numbers. I
Author(s) -
Nikiforov Vladimir,
Rousseau Cecil
Publication year - 2005
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.20081
Subject(s) - lemma (botany) , ramsey's theorem , combinatorics , graph , struct , constant (computer programming) , mathematics , discrete mathematics , computer science , ecology , poaceae , biology , programming language
A book B p is a graph consisting of p triangles sharing a common edge. In this paper we prove that if p ≤ q /6 − o ( q ) and q is large, then the Ramsey number r ( B p , B q ) is given by r ( B p , B q ) = 2 q +3, and the constant 1/6 is essentially best possible. Our proof is based on Szemerédi's uniformity lemma and a stability result for books. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005