TOPICS
Search

Schur Number


The Schur number S(k) is the largest integer n for which the interval [1,n] can be partitioned into k sum-free sets (Fredricksen and Sweet 2000). S(k) is guaranteed to exist for each k by Schur's problem. Note the definition of the Schur number as the smallest number S^'(k)=S(k)+1 for which such a partition does not exist is also prevalent in the literature (OEIS A030126; Fredricksen and Sweet 2000).

Schur (1916) gave the lower bound

 S(k)>=1/2(3^n-1)
(1)

which is sharp for n=1, 2, and 3 (Guy 1994). The Schur numbers also satisfy the inequality

 S(k)>=c·321^(k/5)>c·3.15977^k
(2)

for k>5 and some constant c (Abbott and Moser 1966, Abbott and Hanson 1972, Exoo 1994). Schur's Ramsey theorem also shows that

 S(n)<=R(n)-2,
(3)

where R(n) is a Ramsey number. The first few Schur numbers are 1, 4, 13, 44, 160<=S(5)<=315 (Fredricksen 1979), S(6)>=536, S(7)>=1680, ... (OEIS A045652; Fredricksen and Sweet 2000). S(4) is due to Baumert (Baumert 1965, Abbott and Hanson 1972), the lower bound on S(5) is due to Exoo (1994), and the lower limits on S(6) and S(7) are due to Fredricksen and Sweet (2000).


See also

Ramsey Number, Ramsey's Theorem, Schur's Problem, Schur's Ramsey Theorem

Explore with Wolfram|Alpha

References

Abbott, H. L. and Hanson, D. "A Problem of Schur ad its Generalizations." Acta Arith. 20, 175-187, 1972.Abbott, H. L. and Moser, L. "Sum-Free Sets of Integers." Acta Arith. 11, 392-396, 1966.Baumert, L. D. and Golomb, S. W. "Backtrack Programming." J. Ass. Comp. Machinery 12, 516-524, 1965.Beutelspacher, A. and Brestovansky, W. "Generalized Schur Numbers." In Combinatorial Theory. Proceedings of a Conference Held at Schloss Rauischholzhausen, May 6-9, 1982. Berlin: Springer-Verlag, pp. 30-38, 1982.Exoo, G. "A Lower Bound for Schur Numbers and Multicolor Ramsey Numbers of K_3." Electronic J. Combinatorics 1, No. 1, R8, 1-3, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1r8.html.Fredricksen, H. "Schur Numbers and the Ramsey Numbers N(3,3,...,3;2)." J. Combin. Theory Ser. A 27, 376-377, 1979.Fredricksen, H. and Sweet, M. M. "Symmetric Sum-Free Partitions and Lower Bounds for Schur Numbers." Electronic J. Combinatorics 7, No. 1, R32, 1-9, 2000. http://www.combinatorics.org/Volume_7/Abstracts/v7i1r32.html.Guy, R. K. "Schur's Problem. Partitioning Integers into Sum-Free Classes" and "The Modular Version of Schur's Problem." §E11 and E12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 209-212, 1994.Radziszowski, S. P. "Small Ramsey Numbers." Electronic J. Combin. 1, DS1 1-29, Rev. Jul. 5, 1999. http://www.combinatorics.org/Surveys/.Schur, I. "Über die Kongruenz x^m+y^m=z^m (mod p)." Jahresber. Deutsche Math.-Verein. 25, 114-116, 1916.Sloane, N. J. A. Sequences A030126 and A045652 in "The On-Line Encyclopedia of Integer Sequences."Whitehead, E. G. "The Ramsey Number N(3,3,3,3;2)." Disc. Math. 4, 389-396, 1973.

Referenced on Wolfram|Alpha

Schur Number

Cite this as:

Weisstein, Eric W. "Schur Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SchurNumber.html

Subject classifications