Theorem : Show that if the edges of K

_{6}are colored with two colors, then there will be a monochromatic triangle_{ }**Problem 1 : Also show that K**

_{6}is minimal with property
Proof :

• Let

**v**be any vertex of K_{6}
• 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

_{5}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

_{9}are colored with red and blue, then there will be a red K_{3}or a blue K_{4}
• Show
that K

_{9}is minimal with this property
Proof
:

• Assume
that the edges of K

_{9}are colored with red and blue.
• If
at any vertex of K

_{9}there are four red edges, as in figure 4.3.3, then there will be a red triangle or a blue K_{4}.
• This
must be true since if any of the dotted edges is red, there is a red K

_{3}.
• If all of the dotted edges are blue, they form
are blue K

_{4}.
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

_{1}with two colors contains a red K_{1}or a blue K_{n}.
• This
is true because K

_{1}has no edges, so all the edges of K_{1}are red.
• Also,
r(2,n) = n, because any edge coloring of K

_{n}with red and blue contains a red K_{2}, 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}.**dan anda bisa menemukan artikel Ramsey Theory ini dengan url**

__Ramsey Theory__**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.

## 0 komentar:

Posting Komentar