We compute Ramsey numbers in small cases
1 Ramsey Theory
In this section we consider graph colorings. That is, each edge in a graph will be assigned a particular color. The graph below is a colored with red and blue edges. The vertices represent people and the color represents whether they know each other (red) or not (blue).
The Pigeon Hole Principle suggests that in a with two colors, there must be two of the same color. Hence, in a group of three people, there are at least 2 pairs of people that know each other or two pairs of people that do not.
A fundamental question in Ramsey Theory is: how many people are needed in order to ensure that there is a subgroup of 3 people that are either mutually acquainted or mutually unacquainted? In terms of graphs with edge colorings, what is the smallest value of such that with 2 colors must contain a monochromatic ? This value of is known as a Ramsey Number and denoted
The figure above shows that .
We now prove that .
- Proof
- Consider a with edges colored red and blue. We must show that it
contains a monochromatic . Let be any vertex in the . V has 5 edges emanating
from it. By the Pigeon Hole Principle, there must be at least 3 of the same color.
Without loss of generality, assume is connected to vertices and with red edges, as pictured above. Then consider the embedded in the consisting of vertices and . If this contains a red edge, say from to , then the formed by and is monochromatic (red). If the does not contain a red edge, then IT is a monochromatic (blue). Either way, the must contain a monochromatic . Finally, since we can conclude that .
We can use more than two colors. Suppose we use green, red and blue to color the edges of . What is the minimum value of that guarantees a monochromatic ? This Ramsey Number is denoted .
How many edges must emanate from a vertex in to ensure that there are at least 17 of one color?
How many vertices must a graph have to be sure that this many edges emanate from each vertex?