Schur’s theorem states that for any number of colors $c$, there is a number $N(c)$ such that if the numbers of the set $\{1, 2, \ldots, N(c)\}$ are colored using $c$ colors, then there exist monochromatic $x$, $y$, $z$ where $x + y = z$.
There’s a “standard” proof of Schur’s theorem that I’ve found in multiple sources. (Here’s one from Wikibooks; here’s another; here’s another) The idea is the following:
- Pick $N(c) = R(3, 3, \ldots, 3)$. That is, pick $N(c)$ to be the smallest number where any $N(c)$-clique whose edges are colored one of $c$ colors contains a monochrome triangle.
- Form an $N(c)$-clique as follows. The nodes are the numbers $1, 2, \ldots, N(c)$. An edge from $i$ to $j$ is given the color of the number $|j - i|$.
- Obtain a monochrome triangle in the clique consisting of nodes $a$, $b$, and $c$, where WLOG we assume $a \lt b \lt c$.
- Then $b - a$, $c - b$, and $c - a$ are all the same color, and if we pick $x = b - a$, $y = c - b$, and $z = c - a$ we have $x + y = z$.
There’s a small detail about this proof I’ve been wondering about. If you have the set $\{1, 2, \ldots, N(c)\}$ and form the clique as described above, then the number $N(c)$ itself is never used to color any of the edges, since $|i - j|$ is always between $1$ and $N(c) - 1$, inclusive. If we enlarge the clique to contain $N(c) + 1$ nodes, then all elements of the original set make an appearance somewhere as an edge in the clique.
However, if we do this, then setting $N(c) = R(3, 3, \ldots, 3)$ gives us a bigger clique than what we need. We can instead use $N(c) = R(3, 3, \ldots, 3) - 1$.
Does this edit to the “standard” proof work correctly?
I’m aware that this proof of Schur’s theorem still gives a fairly conservative upper bound on minimal size of $N(c)$, so this isn’t a major improvement over the original proof. It’s just something I’ve been curious about because I found it odd that the proof would exclude some element from participating in the clique coloring.
(It appears that some discussion to this effect appeared in the comments on this earlier question, though not in a huge amount of detail.)
Thanks!