Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

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


Authors: S. D. Adhikari, L. Boza, S. Eliahou, J. M. Marín, M. P. Revuelta and M. I. Sanz
Journal: Math. Comp. 85 (2016), 2047-2064
MSC (2010): Primary 05A17, 11P83, 05C55, 05D10, 05-04
DOI: https://doi.org/10.1090/mcom3034
Published electronically: September 14, 2015
MathSciNet review: 3471118
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

$\displaystyle 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05A17, 11P83, 05C55, 05D10, 05-04

Retrieve articles in all journals with MSC (2010): 05A17, 11P83, 05C55, 05D10, 05-04


Additional Information

S. D. Adhikari
Affiliation: Harish-Chandra Research Institute, Chhathnag Road, Jhunsi, Allahabad-211 019, India
Email: adhikari@hri.res.in

L. Boza
Affiliation: Escuela Técnica Superior de Arquitectura, Departamento de Matemática Aplicada I, Avenida de la Reina Mercedes 2, C.P. 41012 Sevilla, Spain
Email: boza@us.es

S. Eliahou
Affiliation: ULCO, LMPA J. Liouville, CS 80699 – 62228 Calais Cedex, France — and — CNRS, FR 2956, France
Email: eliahou@lmpa.univ-littoral.fr

J. M. Marín
Affiliation: Escuela Técnica Superior de Ingeniería de Edificación, Departamento de Matemática Aplicada I, Avenida de la Reina Mercedes 4, C.P. 41012 Sevilla, Spain
Email: jmarin@us.es

M. P. Revuelta
Affiliation: Escuela Técnica Superior de Ingeniería de Edificación, Departamento de Matemática Aplicada I, Avenida de la Reina Mercedes 4, C.P. 41012 Sevilla, Spain
Email: pastora@us.es

M. I. Sanz
Affiliation: Escuela Técnica Superior de Ingeniería de Edificación, Departamento de Matemática Aplicada I, Avenida de la Reina Mercedes 4, C.P. 41012 Sevilla, Spain
Email: isanz@us.es

DOI: https://doi.org/10.1090/mcom3034
Keywords: Schur numbers, sum-free sets, Rado numbers, Boolean variables, SAT problem, SAT solver
Received by editor(s): June 4, 2014
Received by editor(s) in revised form: December 17, 2014
Published electronically: September 14, 2015
Additional Notes: The authors acknowledge partial support from the Instituto de Matemáticas; Antonio de Castro Brzezicki de la Universidad de Sevilla during research on this work.
Article copyright: © Copyright 2015 American Mathematical Society