A constructive approach for the lower bounds on the Ramsey numbers R (s, t)

✍ Scribed by Xu Xiaodong; Xie Zheng; Stanisław P. Radziszowski

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 89 KB
• Volume: 47
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20038

✦ Synopsis

Abstract

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K~k~, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K~k−1~‐free graph M, we construct a (k, p + q − 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q − 1) ≥ R (k, p) + R (k, q) + n(M) − 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004