论文标题
RADO数字和SAT计算
Rado Numbers and SAT Computations
论文作者
论文摘要
给定一个线性方程$ \ MATHCAL {E} $，$ k $ -color rado number $ r_k（\ Mathcal {e}）$是最小的整数$ n $，这样每一个$ k $ -coloring $ \ \ \ \ \ \ \ \ {1,2,3，\ dots，\ dots，n \} $ co $ a $ a $ $ a $ $ c。 $ \ MATHCAL E $的规律性，表示为$ dor（\ Mathcal e）$，是最大的$ k $，因此$ r_k（\ Mathcal e）$是有限的。在本文中，我们介绍了有关RADO数字$ R_3（\ Mathcal {e}）$的新理论和计算结果以及三变量方程的规律性$ \ Mathcal {e} $。 ％我们使用SAT求解器来计算固定整数$ A，B，$和$ C $的三色RADO数字$ R_3（AX+By+CZ = 0）$的许多新值。我们还提供了一种基于SAT的方法来计算这些数字的无限家庭。特别是，我们表明$ r_3（x-y =（m-2）z）$的值等于$ m^3-m^2-m-1 $对于$ m \ ge 3 $。这解决了迈尔斯的猜想，并暗示了一个猜想的是，广义的schur数字$ s（m，3）= r_3（x_1 + x_2 + \ dots x_ {m-1} = x_m）$等于$ m^3-m^2-m^2-m-1 $ for $ m \ ge 3 $。我们的SAT求解器计算与我们的新组合结果相结合，在$ DOR（AX+by = Cz）$和$ 1 \ le a，b，c \ le 5 $的精确值上提供了改进的界限。我们还为Golowich的猜想提供了反例。
Given a linear equation $\mathcal{E}$, the $k$-color Rado number $R_k(\mathcal{E})$ is the smallest integer $n$ such that every $k$-coloring of $\{1,2,3,\dots,n\}$ contains a monochromatic solution to $\mathcal E$. The degree of regularity of $\mathcal E$, denoted $dor(\mathcal E)$, is the largest value $k$ such that $R_k(\mathcal E)$ is finite. In this article we present new theoretical and computational results about the Rado numbers $R_3(\mathcal{E})$ and the degree of regularity of three-variable equations $\mathcal{E}$. % We use SAT solvers to compute many new values of the three-color Rado numbers $R_3(ax+by+cz = 0)$ for fixed integers $a,b,$ and $c$. We also give a SAT-based method to compute infinite families of these numbers. In particular, we show that the value of $R_3(x-y = (m-2) z)$ is equal to $m^3-m^2-m-1$ for $m\ge 3$. This resolves a conjecture of Myers and implies the conjecture that the generalized Schur numbers $S(m,3) = R_3(x_1+x_2 + \dots x_{m-1} = x_m)$ equal $m^3-m^2-m-1$ for $m\ge 3$. Our SAT solver computations, combined with our new combinatorial results, give improved bounds on $dor(ax+by = cz)$ and exact values for $1\le a,b,c\le 5 $. We also give counterexamples to a conjecture of Golowich.
