On Disjunctive Rado Numbers for Some Sets of Equations

Abstract: Given a set of linear equations $S$ with positive integral parameters $a_1, \ldots, a_k$, $k \ge 2$, the disjunctive Rado number for the set $S$ is the least positive integer $R_d = R_d(S)$, if it exists, such that every $2$-coloring $\chi$ of the integers in ${1, \ldots, R}$ admits a monochromatic solution to at least one equation in $S$. We give conditions for the existence of $R_d(S)$, and also give general upper and lower bounds on $R_d(S)$, when $S$ is a set of additive equations ${y = x + a_1, \ldots, y = x + a_k}$. We also determine $R_d(S)$ when $\max_i a_i$ is large enough, or when $a_1, \ldots, a_k$ form an arithmetic or geometric progression. We also give conditions for the existence of $R_d(S)$ when $S$ is a set of multiplicative equations ${y = a_1x, \ldots, y = a_kx}$. Further, we give a general search-based algorithm to determine $R_d(S)$ when $S$ is a system of equations in two variables, given an upper bound on $R_d(S)$ and an algorithm to determine solutions to $S$. This algorithm runs in time $O(k a_k \log a_k)$ for the case of additive equations, which is exponentially better than the brute-force algorithm for the problem.

Journal link