Computational Methods for Ramsey Numbers

Reference:

Harri Haanpää. Computational methods for Ramsey numbers. Research Report A65, Helsinki University of Technology, Department of Computer Science and Engineering, Laboratory for Theoretical Computer Science, Espoo, Finland, November 2000.

Abstract:

The Ramsey number R(k,l) is the least integer n such that all graphs on n or more vertices contain a clique of k vertices or an independent set of l vertices as a subgraph. In this work we investigate computational methods for finding lower bounds for Ramsey numbers. Some constructions of lower bounds for multicolor Ramsey numbers, a generalization of Ramsey numbers, 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.

Evaluating Ramsey numbers is very difficult due to the combinatorial nature of the problem, and exact values are only known for the smallest values of the parameters. Some recent results concerning the computational complexity of related problems are summarized.

Keywords:

Ramsey numbers, graph theory, tabu search

Suggested BibTeX entry:

@techreport{HUT-TCS-A65,
    address = {Espoo, Finland},
    author = {Harri Haanp{\"a}{\"a}},
    institution = {Helsinki University of Technology, Department of Computer Science and Engineering, Laboratory for Theoretical Computer Science},
    month = {November},
    number = {A65},
    pages = {50},
    title = {Computational Methods for {R}amsey Numbers},
    type = {Research Report},
    year = {2000},
}