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?)

  • [1] H. L. Abbott and D. Hanson, A problem of Schur and its generalizations, Acta Arith. 20 (1972), 175-187. MR 0319934 (47 #8475)
  • [2] L. D. Baumert, Sum-free sets, J.P.L. Research Summary 36-10, 16-18, (1961).
  • [3] S. A. Burr and S. Loo, On Rado number I, Preprint.
  • [4] S. A. Burr and S. Loo, On Rado number II, Preprint.
  • [5] Albrecht Beutelspacher and Walter Brestovansky, Generalized Schur numbers, Combinatorial Theory (Schloss Rauischholzhausen, 1982) Lecture Notes in Math., vol. 969, Springer, Berlin-New York, 1982, pp. 30-38. MR 692232 (84f:10019)
  • [6] S. Eliahou, J. M. Marín, M. P. Revuelta, and M. I. Sanz, Weak Schur numbers and the search for G. W. Walker's lost partitions, Comput. Math. Appl. 63 (2012), no. 1, 175-182. MR 2863489, https://doi.org/10.1016/j.camwa.2011.11.006
  • [7] Geoffrey Exoo, A lower bound for Schur numbers and multicolor Ramsey numbers of $ K_3$, Electron. J. Combin. 1 (1994), Research Paper 8 (electronic). MR 1293398 (95k:05122)
  • [8] Harold Fredricksen and Melvin M. Sweet, Symmetric sum-free partitions and lower bounds for Schur numbers, Electron. J. Combin. 7 (2000), Research Paper 32 (electronic). MR 1763971 (2000m:05228)
  • [9] M. Heule,
    http://www.st.ewi.tudelft.nl/sat/,
    March RW. SAT Competition 2011 (2011).
  • [10] Honghui Wan, Upper bounds for Ramsey numbers $ R(3,3,\cdots ,3)$ and Schur numbers, J. Graph Theory 26 (1997), no. 3, 119-122. MR 1475891 (98f:05114), https://doi.org/10.1002/(SICI)1097-0118(199711)26:3$ \langle $119::AID-JGT1$ \rangle $3.3.CO;2-1
  • [11] Scott Jones and Daniel Schaal, Two-color Rado numbers for $ x+y+c=kz$, Discrete Math. 289 (2004), no. 1-3, 63-69. MR 2106029 (2005g:05149), https://doi.org/10.1016/j.disc.2004.06.022
  • [12] Wojciech Kosek and Daniel Schaal, Rado numbers for the equation $ \sum ^{m-1}_{i=1}x_i+c=x_m$, for negative values of $ c$, Adv. in Appl. Math. 27 (2001), no. 4, 805-815. MR 1867934 (2002i:05117), https://doi.org/10.1006/aama.2001.0762
  • [13] Richard Rado, Studien zur Kombinatorik, Math. Z. 36 (1933), no. 1, 424-470 (German). MR 1545354, https://doi.org/10.1007/BF01188632
  • [14] Stanisław P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. 1 (1994), Dynamic Survey 1, 30 pp. (electronic). MR 1670625 (99k:05117)
  • [15] Kathryn Rendall Truman and Daniel Schaal, Three-color Rado numbers for $ x_1+x_2+c=x_3$ for negative values of $ c$, Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing, 2006, pp. 5-10. MR 2311465 (2007m:05224)
  • [16] Aaron Robertson, Difference Ramsey numbers and Issai numbers, Adv. in Appl. Math. 25 (2000), no. 2, 153-162. MR 1780763 (2001f:05098), https://doi.org/10.1006/aama.2000.0678
  • [17] Adolfo Sánchez-Flores, An improved upper bound for Ramsey number $ N(3,3,3,3;2)$, Discrete Math. 140 (1995), no. 1-3, 281-286. MR 1333725 (96b:05121), https://doi.org/10.1016/0012-365X(93)E0187-9
  • [18] I. Sanz Domínguez,
    Números de Schur y Rado,
    Ph. Thesis, Universidad de Sevilla, 2010.
  • [19] Daniel Schaal, On generalized Schur numbers, Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993), 1993, pp. 178-187. MR 1267352 (95f:05113)
  • [20] Daniel Schaal, A family of $ 3$-color Rado numbers, Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), 1995, pp. 150-160. MR 1369349 (96h:05006)
  • [21] Daniel Schaal and Donald Vestal, Rado numbers for $ x_1+x_2+\dots +x_{m-1}=2x_m$, Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, 2008, pp. 105-116. MR 2489815 (2010f:05184)
  • [22] I. Schur,
    Uber die Kongruenz $ x^{m}+y^{m}\equiv z^{m}($mod $ p)$,
    Jahresber. Deutsch. Math.-Verein. 25, 114-117 (1916).
  • [23] Earl Glen Whitehead Jr., The Ramsey number $ N(3,\,3,\,3,\,3;\,2)$, Discrete Math. 4 (1973), 389-396. MR 0314678 (47 #3229)
  • [24] Štefan Znám, Generalisation of a number-theoretical result, Mat.-Fyz. Casopis Sloven. Akad. Vied 16 (1966), 357-361. MR 0209175 (35 #78)

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

American Mathematical Society