Rado Numbers and SAT Computations

DOI10.1145/3476446.3535494MaRDI QIDQ6413161zbMATH OpenWikidataFDO

Authors Yuan Chang, Jesús A. De Loera, William J. Wesley

Publication date 6 October 2022

Full work available at URL https://doi.org/10.1145/3476446.3535494

Abstract: Given a linear equation $mathcalE$, the $k$-color Rado number $R_k(mathcalE)$ is the smallest integer $n$ such that every $k$-coloring of $1,2,3,dots,n$ contains a monochromatic solution to $mathcalE$. The degree of regularity of $mathcalE$, denoted $dor(mathcalE)$, is the largest value $k$ such that $R_k(mathcalE)$ is finite. In this article we present new theoretical and computational results about the Rado numbers $R_3(mathcalE)$ and the degree of regularity of three-variable equations $mathcalE$. % 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 $mge3$. 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 $mge3$. Our SAT solver computations, combined with our new combinatorial results, give improved bounds on $dor(ax+by=cz)$ and exact values for $1lea,b,cle5$. We also give counterexamples to a conjecture of Golowich.

This page was built for publication: Rado Numbers and SAT Computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6413161)