Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm having problem proving the ramsey number of R(3,5) = 14. Below is my proof.

Proof. Let $v_0$ be a vertex from a $k_{14}$ vertices. The vertices incident to $v_0$ are $v_1, v_2, \cdots , v_{13}$ with edges coloured with either red or blue.

By Pigeonhole principle, there are at least $7$ ($kn+1=13,6\cdot 2+1=13,6+1=7$) edges coloured with either blue or red. Assume it to be coloured with blue. And let these be edges $\{(v_0,v_1),(v_0,v_2),\cdots , (v_0,v_7)\}$. If any of the edges between $v_1,v_2,\cdots , v_7$ is coloured with blue then we have a 3-blue clique, if none of them, then we have a 7-red clique. $\blacksquare$

Now, I'm confused. I get R(3,7) in my proof not R(3,5). Any suggestion?

share|improve this question
    
Indeed, yuo show that $R(3,7)\le 14$. The same approach with a $k_{10}$ shows $R(3,5)\le 10$. –  Hagen von Eitzen Sep 4 '12 at 14:57
    
@HagenvonEitzen $R(3,5) = 14$ and $R(3,7)=23$, so something has gone wrong. –  Austin Mohr Sep 4 '12 at 14:59
2  
The problem isn't symmetric in "red" and "blue" ... so you can't say "Assume ... colored with blue". You have to consider two cases. –  martini Sep 4 '12 at 15:01
    
Ok, if I consider two cases. Then, If I can have 7 edges for case 1, then the other case would have 6 edges? Now, if I'm going to consider case 2 with 6 edges. I got R(3,6). Am I right? –  Al-Ahmadgaid Asaad Sep 4 '12 at 15:04
1  
Here is a solution using the inequality $R(m,n) \leq R(m-1,n) + R(m,n-1)$ and an explicit construction: cut-the-knot.org/arithmetic/combinatorics/Ramsey53.shtml –  Austin Mohr Sep 4 '12 at 15:08

1 Answer 1

up vote 4 down vote accepted

First, let's verify that $R(3,5)>13$. As is typical for explicit lower bounds in Ramsey theory, we show this inequality by exhibiting a concrete $\{\mbox{red},\mbox{blue}\}$-coloring of $K_{13}$ without a red triangle or a blue $K_5$.

A nice way of describing this coloring is as follows: Identify the vertices of $K_{13}$ with the elements of $\mathbb Z/13\mathbb Z=\{0,1,\dots,12\}$, and color red the edge between two vertices $i$ and $j$ iff their difference is a (non-zero) cubic residue mod $13$.

The cubic residues modulo 13 are $1=1^3=3^3=9^3$, $5=7^3=8^3=11^3$, $8=2^3=5^3=6^3$, and $-1=4^3=10^3=12^3$. Note that since $-1$ is a cubic residue, it is immaterial the order in which we consider $i$ and $j$ when taking their difference.

It is easy to see that this coloring does not admit a red triangle.

To see that we do not have a blue $K_5$, we argue that of any $5$ vertices we choose, two must be a cubic residue apart. By symmetry, we may assume that $0$ is one of the chosen vertices. If any of $1,5,8,12$ is chosen among the remaining four vertices, we are done. Otherwise, they must be chosen among the three "clusters" $2,3,4$, and $6,7$, and $9,10,11$. Two vertices must belong to the same cluster (pigeonhole principle). If they are consecutive, we are done. So we may assume they belong to a cluster of three, and are two apart. By symmetry, we may assume they are $2$ and $4$. This eliminates $3,7,10$ (because of $2$) and $9$ (because of $4$). We are now forced to pick $6$ and $11$ as the remaining vertices, but they are $5$ apart, and we are done.


Second, we verify that $R(3,5)\le 14$. The simplest argument is by using the inequality $R(3,5)\le R(3,4)+R(2,5)$. In general, we have $R(m,n)\le R(m-1,n)+R(m,n-1)$. This has been asked on this site before, a proof can be seen here.

Briefly, if $N=R(m-1,n)+R(m,n-1)$, and $K_N$ is $2$-colored, we can fix a vertex $v$, and call $A$ the set of vertices joined to $v$ by a red arc, and $B$ the set of vertices joined to it by a blue arc. Then $|A|\ge R(m-1,n)$ or $|B|\ge R(m,n-1)$. Otherwise, $N-1=|A|+|B|\le (R(m-1,n)-1)+(R(m,n-1)-1)=N-2$. In the first case, we either have a blue $K_n$ among the vertices in $A$, and we are done, or we have a red $K_{m-1}$. But all these vertices are joined to $v$ by a red arc, so adding $v$ to them gives us a red $K_m$. The other case is similar.

Clearly, $R(2,5)=5$. We are done if we show that $R(3,4)=9$. The argument above only gives $R(3,4)\le R(3,3)+R(2,4)=6+4=10$. To see that $9$ vertices suffice, note that by the general argument we gave, if we have a $2$-coloring of $K_9$ without red triangles or blue $K_4$s, we must have that the blue degree of each vertex is $5$ and their red degree is $3$. But this is impossible, because the sum of the red degrees is twice the number of red edges, but $9\times 3=27$.

In general, what this says is that if both $R(n-1,m)$ and $R(n,m-1)$ are even, then $R(n,m)<R(n-1,m)+R(n,m-1)$.


This completes the proof. Let me add some references. The first argument in print showing that $R(3,5)=14$ is from

For an up-to-date survey of small Ramsey numbers, including references, see

  • Stanislaw Radziszowski. Small Ramsey Numbers, The Electronic Journal of Combinatorics, Dynamic survey DS1, latest version: August 22, 2011.

It is always nice to see a picture of the graphs one is describing. The coloring of $K_{13}$ I mentioned above can be seen here (with red and blue interchanged).

Finally, let me mention that the argument sketched in the question is flawed, because there is no symmetry in the roles of red and blue (it is certainly easier to ensure the existence of a blue triangle than the existence of a blue $K_5$).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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