Ramsey's Number

[Phudis]

ขอโทษนะครับ ช่วยไกด์วิธีพิสูจน์ว่า R(4,4)=18 โดยใช้หลักรังนกพิราบหน่อยครับ

[Aquila]

เห็นบ่นจะสอบแล้วเอาเฉลยไปเลยละกัน
ไปหาโหลดหลังสือเล่มนี้มา Arthur Engel - Problem Solving Strategies
(ถ้าในค่ายซื้อเล่มนี้มาแล้วก็เปิดดูเลย)

เฉลยอยู่บท Box principle หน้า 77 ข้อ 42
แต่บทพิสูจน์ใช้กราฟนะ วิธีก็พยายามพิสูจน์ตัว bound ล่าง คือ $R(4,4) > 17$
ให้ไปชนกับตัว Bound บน ซึ่ง Bound บนก็มาจาก $R(r,s) \leq R(r-1,s)+R(r,s-1)$

ทีนี้ตัวเฉลยมันใช้ pigeon ไม่เด่นชัดเท่าไร (ลงผมยังไม่เห็นคำว่า pigeon ในเฉลยเลย)
ตัว bound ล่างในเฉลย มันใช้วิธีสร้าง $G_{17}$ ขึ้นมาแล้วบอกว่า 17 node นี้ไม่มี $K_{4}$
ถ้าก๊อปแบบนี้ไปตอบต่อให้ได้คะแนนก็อาจจะได้ไม่เต็มข้อ
เพราะงั้นพยายามใช้ pigeon ให้ได้ชัดๆซักที่ในการ claim โจทย์นะ
ไม่รู้นะความคิดผม ผมก็ช่วยได้แค่นี้

ปล.เอ๊อ สอบเสร็จโพสต์ข้อสอบให้หน่อยนะ จะลองมาทำดู

[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