×

Schur numbers involving rainbow colorings. (English) Zbl 1464.05262

Summary: In this paper, we introduce two different generalizations of Schur numbers that involve rainbow colorings. Motivated by well-known generalizations of Ramsey numbers, we first define the rainbow Schur number \(RS(n)\) to be the minimum number of colors needed such that every coloring of \(\{1,2,\dots,n\}\), in which all available colors are used, contains a rainbow solution to \(a+b=c\). It is shown that \[ RS(n)=\lfloor\log_2(n)\rfloor+2, \text{ for all } n\geq 3. \] Second, we consider the Gallai-Schur number \(GS(n)\), defined to be the least natural number such that every \(n\)-coloring of \(\{1,2,\dots,GS(n)\}\) that lacks rainbow solutions to the equation \(a+b=c\) necessarily contains a monochromatic solution to this equation. By connecting this number with the \(n\)-color Gallai-Ramsey number for triangles, it is shown that for all \(n\geq 3\), \[ GS(n)=\begin{cases}5^k&\text{if }n=2k\\2\cdot 5^k&\text{in }n=2k+1.\end{cases} \]

MSC:

05C55 Generalized Ramsey theory
05D10 Ramsey theory
05C15 Coloring of graphs and hypergraphs
11B75 Other combinatorial number theory
Full Text: DOI

References:

[1] A. Beutelspacher and W. Brestovansky, Generalized Schur numbers, in:Combinatorial Theory, Springer, Berlin-New York, volume 969 ofLecture Notes in Mathematics, 1982 pp. 30-38, Proceedings of a Conference held at Schloss Rauischholzhausen, May 6 - 9, 1982. · Zbl 0498.05002
[2] G. Chartrand and P. Zhang,Chromatic Graph Theory, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, Florida, 2009. · Zbl 1169.05001
[3] F. R. K. Chung and R. L. Graham, Edge-colored complete graphs with precisely colored subgraphs,Combinatorica3(1983), 315-324, doi:10.1007/bf02579187. · Zbl 0529.05041
[4] L. E. Dickson, On the last theorem of Fermat,Quart. J. Pure Appl. Math.40(1908), 27-45. · JFM 39.0260.03
[5] J. Fox, V. Jungi´c and R. Radoiˇci´c, Sub-Ramsey numbers for arithmetic progressions and Schur triples,Integers7(2007), #A12,http://math.colgate.edu/ integers/ a12int2005/a12int2005.Abstract.html. · Zbl 1123.05090
[6] S. W. Golomb and L. D. Baumert, Backtrack programming,J. Assoc. Comput. Mach.12(1965), 516-524, doi:10.1145/321296.321300. · Zbl 0139.12305
[7] M. J. H. Heule, Schur number five, in: S. A. McIlraith and K. Q. Weinberger (eds.),ThirtySecond AAAI Conference on Artificial Intelligence, AAAI Press, 2018 pp. 6598-6606, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th
[8] R. W. Irving, An extension of Schur’s theorem on sum-free partitions,Acta Arith.25(1973/74), 55-64, doi:10.4064/aa-25-1-55-64. · Zbl 0241.10036
[9] B. M. Landman and A. Robertson,Ramsey Theory on the Integers, volume 24 ofStudent Mathematical Library, American Mathematical Society, Providence, Rhode Island, 2004. · Zbl 1035.05096
[10] F. P. Ramsey, On a Problem of Formal Logic,Proc. London Math. Soc.30(1929), 264-286, doi:10.1112/plms/s2-30.1.264. · JFM 55.0032.04
[11] I. Schur, Uber die Kongruenzxm+ym≡zm(modp),Jber. Deutsch. Math.-Verein.25 (1916), 114-117. · JFM 46.0193.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.