1. Graph Coloring
Complete disorder is impossible. - T.S. Motzkin, on the theme of Ramsey Theory
Ramsey's Theorem¶
(Multicolor Triangle Ramsey's Theorem) For every positive integer \(r\), there is some integer \(N=N_r\) such that if each edge of \(K_N\) is colored using one of the \(r\) colors, then there will be a monochromatic (one color) triangle.
First, it's clear that if \(r=1\), then \(N_r=3\) simply satisfy the condition since there is only one color. We want to prove a non-trivial case when \(r=2\). When \(N=5\), we can give a construction where there is no monochromatic triangle like this:
This graph suggest that \(N_2 > 5\), since it provides a counterexample for \(N_2 = 5\). However, \(N_2=6\), which means that no matter how we color \(K_6\), there will be a triangle with edges sharing the same color!
If we see people as vertices and mutual friendship as the edges of a graph, this theorem tells us that among any \(6\) people, there must be a group of \(3\) that are friends of one another or that are complete strangers.
Interesting! But how do we prove this? First, we need to know pigeonhole principle:
(Pigeonhole Principle) If \(n=km+t\) items \((k,t>0)\) are put into \(m\) containers, at least one of the containers will contain \(k+1\) items.
Proof: Suppose the \(i\)-th container contain \(c_i\) items and all containers contain less than \(k+1\) items, then:
Contradiction!
It is not hard to further show that the maximum value of \(k+1\) in this theorem is \(\lceil n/m\rceil\) . Intuitively, the principle tells us that the larger number of items we have, there will be a container with more items in it. Now we can go back to the original problem.
Proof¶
Proof: For the \(5\) edges that have vertex \(1\), by pigeonhole principle, at least \(3\) of them will have the same color! Since the labelings don't matter, let's say the three edges are \((1,2),(1,4)\) and \((1,5)\) are colored red.
Now:
- If \((2,5)\) is red. We have \((1,2),(1,5),(2,5)\) a red triangle. We can get similar red triangles if either \((2,4)\) or \((4,5)\) is red.
- If none of \((2,3),(2,4),(3,4)\) is red, then they must be all blue. \((2,3),(2,4),(3,4)\) indeed forms a all blue triangle!
Thus, in all cases we have found a monochromatic triangle, and \(N(2)=6\) is proved! Now we can move on to the more generalized case and try proving it with the same idea and induction on \(r\).
Suppose the claim is true for \(r-1\) colors, which means that we can find a monochromatic triangle in any \(r-1\) colored complete graph of \(N_{r-1}\) vertices. It is left to somehow reduce a larger graph into a case like that, then we are done.
Notice how we reduce the \(N=6,r=2\) case to \(N=3,r=1\) by pigeonhole? We can do it again! If we take \(N\) large enough, there will be more than \(N_{r-1}\) edges of the same color coming out from vertex \(1\). Then for the \(N_{r-1}\) other vertices in these edges, the edges between them cannot be of the same color, which reduces the coloring among them into \(r-1\) colors. Finally, we can get a monochromatic triangle in them following by our induction. Numerically, the large enough \(N\) is \(N_r=r(N_{r-1}-1)+2\). The readers can verify that this suffices for our pigeonhole to work.
Variations¶
There are some more variations of this theorem, which can be proven by applying the pigeonhole principle inductively in a similar style as above.
- (Ramsey's Theorem) For every \(k\) and \(r\) there exist some integer \(N=N(k,r)\) such that if each edge of \(K_N\) is colored using one of the \(r\) colors, then there is a monochromatic \(K_k\).
- (Ramsey's Number) For every \(r\) and \(b\) there exist an integer \(n=R(r,b)\) such that if each edge of \(K_N\) is colored either blue or red, either a red monochromatic subgraph \(K_r\) or a blue monochromatic subgraph \(K_b\) exists.
Though it is not difficult proving such integer exists, finding the exact Ramsey number is extremely hard and mathematicians have been working on this problem for decades! In fact, people still haven't found the value of \(R(5,5)\) though it has been proven to be no less than 43 (Geoffrey Exoo (1989)) and no greater than 48 (Angeltveit and McKay (2017)).
Ramsey's number¶
We can use an idea similar to pigeonhole principle to set up an upper bound for Ramsey's number!
Lemma: \(R(s,t)\le R(s,t-1)+R(s-1,t)\)
Proof: Suppose \(n=R(s,t-1)+R(s-1,t)\) and we pick a vertex \(v\) from the complete graph \(K_n\). we can classify the other vertices into two different sets \(A\) and \(B\), based on the color of the edge that connects them with \(v\) are red or blue. Let \(a,b\) be the size of the two sets, we have \(a+b=n-1\).
If \(a< R(s,t-1)\) and \(b<R(s-1,t)\), then \(a+b\le R(s,t-1)-1+R(s-1,t)-1=n-2\), contradiction!
Thus, either \(a\ge R(s,t-1)\) or \(b\ge R(s-1,t)\), by induction we will have a red \(K_s\) clique or a blue \(K_t\) clique.
Claim: \(R(s,t)=R(t,s)\)
This claim should be quite straightforward by symmetry.
Claim: \(R(2,t)=t\)
(Upper bound on Ramsey's numbers): \(R(s,t)\le \binom{s+t-2}{s-1}\)
Hint: Try applying the lemma and notice that
Proof: This holds when \(s=1,2\), and we can continue by induction. Suppose the upper bound holds for \(s+t\le k\), then for \(s+t=k+1\):
Examples: Let's compute some upperbounds using our formula! We have
Remember the party of 6 people where we must have a friend group or a stranger group of 3? This inequality is exactly what we did to prove that thing! In fact, we have equality in this case.
Schur's theorem¶
We will end this blog with another problem that seems unrelated to graph theory at all.
(Schur's Theorem) For every positive integer \(r\), there exists a possible integer \(N=N(r)\) such that each element of \([N]\) is colored using oe of \(r\) colors, then there is a monochromatic solution to \(x+y=z\) (\(x,y,z\) have the same color).
Proof: Assume we have the coloring \(\phi\), for \([N]\), then for each edge of a complete graph we color the edge \((i,j)\) with the color \(\phi(j-i)\) when \(i<j\).
By Ramsey's Theorem, there is a monochromatic triangle, so there exist \(i<j<k\) such that
Take \(x = j-i,y=k-j,z=k-i\), then \(\phi(x)=\phi(y)=\phi(z)\) and \(x+y=z\).
"Now that we proved Schur’s theorem, let us pause and think about what did we gain by translating the problem to graph theory? We were able to apply Ramsey’s theorem, whose proof considers restrictions to subgraphs, which would have been rather unnatural if we had worked exclusively in the integers. Graphs gave us greater flexibility." - Yufei Zhao
Problems¶
Show that \(R(t,t) \le 2^{2t}\) . Then show that \(R(t,t)\ge 2^{t/2}\) for \(t\ge 3\).
Hint: For the second bound, think about random coloring of the edges of \(K_{2^{t/2}}\) . Then estimate the probability of having no monochromatic \(K_t\) in our graph. This is an application of probablistic method in combinatorics, which we will talk more about in future blogs.
(IMO 1964/4) \(17\) people correspond by mail with one another—each one with all the rest. In their letters only \(3\) different topics are discussed. Each pair of correspondents deals with only one of these topics. Prove that there are at least \(3\) people who write to each other about the same topic.
Hint 1: Generalize the definition of Ramsey's number to 3-color so we have \(R(a,b,c)\). What are we trying to prove in this problem?
Hint 2: Try to get an upper bound for \(R(a,b,c)\) expressed by \(R(a-1,b,c),R(a,b-1,c),R(a,b,c-1)\).