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, 2022 at 19:33
  • 3
    $\begingroup$ hi Lord Mansfield. what does $r(k,l,m)$ denote? $\endgroup$ Jun 1, 2022 at 19:44
  • 2
    $\begingroup$ Did you mean not necessarily distinct? $\endgroup$ Jun 1, 2022 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, 2022 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, 2022 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, 2022 at 7:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .