We compute Ramsey numbers in small cases

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 .

(problem 1) Show that by exhibiting an edge coloring on that does not contain a monochromatic

We now prove that .

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 .

Suppose is colored using 4 colors: yellow, green, red and blue. The smallest value of that guarantees a monochromatic is denoted . Show that
Use the fact that
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?