On the $n$-color Rado number for the equation $x_{1}+x_{2}+ \dots +x_{k}+c =x_{k+1}$

Abstract:

For integers $k,n,c$ with $k,n \ge 1$, the $n$-color Rado number $R_{k}(n,c)$ is defined to be the least integer $N$, if it exists or $\infty$ otherwise, such that for every $n$-coloring of the set $\{1,2,\dots ,N\}$, there exists a monochromatic solution in that set to the equation \[ x_{1}+x_{2}+ \dots +x_{k}+c =x_{k+1}.\]

In this paper, we mostly restrict to the case $c \ge 0$, and consider two main issues regarding $R_{k}(n,c)$: is it finite or infinite, and when finite, what is its value? Very few results are known so far on either one.

On the first issue, we formulate a general conjecture, namely that $R_{k}(n,c)$ should be finite if and only if every divisor $d \le n$ of $k-1$ also divides $c$. The “only if” part of the conjecture is shown to hold, as well as the “if” part in the cases where either $k-1$ divides $c$, or $n \ge k-1$, or $k \le 7$, except for two instances to be published separately.

On the second issue, we obtain new bounds on $R_{k}(n,c)$ and determine exact formulae in several new cases, including $R_{3}(3,c)$ and $R_{4}(3,c)$. As for the case $R_{2}(3,c)$, first settled by Schaal in 1995, we provide a new shorter proof.

Finally, the problem is reformulated as a Boolean satisfiability problem, allowing the use of a SAT solver to treat some instances.