2
$\begingroup$

The question is about Exercise (b).

Exercise (a). Let $k,l$ and $m$ be positive integer. Show that $r(k,l,m)$ exists and that $r(k,l,m)\leq r(k,r(m,l))$.

Here $r(k,l,m)$ is Ramsey’s number over three colours, so that when colouring a graph $K_c$, there exists either a blue $K_k$, a red $K_l$ or green $K_m$.

Exercise (b). Find a value of $n$ such that if the numbers $1,2,...,n-1,n$ are drawn in three different colours, then there exist $x,y$ and $z$ (not necessarily distinct) so that $x+y=z$.

Solution for (a). By Ramsey's theorem, we know that $r(l,m)=n$ exists for complete graphs $K_{n'\geq n}$ that consist of edges coloured in red and green. Since $n\in \Bbb Z^+$, by Ramsey's theorem, we conclude that $r(k,r(l,m))=r(k,n)=c$ exists for complete graphs $K_{c'\geq c}$ that consist of edges coloured in blue, red and green, where red and green are considered one colour. Thus, Let a complete graph $K_c$ be coloured in blue, red and green. From the existence of $r(k,r(l,m))$, we have a blue $K_k$ in $K_c$ or a red and green $K_n$ in $K_c$. If we have a blue $K_k$, we are done; otherwise, we obtain a red and green $K_n$ that contains either a red $K_l$ or a green $K_m$ from the fact that $r(l,m)=n$. That proves the existence of $r(k,l,m)$. Therefore, $$r(k,l,m)\leq c=r(k,r(l,m))$$ $$\therefore r(k,l,m)\leq r(k,r(l,m)).$$


Now to section (b) – I have been trying for hours to connect the colouring of the consecutive number $1,2,...,n-1,n$ with the result from section (a), but with no success. Now I am trying to find a connection between the sum $x+y$ with $r(l,m)$ from the inequality $r(k,l,m)\leq r(k,r(l,m))$, with the possibility that $m=l$, but I have not got an idea how it relates to existence of a number $z$ from the set $\{1,2,...,n-1,n\}$, so that $x+y=z$.

Any help would be appreciated.

$\endgroup$
10
  • 1
    $\begingroup$ @Shaun Ok. Thank you. $\endgroup$ Jun 1 at 19:33
  • 3
    $\begingroup$ hi Lord Mansfield. what does $r(k,l,m)$ denote? $\endgroup$ Jun 1 at 19:44
  • 2
    $\begingroup$ Did you mean not necessarily distinct? $\endgroup$ Jun 1 at 19:55
  • 2
    $\begingroup$ Saying they're "unnecessarily distinct" says they are distinct but need not have been. Surely you meant "not necessarily distinct". $\endgroup$ Jun 1 at 20:02
  • 1
    $\begingroup$ r(k,l,m) is Ramsey’s number over three colours, so that when colouring a graph $K_c$, there exists either a blue $K_k$, a red $K_l$ or a green $K_m$. $\endgroup$ Jun 1 at 20:51

1 Answer 1

2
$\begingroup$

Let $n=r(3,3,3)-1$. Given a colouring of the numbers $1,2,3,\dots,n$, colour the edges of the complete graph on the vertex set $\{0,1,2,\dots,n\}$ by giving the edge $\{i,j\}$ the colour of the number $|i-j|$. If there is a monochromatic triangle with vertices $i\lt j\lt k$, then $x=j-i$, $y=k-j$, $z=k-i$ is the desired solution.

I'm sure this is what @aerile was hinting at in his answer which was deleted by a gang of vandals.

$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$ Jun 2 at 7:04

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.