The problem
Show that $\mathcal{R}(3,3,3)=17$
The story behind the problem and some notation
It was first proven by Greenwood and Gleason in 1955 in their paper Combinatorial relations and chromatic graphs. Later, in 1984 Sun and Cohen published an easy proof of the Greenwood-Gleason evaluation of the Ramsey number $\mathcal{R}(3,3,3)$. I can understand this proof, but I don't like it, because in my opinion it lacks intuition. Instead, I found another proof of the above result in Problems in Combinatorics and Graph Theory book by Ioan Tomescu (page 324).
Firstly, let me explain the notation, which I used above:
Ramsey's Theorem for c colors states that:
For every positive integer $c \geq 2$ and positive integers $n_{1},n_{2}, \cdots ,n_{c} \geq 2$ there exists a (minimal) positive integer $\mathcal{R}(n_{1},n_{2}, \cdots ,n_{c})$ with the following property:
If we color the edges of a complete graph of $\mathcal{R}(n_{1},n_{2}, \cdots ,n_{c})$ vertices with colors $1,2, \cdots , c$ then for some $i \in \{1,2, \cdots c\}$ there exists a complete subgraph with $n_{i}$ vertices whose edges are $i$-colored.
So, to prove $\mathcal{R}(3,3,3)=17$, we have to 3-color the edges of a $K_{16}$ avoiding monochromatic triangles. The three colored $K_{16}$ without monochromatic triangles that you get from Sun and Cohen's coloring is the following
$\mathcal{R}(3,3,3)>16$">
My question
Tomescu in his proof uses the following coloring:
Let $P$ be a pentagon and $M=\{1,2,3,4,5\}$ the set of its vertices. Let $X$ be the set of vertices of the graph $K_{16}$ and $Y$ be the set of subsets of $M$ with even cardinality. Let $f$ be any bijection from $X$ to $Y$. The edges of $K_{16}$ will be colored as follows: If $a,b \in X$ and $a \neq b$ color the edge joining $a$ and $b$ according to the following rule:
- with color $c_{1}$ if $f(a) \triangle f(b)$ is a side of $P$
- with color $c_{2}$ if $f(a) \triangle f(b)$ is a diagonal of $P$
- with color $c_{3}$ if $|f(a) \triangle f(b)|=4$
where $f(a) \triangle f(b)$ represents the symmetric difference between the vertex sets $f(a)$ and $f(b)$, which must clearly be an even number of vertices of $P$, and in the case of 2 vertices we treat it as an edge.
I am having trouble understanding the argument that he uses in order to prove that there are no monochromatic triangles by contradiction. The argument goes like this:
Suppose that there is a triangle with sides colored $c_{1}$ and having vertices $a,b,c$. It can be seen that $f(a) \triangle f(b), f(a) \triangle f(c)$ and $f(b) \triangle f(c)$ are sides of the polygon $P$.
But $$(f(a) \triangle f(b)) \triangle (f(b) \triangle f(c)) = f(a) \triangle f(c)$$ and thus $ f(a) \triangle f(c)$ cannot be a side of the polygon $P$. In fact, if the sides $f(a) \triangle f(b)$ and $f(b) \triangle f(c)$ have a common vertex, then their symmetric difference is a diagonal of the pentagon $P$ and hence the edge joining $a$ and $c$ is colored $c_{2}$. If the sides have no common vertex, then their symmetric difference has cardinality 4 and thus the edge joining $a$ and $c$ is colored $c_{3}$, which is a contradiction. An analogos argument can be used if it is supposed that the monochromatic triangle is colored $c_{2}$ or $c_{3}$.
- Why $ f(a) \triangle f(c)$ cannot be a side of the polygon?
- Why is it true that if two sides have a common vertex then its symmetric difference is a diagonal?
- Why is it true that if they do not have a common vertex then its symmetric difference is of cardinality 4?
I am thankful for any suggestions on the problem!
Best Answer
This proof considers the even-sized subsets of vertices of a pentagon. There are 16 such subsets: The empty set, the five sides of $P$, the five diagonals of $P$, and the five sets of size 4.
Each subset corresponds to a vertex in the graph we want to color. The color of the edge between two vertices is found by considering the symmetric difference of their two subsets.
The symmetric difference operation $\triangle$ takes any two such subsets to a third. If the subsets are different, the result cannot be empty, and so must be one of the other types: a side, a diagonal, or size 4. The coloring strategy is simply to use one color for each of these three types.
Any triangle $\{a,b,c\}$ in the graph we are coloring consists of three edges, colored according to the type of $f(a) \triangle f(b)$, the type of $f(b) \triangle f(c)$, and the type of $f(a) \triangle f(c)$.
This is easy to reason about, because the identity $$ \underbrace{(f(a) \triangle f(b))}_{\mbox{subset 1}} \; \triangle \; \underbrace{(f(b) \triangle f(c))}_{\mbox{subset 2}} = \underbrace{f(a) \triangle f(c)}_{\mbox{subset 3}} $$ tells us that if there is a monochromatic triangle, then there must be two subsets of the same type whose symmetric difference is also of the same type.
But the symmetric difference of two sides is either a diagonal or of size 4, depending on whether the sides shared a vertex or not.
Similarly, the symmetric difference of two diagonals is either a side or of size 4, depending on whether the diagonals shared a vertex or not.
And finally, the symmetric difference of two distinct subsets of size 4 (so each subset is only missing a single vertex) has to be a subset of size 2 (namely the two missing vertices), and is thus either a side or a diagonal.
$\scriptsize\mbox{(You might wonder whether the final coloring of the graph is symmetric in all three colors, since it is clearly symmetric}$ $\scriptsize\mbox{in the first two (by rearranging the pentagon to make the diagonals be the sides), and surprisingly, the answer is yes!)}$