Ramsey Theory

  Theorem : Show that if the edges of K₆ are colored with two colors, then there will be a monochromatic triangle

Problem 1 :  Also show that K₆ is minimal with property

Proof  :

•       Let v be any vertex of K₆

•      Either there are at least three red edges incident with v or at least three blue edges incident with v , since v has degree 5

•      We assume there are  three red edges

•      If  any of the dotted edges in Figure 4.3.1 is red, there is a red triangle.

•      If all are blue, they form a blue triangle.

Figure 4.3.2 shows a coloring of K₅ with two colors and no monochromatic triangle.

Teorema 4.3.1

  “ For every number n, there is a number r(n) such that any edge-coloring of the complete graph with r(n) vertices using red and blue must contain either a red K_n or a blue K_n “

Problem 2:

•      Show that if the edges of K₉ are colored with red and blue, then there will be a red K₃ or a blue K₄

•      Show that K₉ is minimal with this property  

Proof :

•      Assume that the edges of K₉ are colored with red and blue.

•      If at any vertex of K₉ there are four  red edges, as in figure 4.3.3, then there will be a red triangle or  a blue K₄.

•      This must be true since if any of the dotted edges is red, there is a red K₃.

•       If all of the dotted edges are blue, they form are blue K₄.

The Ramsey number  r(m,n) is the smallest number with this property that any edge coloring of the complete graph with r(m,n) vertices using red and blue must contain a red K_m or a blue K_n.

We have just shown that r(3,4)=9. Very few of the Ramsey Numbers are actually known.

•      Notice  that r(1,n)=1, since any edge coloring of K₁ with two colors contains a red K₁ or a blue K_n .

•      This is true because K₁ has no edges, so all the edges of K₁ are red.

•      Also, r(2,n) = n, because any edge coloring of K_n with red and blue contains a red K₂, that is, it contains a red edge, it contains a blue K_n.

Teorema 4.3.2:

   “For every m and n, there exist the Ramsey number r(m,n) such that any edge-coloring of K _r(m,n) with red and blue contains a red K_m or a blue K_n. Furthermore, r(m,n) satisfies the inequality. r(m,n) ≤ r(m-1,n) + r(m,n-1)”.

Proof :

We proceed by induction on k= m+n. The smallest value that makes sense is k=4, for m=2, and n=2. Then r(2,2) = 2

            ≤ 1+1

            = r(1,2) + r(2,1)

Now suppose that the theorem is true for all values less than k.

•      Let G be the complete graph r(m-1,n)+r(m,n-1) vertices.

•      Assume that the edges of G are colored with red and blue.

•      Let v be any vertex of G.

•      At v either there are r(m-1,n) red edges or r(m,n-1) blue edges.

To see that this is true, consider that the degree of v is r(m-1,n)+r (m,n-1) – 1.

Case1

1.      If there are r(m-1,n) red edges   at v, the subgraph H induced by the other endpoints of these edges is a complete graph with r(m-1,n) vertices that is edge colored with red and blue.

2.      Thus either there is a red K_m-1 in H, that together with v forms a red K_m in G, or there is a blue K_n in H and hence also in G.

3.      Therefore, if there are r(m-1,n) red edges at v , either G contains a red K_m or a blue K_n .

Case 2

1.      If there are r (m, n-1) blue edges at v, the subgraph I induced by the other endpoints of these edges is a complete graph with r(m,n-1) vertices that is edge colored with red and blue.

2.      Thus either there is a red K_m  in I and hence in G, or there is a blue K_n-1 in I, that together with v forms a blue K_n in G.

3.      Therefore, if there are r(m,n-1) blue edges at v, either G contains a red K_m or a blue K_n

·         And we have established that  r (m, n) ≤ r(m-1,n) + r(m,n-1)

•      If we define r(n,n)=r(n) ,Theorem 4.3.1 is now a special case of Theorem 4.3.2

Problem 3:

   Show that if the edges of K_5,5 are colored with two colors,  there will be a monochromatic K _2,2

Proof :

•      There are 25 edges in K_5,5

•      One of the colors will go to at least 13 edges

•      Since each edges has no endpoint in each of the partite sets, we can look at the number of edges incident with the five vertices in one of the sets.

•      Notice that the coloring will contain a monochromatic K_2,2 precisely when two of these vertices have two neighbors in common.

•      There are three cases

Case 1

One vertex v has degree 5 in S. Since the average degree of the remaining four vertices is two, at least one has degree at least two, call it w. Then v and w have two neighbors in common, and there is K_2,2.

Case 2

One vertex has degree 4 in S. Since there are still at least nine edges, at least one remaining vertex w has degree 3 in S, and there is a K_2,2 .

Case 3.

At least three vertices have degree at least three in S, and there is a K_2,2 .

Related Post