5
$\begingroup$

I'm trying to prove the following statement

There is an integer $n_0$ such that for any $n\ge n_0$, in every $9$-coloring of $\{1,2,3,\dots,n\}$, one of the $9$ color classes contains $4$ integers $a,b,c,d$ such that $a+b+c=d$.

I thought about taking $\{1,2,\dots,n\}$ to be vertices of a graph where edges connect vertices of the same color. Then I tried to use Ramsey theorem, but to no avail. I thought also about Schur theorem and tried to find some generalization of it, but got nothing.

How should one prove the statement?

Please help, thanks!

$\endgroup$
  • $\begingroup$ In a 9-coloring of $\{1,2,...,n\}$ can any colors be assigned to each $k$ [so giving $9^n$ colorings in all], or are there restrictions such as that $k$ and $k+1$ have different colors? $\endgroup$ – coffeemath Apr 10 '16 at 17:00
  • $\begingroup$ @coffeemath, each coloring that uses 9 different colors is acceptable. Coloring the graph in one color, for instance, is not. $\endgroup$ – Galc127 Apr 10 '16 at 17:35
  • 1
    $\begingroup$ @Galc127: That restriction is irrelevant; if the claim is true for colourings that use all $9$ colours, then it's also true for colourings that use fewer colours. $\endgroup$ – joriki Jun 6 '16 at 5:17
  • $\begingroup$ Does "$4$ integers" mean that $a,b,c$ have to be distinct? $\endgroup$ – bof Jun 11 '16 at 22:47
  • $\begingroup$ @bof, I don't know what OP has in mind, but the original formulation of either Schur's theorem or Rado's single equation theorem does not require the integers being different. Fortunately both theorems can be easily strengthened to show the existence of monochromatic solutions consisting of distinct integers (same reference as in my answer below), but in general this additional requirement can turn Ramsey-type statements into false. $\endgroup$ – Wiley Jun 11 '16 at 23:57
3
+50
$\begingroup$

Let $n_0=R(4,\dots,4)$, where 4 appears $r-1$ times. Consider any $r$-colouring $c:\{1,\dots,n\}\to\{1,\dots, r\}$. Enumerate the vertices of the graph $K_n$ by $\{1,\dots,n\}$ and colour edge $ij$ with $c(|i-j|)$. This gives a $r-1$-colouring of $K_n$. Then by definition of $n_0$, we must have a $K_4$ with all edges monochromatic. If this $K_4$ has vertices $x\le y\le z \le w$ then $a=y-x,b=z-y,c=w-z,d=w-x$ gives a solution to your equation.

$\endgroup$
  • $\begingroup$ Thanks, this is exactly the solution I submitted two months ago (forgot to update it here...) $\endgroup$ – Galc127 Jun 12 '16 at 17:55
  • $\begingroup$ This assumes $a,b,c,d$ don't need to be distinct. For example if the vertices of $K_4$ are numbered $x=2, y=4,z=6, w=8$, then $a=2, b=2, c=2, d=6$. Or did I misunderstand something? I took the problem to want distinct $a,b,c,d\in \{1,2,...,n \}$. $\endgroup$ – M47145 Jun 12 '16 at 18:40
  • 2
    $\begingroup$ @M47145, all you need to do is to find a monotonic increasing sequence $\{a_i\}_{i=1}^{n_0}$ such that $a_l-a_k\neq a_j-a_i$ for all $1\le i<j\le k<l\le n_0$ and consider the coloring of this subset. It's easy to see $a_i=2^{i-1}$ suffices. The same arguments given by ArtW would carry through. $\endgroup$ – Wiley Jun 12 '16 at 19:14
2
$\begingroup$

Isn't this a direct consequence of Rado's single equation theorem?

(taken from the book Ramsey Theory over the Integers by B. Landmann and A. Robertson)

Rado

where $c_1=c_2=c_3=1$, $c_4=-1$ for your statement and we can take e.g., $D=\{c_1, c_4\}$. By "regular", it means your statement is true for all $r$-colorings with $r\ge1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.