0
$\begingroup$

Let us denote by $n=r(k_1,k_2,\ldots,k_s)$ the minimal number of vertices such that for every coloring of the edges of the complete graph $K_n$ by $s$ different colors, there is some color $1\le i\le s$ such that the $i$-th graph contains a $k_i$ clique. By the $i$-th graph we mean the graph on the given $n$ vertices and this edges of the complete graph that are colored $i$.

let us denote $r_s = r(3,3,3,3,\ldots)$, with $3$ appearing $s$ times.

a) show that $r(k,s)$ is exactly the regular Ramsey number.
b) show that $r_s \le s(r_{s-1}-1)+ 2$.
c) show that $r_s \le s! \cdot e + 1$.
d) show that $r_3 \le 17$.

Now I don't get how to even start solving this, considering (c) for example, I don't see how we can achieve a factorial... Any hints for the solution, or a better explanation of the definition will be really helpful, thank you!

$\endgroup$
5
  • $\begingroup$ Here is the basic tutorial and quick reference for writing mathematics here. $\endgroup$ – Brian M. Scott Dec 7 '14 at 9:09
  • $\begingroup$ @BrianM.Scott Thank you! $\endgroup$ – Tai Dec 7 '14 at 9:10
  • $\begingroup$ @Jobin: Please stop restoring the first paragraph, which is no longer relevant, and substituting ASCII workarounds like <= for normal mathematical symbols like $\le$. $\endgroup$ – Brian M. Scott Dec 7 '14 at 9:16
  • $\begingroup$ When you sey you "don't get how to even start", do you mean to say that you can't even do part a)? How was the "regular Ramsey number" defined in your course? $\endgroup$ – bof Dec 7 '14 at 9:16
  • $\begingroup$ @BrianM.Scott: I wasn't restoring it. I just didn't realize that you were editing it too. Sorry for the trouble. $\endgroup$ – Train Heartnet Dec 7 '14 at 10:18
3
$\begingroup$

The definition seems clear enough, especially if you've seen Ramsey numbers before. The questions are all about the special case of $r_s$, which is just the smallest $n$ such that every coloring of the edges of $K_n$ with $s$ colors contains a monochromatic triangle, that is, a triangle whose edges are all the same color; e.g., $r_1=3$, $r_2=6$.

a) I hope this follows directly from the definitions.

b) Have you seen a proof of an upper bound for the "regular" Ramsey numbers? This is a lot like that. Pick a point $v$, consider the edges incident with $v$, and use the pigeonhole principle to show that enough of them are of the same color. [*]

c) This is misstated. The upper bound should be $\lfloor s!e\rfloor+1$ where $e=2.718\dots$ is the base of natural logarithms and $\lfloor x\rfloor$ is the floor function; e.g., if $s=2$ then $\lfloor s!e\rfloor+1=6$. Prove by induction on $s$, using b) and the fact that, for $s\ge1$, $$\lfloor s!e\rfloor=\frac{s!}{0!}+\frac{s!}{1!}+\frac{s!}{2!}+\cdots+\frac{s!}{s!}.$$

d) Just set $s=3$ in c) and do the calculation.

[*] Consider an integer $s\gt1$, let $n=s(r_{s-1}-1)+2$, and suppose the edges of $K_n$ are colored with $s$ colors. Choose a vertex $v$ and consider the $n-1=s(r_{s-1}-1)+1$ edges incident with $v$. By the pigeonhole principle, at least $r_{s-1}$ of those edges have the same color, which I will call "red". That is, there is a set $W\subset V(K_n)$ of size $|W|=r_{s-1}$ such that each vertex in $W$ is joined to $v$ by a red edge. If two vertices $w_1,w_2\in W$ are joined to each other by a red edge, then $v,w_1,w_2$ are the vertices of a red triangle. On the other hand, if no two vertices in $W$ are joined by a red edge, then the edges of the complete graph on $W$ are colored with $s-1$ colors, and the existence of a monochromatic triangle follows from the definition of $r_{s-1}$. This proves that $r_s\le n=s(r_{s-1}-1)+2$.

$\endgroup$
4
  • $\begingroup$ I still don't get how you can solve b) using the upper bound, on the proof I've seen in order to prove that we first use the fact that r(k,l)≤r(k-1,l)+r(k,l-1) then we use the induction step, but here we can't really do that, because that theorem doesn't apply here ... $\endgroup$ – Tai Dec 7 '14 at 19:56
  • $\begingroup$ @Tai OK, I edited a proof of b) into my answer. Do you see any similarity between the proof of b) and the proof of the inequality $r(k,l)\le r(k-1,l)+r(k,l-1)$? $\endgroup$ – bof Dec 7 '14 at 20:20
  • $\begingroup$ I am not sure I get how your proof works. I mean, I get what you did by taking a vertex and showing that it's either a part of a triangle, or there is one in the complement, but I don't see how you can assume that proves that rs≤n=s(rs−1−1)+2. I don't really understand the inductive step here. the s(rs−1−1) makes sense considering you have s options to chose that vertex, but why "+2" ? $\endgroup$ – Tai Dec 8 '14 at 7:03
  • $\begingroup$ @Tai $r_s$ is defined as the least number $n$ with the property "any coloring of the edges of $K_n$ with $s$ colors contains a monochromatic triangle". I defined a certain number $n$ (in fact I defined $n$ to be $s(r_{s-1}-1)+2$) and showed that $n$ has the above-mentioned property; since $r_s$ is defined as the least number with that property, it follow that $r_s\le n$. What is it you don't understand? $\endgroup$ – bof Dec 8 '14 at 7:15

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.