Improved Lower Bounds for Multicolour Ramsey Numbers using SAT-Solvers

Publication date 25 March 2022

Abstract: This paper sets out the results of a range of searches for linear and cyclic graph colourings with specific Ramsey properties. The new graphs comprise mainly 'template graphs' which can be used in a construction described by the current author in 2021 to build linear or cyclic compound graphs with inherited Ramsey properties. These graphs result in improved lower bounds for a wide range of multicolour Ramsey numbers. Searches were carried out using relatively simple programs (written in the language `C') to generate clauses for input to the PeneLoPe and Plingeling parallel SAT-solvers. When solutions were found, the output from the solvers specified the desired graph colourings. The majority of the graphs produced by this work are `template graphs' with parameters in the form

(k, k, 3)

or

(k, l, 3)

with

k e l

. Using these template graphs in familiar constructions, it has been possible to demonstrate significant improvements for lower bounds for most

R_{r} (k)

for

5 l e k l e 9

and

r g e 4

. These improvements provide correspondingly increased lower bounds on

G a m m a (k) = l i m_{s u b s t a c k r i g h t a r r o w i n f t y} R_{r} (k)^{1 / r}

. We also show that

R_{3} (8) g e 7174

and

R_{3} (9) g e 15041

. Other new lower bounds include

R (3, 6, 6) g e 338

and

R (3, 8, 8) g e 941

, based on non-template cyclic graphs, and the interesting particular cases

R (3, 4, 5, 5) g e 729

and

R (3, 5, 5, 5) g e 1429

. A spreadsheet containing specimens of many of the graphs mentioned here will be attached as an ArXiv ancillary file.

This page was built for publication: Improved Lower Bounds for Multicolour Ramsey Numbers using SAT-Solvers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6394668)