On disjunctive Rado numbers for some sets of equations

A. Dileep ; Jai Moondra ; Amitabha Tripathi

The electronic journal of combinatorics, Tome 31 (2024) no. 1

Résumé

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=R_d(S)$, if it exists, such that every $2$-coloring $\chi$ of the integers in $[1, 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 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_1 x,\ldots,y=a_k x\}$. 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(ka_k \log a_k)$ for the case of additive equations, which is exponentially better than the brute-force algorithm for the problem.

Détail

DOI : 10.37236/12012

Classification : 05D10
Mots-clés : search-based algorithm, valid coloring