[Sirius]

Bound บน

จะแสดงว่า $R(r,s)\leqslant R(r-1,s)+R(r,s-1)$
สมมติระบายสีเส้นเชื่อมทุกเส้นใน Complete Graph ที่มี $R(r-1,s)+R(r,s-1)$ จุดยอด ด้วยสีแดง/น้ำเงิน
เลือกจุดยอดมา 1 จุดเรียกว่า A จะได้ว่า เส้นเชื่อม $R(r-1,s)+R(r,s-1)-1$ เส้นที่ผ่านจุดยอดนั้น
ต้องมีอย่างน้อย $R(r-1,s)$ เส้นเป็นสีแดง หรืออย่างน้อย $R(r,s-1)$ เส้นเป็นสีน้ำเงิน (Pigeonhole)
ถ้าเป็นกรณีแรก (อย่างน้อย $R(r-1,s)$ เส้นเป็นสีแดง)
ใน $R(r-1,s)$ จุดที่เชื่อมด้วยสีแดงกับ A จะต้องมี
complete graph size r-1 สีแดง หรือ complete graph size s สีน้ำเงิน
กรณี complete graph size r-1 สีแดง ใชัจุดทั้ง r-1 จุดนั้นกับ A จะได้ complete graph size r สีแดง
กรณี complete graph size s สีน้ำเงิน เห็นได้ชัด
กรณีที่สอง (อย่างน้อย $R(r,s-1)$ เส้นเป็นสีน้ำเงิน) เป็นไปในทำนองเดียวกับกรณีแรก

ดังนั้น $R(4,4)\leqslant R(3,4)+R(4,3)=2R(3,4)$
จะแสดงว่า $R(4,3)\leqslant 9$ นั่นคือ Complete graph ขนาด 9 จะต้องมี 3-clique สีแดง / 4-clique สีน้ำเงิน
ถ้ามีจุดที่เส้นเชื่อมเป็นสี แดง อย่างน้อย 4
จาก R(2,4)=4 จะต้องมี 3-clique สีแดง / 4-clique สีน้ำเงิน (วิธีเหมือนกับข้างบนในแต่ละกรณี)
ถ้ามีจุดที่เส้นเชื่อมเป็นสี น้ำเงิน อย่างน้อย 6
จาก R(3,3)=6 จะต้องมี 3-clique สีแดง / 4-clique สีน้ำเงิน
ถ้าเป็นสี แดง 3 น้ำเงิน 5 ทุกจุด จะได้ว่าผลรวมดีกรีสีแดง $=9\times 3=27$
จึงต้องมีเส้นเชื่อมสีแดง $27\div 2=13.5$ เส้น เป็นไปไม่ได้


Bound ล่าง

คิดว่าน่าจะไม่มีวิธีที่ดีกว่ายกตัวอย่างกรณี 17