Computational Methods for Ramsey Numbers

摘要

The Ramsey number R(k,l) is the least integer in such that all graphs on n ormore vertices contain a clique of k vertices or an independent set of 1 vertices as an induced subgraph. In this work we investigate computational methods for finding lower bounds for Ramsey numbers. Some constructions of lower bounds for multicolor Ramsey numbers, generalization of Ramsey number, are also considered. Several methods that have been used for finding lower bounds for Ramsey numbers are surveyed. Specifically, constructions which correspond to the structure of finite fields are examined, using local search methods is discussed, and using symmetrical graph colorings are investigated. The main emphasis in this work is on using local search methods for finding lower bounds for Ramsey numbers. By a construction found by using tabu search, we show that R(5,9) is greater than 120.