Schur number

In discrete mathematics, the Schur numbers are those numbers which satisfy the condition of Schur's theorem and are minimal. They give a measure of how large a colored amount must be at least in order to always find a monochrome solution . In this way, statements can be made in coloring problems of planes as to whether there are colored sets for which there is no single-colored solution and thus no point on the plane can be colored. ${\displaystyle s(r)}$

definition

According to Schur's theorem, these are defined as follows: Let be a set colored arbitrarily with colors. Then is the smallest number for which different numbers do not necessarily exist, so that they are monochrome and solve the equation . ${\displaystyle s(r)\in \mathbb {Z} ^{+}}$ ${\displaystyle [1,s(r)]}$ ${\displaystyle r}$ ${\displaystyle s(r)}$ ${\displaystyle x,y,z\in [1,s(r)]}$ ${\displaystyle x,y,z}$ ${\displaystyle x+y=z}$

calculation

The only previously known Schur numbers are sufficient for with . ${\displaystyle r=1\ldots 4}$ ${\displaystyle s(1)=2,s(2)=5,s(3)=14,s(4)=45}$

Example s (2)

${\displaystyle s(2)=5}$states that to color the positive number line from the 1 with two colors, at least 5 numbers must be colored so that a single color solution for results in each case . We choose the colors red and blue and agree that all red numbers are in and all blue in . OBdA is 1 red, so . Then it follows that . , so 4 red and , so the 3 must be blue. So and . But now it follows that it must be. It remains to show that is. We choose the quantities as above and , but there is no one-color solution. must therefore be 5. ${\displaystyle x+y=z}$ ${\displaystyle R}$ ${\displaystyle B}$ ${\displaystyle 1\in R}$ ${\displaystyle 1+1=2}$ ${\displaystyle 2\in B}$ ${\displaystyle 2+2=4}$ ${\displaystyle 1+3=4}$ ${\displaystyle R=\{1,4\}}$ ${\displaystyle B=\{2,3\}}$ ${\displaystyle 1+4=5=2+3}$ ${\displaystyle s(r)\leq 5}$ ${\displaystyle s(r)\geq 5}$ ${\displaystyle R=\{1,4\}}$ ${\displaystyle B=\{2,3\}}$ ${\displaystyle s(r)}$

appraisal

Upper bound by Ramsey numbers

The chore numbers can be estimated for by the Ramsey numbers . We derive from a staining of one of the staining from, by offering the corners of the of color and then enumerate its edges. We proceed in such a way that each edge is assigned the amount of the difference between its two incident points, i.e. for the nodes and . Now every edge has a value and is colored accordingly . According to Ramsey, there is a monochrome triangle im , which, according to the definition of our coloring, corresponds to a monochrome Schur triple thus the solution. From follows . ${\displaystyle r\geq 1}$ ${\displaystyle s(r)\leq R(3;r)-1}$ ${\displaystyle r}$ ${\displaystyle \chi }$ ${\displaystyle [1,n-1]}$ ${\displaystyle r}$ ${\displaystyle K_{n}}$ ${\displaystyle K_{n}}$ ${\displaystyle 1\ldots n}$ ${\displaystyle |j-i|}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle [1,n-1]}$ ${\displaystyle \chi }$ ${\displaystyle n=R(3;r)}$ ${\displaystyle K_{n}}$ ${\displaystyle n=R(3;r)}$ ${\displaystyle s(r)\leq n-1=R(3;r)-1}$

Explicit upper bound

The Ramsey numbers allow the estimation . This results in the explicit estimate for the Schur numbers . ${\displaystyle R(3;r)\leq 3r!}$ ${\displaystyle s(r)\leq 3r!-1}$

Lower bound

Provided that applies . The inequality results from a suitable coloration . The rest is done by induction using and ${\displaystyle r\geq 1}$ ${\displaystyle s(r)\geq {\frac {3^{r}+1}{2}}}$ ${\displaystyle r+1}$ ${\displaystyle s(r+1)\geq 3s(r)-1}$ ${\displaystyle r}$ ${\displaystyle s(1)=2\geq {\frac {3^{1}+1}{2}}.}$

Guesswork and open questions

It has not yet been shown that is. ${\displaystyle s(5)=120}$

literature

• Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory . 8th chapter, 2nd edition. Wiley, New York, NY, 1990, ISBN 0-471-50046-1
• Bruce M. Landman, Aaron Robertson: Ramsey Theory on the Integers . 3rd chapter, 1st edition. AMS, Rhode Island, 2004, ISBN 0-8218-3199-2