MORE CONSTRUCTIVE LOWER BOUNDS ON CLASSICAL RAMSEY NUMBERS

摘要

We present several new constructive lower bounds for classical Ramsey numbers. In particular, the inequality R(k, s + 1) ≥ R(K, s) + 2k - 2 is proved for k ≥ 5. The general construction permits us to prove that, for all integers k, l, with k > 5 and l > 3, the connectivity of any Ramsey-critical (k,l)-graph is at least k, and if k ≥ l - 1 ≥ 1, k ≥ 3 and (k, l) ≠ (3,2), then such graphs are Hamiltonian. New concrete lower bounds for Ramsey numbers are obtained, some with the help of computer algorithms, including: R(5, 17) ≥ 388,R(5, 19) ≥ 411, R(5,20) ≥ 424, R(6,8) ≥ 132, R(6,12) ≥ 263, R(7,8) ≥ 217, R(7,9) ≥ 241, R(7,12) ≥417, R(8,17) ≥ 961, R(9,10) ≥ 581, R(12, 12) > 1639, and also one three-color case R(8, 8, 8) > 6079.