Applying a genetic algorithm to improve the lower bounds of multi-color ramsey numbers
Shardul Rao · RIT Scholar Works (Rochester Institute of Technology) · 1997
Ramsey Theory studies conditions when a combinatorial object contains necessarily some smaller given objects. The role of Ramsey Numbers is to quantify some of the general existential theorems in Ramsey Theory. The objective of this thesis is to try to improve the lower bounds of Ramsey Numbers, in particular the bounds for multi-color graph Ramsey Numbers. Let Gi,G2,---,Gm be graphs on some n. R(G\,G2, ,Gm) denotes the m-color Ramsey number for graphs, avoiding G, in color i for 1 N, we need to find an edge coloring for a Kn graph using m colors (for N as large as possible) avoiding G, in color i. An order-based Genetic Algorithm (GA) combined with a greedy coloring heuristic is used as a search heuristic in finding the coloring. Each chromo some is a permutation representing the order in which the edges of graph are colored. (This approach was far more successful than a string representing the coloring.) The algorithm was successful. The known lower bounds for R(C4,C4,C4), R(C4,C4, K3), R(C4,K3, K3), R(C5,C5, C5) were matched, and two new lower bounds for Ramsey numbers, R(C4,C4,K3,K3) > 25 and R(Cs, C4, K3) > 13, were found. *See thesis for correct equations and mathematical terms