Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

JUL  01  2022  MATH  175

3 .3 A Theorem of Ramsey

Of six (or more) people, either there are three, each pair of whom are acquainted, or there are three, each pair of whom are unacquainted. We formulate it as

K6  → K3 , K3 .

Theorem.  If m ≥ 2 and n ≥ 2 are integers, then there is a positive integer p such that Kp  → Km , Kn .

Definition  (Ramsey number).  The Ramsey number r(m, n)  is the smallest integer p  such that Kp  → Km , Kn .  The Ramsey’s theorem asserts the existence of the number r(m, n)

Remark.

r(3, 3) = 6; r(3, 4) = 9; r(3, 5) = 14; r(3, 6) = 18; r(3, 7) = 23.

Example  (Page 82 # 20).  Prove that r(3, 3, 3) ≤ 17 .

Solution. So, we are trying to show that

K17  → K3 , K3 , K3 .

We prove it by contradiction,  suppose this is not possible.   Say we have  17 dots,  and we assign three

colors, RED , GREEN , BLUE , to the line segments between them .  We assume that we can not find three

dots  such  that  the  line  segments  between  them  are  the  same  color .   Fix  a  dot,  then  there  are  16  line

segments connecting this dot to other  16 dots .  By the Pigeonhole principle, at least 6 line segments will

share  the  same  color,  say  RED  for  convenience .   For  6  dots  at  the  other  side  of these  6  line  segments,

we  may  assume  that  the  line  segments  between  these  6  points  cannot  be  RED .  Otherwise  you  find  a

RED  K3,  which  implies  that  K17   → K3 , K3 , K3   is  possible .   So  we  assume  the  line  segments  between

these 6 points are either GREEN or BLUE . Then in fact, this is another Ramsey Theory, we know that

r(3, 3) = 6, which means that it is possible for  6 dots to have either there are  3 dots such that the line

segments between them are  GREEN , or there are 3 dots such that the line segments between them are

BLUE . Thus we get a contradiction, for  17 dots, you can either find 3 dots such that the line segments

between them are  RED, or  3 dots such that the line segments between them are  Green,  or  3 dots such

that the  line  segments  between them  are  Blue .   This  implies that  K17   → K3 , K3 , K3   is  possible,  which

gives r(3, 3, 3) ≤ 17.                                                                                                                                                               □