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

Abstract

Graph G is a (k, p)-graph if G does not contain a complete graph on k vertices Kk, 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 Kk-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