论文标题
使用SAT-Solvers改进了多色Ramsey数字的下限
Improved Lower Bounds for Multicolour Ramsey Numbers using SAT-Solvers
论文作者
论文摘要
本文阐明了具有特定Ramsey属性的线性和循环图形的一系列搜索结果。新图主要包含“模板图”，可在2021年当前作者描述的构造中使用，以构建具有继承的Ramsey属性的线性或循环化合物图。这些图导致了广泛的多色拉姆齐数字改善的下限。 使用相对简单的程序（用语言`C'编写）进行搜索，以生成对佩内洛普的输入和平行sat-solvers的输入条款。当找到解决方案时，求解器的输出指定了所需的图形着色。 这项工作产生的大多数图是“模板图”，其参数为$ $（k，k，3）$或$（k，l，3）$，带有$ k \ ne l $。在熟悉的构造中使用这些模板图，对于大多数$ r_r（k）$，以$ 5 \ le K \ le 9 $和$ r \ ge 4 $而言，可以证明大多数$ r_r（k）$的下限的显着改进。这些改进提供了相应增加的$γ（k）= \ lim _ {\ ordack {r \ rightarrow \ infty}} r {_r}（k）^{1/r} $的下限。 我们还表明，$ R_3（8）\ GE 7174 $和$ R_3（9）\ GE 15041 $。其他新的下限包括$ r（3,6,6）\ ge 338 $和$ r（3,8,8）\ ge 941 $，基于非板循环图，以及有趣的特定情况$ r（3,4,5,5）\ ge 729 $和$ r（3,5,5,5,5,5）\ ge 1429 $ 1429 $。 包含此处提到的许多图的标本的电子表格将作为ARXIV辅助文件附加。
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 \ne 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 \le k \le 9$ and $r \ge 4$. These improvements provide correspondingly increased lower bounds on $Γ(k) = \lim_{\substack{r \rightarrow \infty}} R{_r}(k)^{1/r}$. We also show that $R_3(8) \ge 7174$ and $R_3(9) \ge 15041$. Other new lower bounds include $R(3,6,6) \ge 338$ and $R(3,8,8) \ge 941$, based on non-template cyclic graphs, and the interesting particular cases $R(3,4,5,5) \ge 729$ and $R(3,5,5,5) \ge 1429$. A spreadsheet containing specimens of many of the graphs mentioned here will be attached as an ArXiv ancillary file.
