Can genetic algorithms with the symmetric heuristic find the Ramsey number R(5,5)

Abstract

Ramsey Theory studies the existence of highly regular patterns within a large system and proves that the complete disorder doesn't exist. The role of Ramsey numbers is to quantify some of the general existential theorems in Ramsey theory. The Ramsey number R(m,n) is the smallest integer r such that a simple graph of r vertices has either a clique of size m or an independent set of vertices of size n as an induced subgraph. The evaluation of each Ramsey number is a combinatorial hard problem and only few numbers are currently known in spite of extensive research works carried out since more than six decades. In many cases, all we know is an upper and lower bound for very small values of the n and m. One of the most studied number is R(5,5) which is currently bounded by 43 ≤ R(5,5) ≤ 49. Many interesting research works have been carried out since 1989 to improve its lower bound without success. These works were based mainly on Genetic Algorithms, GAs. In this work, we discuss the application of a new genetic algorithm on R(5,5) in order to try to improve its lower bound from 43 to 44. Although, a graph solution on 43 vertices, G43, without neither a clique nor an independent set of vertices of size 5 couldn't be found, however, the proposed algorithm was able to build a G43 with only two cliques of size five. This shows clearly that we are close to a feasible solution and may be able to establish a new lower bound in the near future. The performance of our GA comes mainly from a new idea at the parent generation phase. This idea consists of obtaining first a chromosome solution for a graph of lower size Gi, and to use it as a starting point to generate the initial parent chromosomes for a graph of higher size Gi+1. These new chromosomes are then processed by the GA operations. This process is iterated staring from a graph on 36 vertices till the current graph on 43 vertices. We prove that the symmetric heuristic used by Exoo doesn't exist for all graphs of order higher than 42 associated with R(5,5)text.