WELCOME TO THIS BLOG!!. PLEASE ENJOY THE MENU HAS BEEN PROVIDED

Senin, 30 Juni 2014

Ramsey Theory


  Theorem : Show that if the edges of K6 are colored with two colors, then there will be a monochromatic triangle
Problem 1 :  Also show that K6 is minimal with property
Proof  :
       Let v be any vertex of K6
      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 K5 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 Kn or a blue Kn
Problem 2:
      Show that if the edges of K9 are colored with red and blue, then there will be a red K3 or a blue K4
      Show that K9 is minimal with this property  
Proof :
      Assume that the edges of K9 are colored with red and blue.
      If at any vertex of K9 there are four  red edges, as in figure 4.3.3, then there will be a red triangle or  a blue K4.
      This must be true since if any of the dotted edges is red, there is a red K3.
       If all of the dotted edges are blue, they form are blue K4.
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 Km or a blue Kn.
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 K1 with two colors contains a red K1 or a blue Kn .
      This is true because K1 has no edges, so all the edges of K1 are red.
      Also, r(2,n) = n, because any edge coloring of Kn with red and blue contains a red K2, that is, it contains a red edge, it contains a blue Kn.
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 Km or a blue Kn. 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 Km-1 in H, that together with v forms a red Km in G, or there is a blue Kn 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 Km or a blue Kn .
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 Kin I and hence in G, or there is a blue Kn-1 in I, that together with v forms a blue Kn in G.
3.      Therefore, if there are r(m,n-1) blue edges at v, either G contains a red Km or a blue Kn
·         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 K5,5 are colored with two colors,  there will be a monochromatic K 2,2
Proof :
      There are 25 edges in K5,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 K2,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 K2,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 K2,2 .
Case 3.
At least three vertices have degree at least three in S, and there is a K2,2 .

























Anda sedang membaca artikel tentang Ramsey Theory dan anda bisa menemukan artikel Ramsey Theory ini dengan url http://zakylubismy.blogspot.com/2014/06/ramsey-theory.html,anda boleh menyebar luaskannya atau mengcopy paste-nya jika artikel Ramsey Theory ini sangat bermanfaat bagi teman-teman anda,namun jangan lupa untuk meletakkan link Ramsey Theory sumbernya.

Related Post



0 komentar: