A Novel Paradigm for Calculating Ramsey Number via Artificial Bee Colony Algorithm
This work addresses a specific combinatorial mathematics problem for researchers in graph theory and optimization, representing an incremental advance in computational methods for Ramsey numbers.
This paper tackled the problem of calculating the Ramsey number R(3,10) by proposing a method using the Artificial Bee Colony algorithm to construct Ramsey graphs, resulting in the first report of four r(3,9,39) graphs that support the current lower bound for R(3,10).
The Ramsey number is of vital importance in Ramsey's theorem. This paper proposed a novel methodology for constructing Ramsey graphs about R(3,10), which uses Artificial Bee Colony optimization(ABC) to raise the lower bound of Ramsey number R(3,10). The r(3,10)-graph contains two limitations, that is, neither complete graphs of order 3 nor independent sets of order 10. To resolve these limitations, a special mathematical model is put in the paradigm to convert the problems into discrete optimization whose smaller minimizers are correspondent to bigger lower bound as approximation of inf R(3,10). To demonstrate the potential of the proposed method, simulations are done to to minimize the amount of these two types of graphs. For the first time, four r(3,9,39) graphs with best approximation for inf R(3,10) are reported in simulations to support the current lower bound for R(3,10). The experiments' results show that the proposed paradigm for Ramsey number's calculation driven by ABC is a successful method with the advantages of high precision and robustness.