จำนวนแรมซีย์

จำนวนแรมซีย์ R(m, n) ในคณิตศาสตร์เชิงการจัด หมายถึง จำนวนจุดยอดของกราฟสมบูรณ์ที่น้อยที่สุดที่เมื่อระบายสีเส้นเชื่อมด้วย 2 สีในวิธีใดๆ จะทำให้เกิดกราฟย่อยที่มีจุดยอด m จุด ซึ่งเส้นเชื่อมทุกเส้นมีสีที่ 1 หรือเกิดกราฟย่อยที่มีจุดยอด n จุด ซึ่งเส้นเชื่อมทุกเส้นมีสีที่ 2

จำนวนแรมซีย์สำหรับจำนวนที่มากกว่าสองจำนวนที่อยู่ในรูป (n1, ..., nc) จะหมายถึงจำนวนจุดยอดของกราฟสมบูรณ์ที่น้อยที่สุดที่เมื่อระบายสีเส้นเชื่อมด้วย c สีในวิธีใดๆ จะมีค่า i อย่างน้อย 1 ค่า ที่มีค่าตั้งแต่ 1 ถึง n ที่ทำให้เกิดกราฟย่อยที่มีจุดยอด ni จุด ซึ่งเส้นเชื่อมทุกเส้นมีสีที่ i

 R(3, 3) = 6 
เราสามารถพิสูจน์ได้ว่า R(3, 3) = 6 โดยสร้างกราฟที่มีจุดยอด 6 จุด แล้วระบายสีเส้นเชื่อมด้วยสีแดงและสีน้ำเงิน จากนั้นเลือกจุดยอด v ขึ้นมา จากหลักการรังนกพิราบ จะได้ว่ามีจุดยอดอย่างน้อย 3 จุดที่เชื่อมกับ v ด้วยสีเดียวกัน ซึ่งสามารถสมมติโดยไม่เสียนัยสำคัญได้ว่าเป็นสีแดง ให้จุดยอดเหล่านั้นคือ r, s และ t พิจารณาเส้นที่เชื่อม (r, s), (s, t) และ (t, r) ถ้ามีเส้นใดเป็นสีแดงก็จะเกิดสามเหลี่ยมสีแดงขึ้น แต่ถ้าทุกเส้นเป็นสีน้ำเงินก็จะเกิดสามเหลี่ยมสีน้ำเงินขึ้น

นอกจากนี้เราสามารถพิสูจน์แย้งกรณีที่มีจุดยอด 5 จุดได้ โดยระบายสีเส้นเชื่อมดังภาพ

 ทฤษฎีบท 
สำหรับกรณีที่ใช้สี 2 สี มีทฤษฎีบทว่า

 R(r, s) ≤ R(r − 1, s) + R(r, s − 1)
 2r/2 ≤ R(r, r) ≤ 4r

ซึ่งสามารถใช้ทฤษฎีบทนี้ในการจำกัดช่วงของจำนวนแรมซีย์ที่มีค่ามากๆได้

 จำนวนแรมซีย์อื่นๆ 
จำนวนแรมซีย์สำหรับค่า r และ s ตั้งแต่ 3 ถึง 10 สำหรับบางจำนวนยังไม่ทราบค่าที่แน่นอน แต่สามารถจำกัดขอบเขตได้ จำนวนแรมซีย์ R(r, s) สำหรับ r และ s ที่มีค่าน้อยกว่า 3 สามารถหาได้โดยสูตร R(1, s) = 1 และ R(2, s) = s สำหรับทุกค่า s
 r,s 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 2 1 2 3 4 5 6 7 8 9 10 3 1 3 6 9 14 18 23 28 36 40-43 4 1 4 9 18 25 35-41 49-61 56-84 69-115 92-149 5 1 5 14 25 43-49 58-87 80-143 101-216 121-316 141-442 6 1 6 18 35-41 58-87 102-165 111-298 127-495 169-780 178-1171 7 1 7 23 49-61 80-143 111-298 205-540 216-1031 232-1713 ≤ 2826 8 1 8 28 56-84 101-216 127-495 216-1031 282-1870 317-3583 ≤ 6090 9 1 9 36 69-115 121-316 169-780 232-1713 317-3583 565-6588 580-12677 10 1 10 40-43 92-149 141-442 178-1171 ≤ 2826 ≤ 6090 580-12677 798-23556

 จำนวนแรมซีย์ 3 สี: R(3, 3, 3) = 17 
เราสามารถพิสูจน์ได้ว่า R(3, 3, 3) = 17 โดยสร้างกราฟที่มีจุดยอด 17 จุด แล้วระบายสีเส้นเชื่อมด้วยสีแดง สีเหลือง และสีเขียว จากนั้นเลือกจุดยอด v ขึ้นมา จากหลักการรังนกพิราบ จะได้ว่ามีจุดยอดอย่างน้อย 6 จุดที่เชื่อมกับ v ด้วยสีเดียวกัน ซึ่งสามารถสมมติโดยไม่เสียนัยสำคัญได้ว่าเป็นสีแดง ถ้ามีเส้นเชื่อมระหว่างจุดยอดเหล่านั้นที่เป็นสีแดง ก็จะเกิดสามเหลี่ยมสีแดงขึ้น แต่ถ้าไม่มีเส้นเชื่อมสีแดงก็จะมีเส้นเชื่อมเพียง 2 สีเท่านั้น ซึ่งจะต้องเกิดสามเหลี่ยมสีเหลืองหรือสีเขียวขึ้นดังที่ได้พิสูจน์ไว้แล้วว่า R(3, 3) = 6

นอกจากนี้เราสามารถพิสูจน์แย้งกรณีที่มีจุดยอด 16 จุดได้ โดยระบายสีเส้นเชื่อมดังภาพ

 จำนวนแรมซีย์ 3 สีอื่นๆ 
ค่าของจำนวนแรมซีย์ 3 สี เท่าที่ทราบในปัจจุบัน
 R(3, 3, 3) 17 R(3, 3, 4) 30-31 R(3, 3, 5) 45-57 R(3, 3, 6) ≥60 R(3, 3, 7) ≥81 R(3, 3, 8) ≥101 R(3, 3, 9) ≥117 R(3, 4, 4) 55-79 R(3, 4, 5) 80-160 R(3, 4, 6) ≥107 R(3, 4, 7) ≥143 R(3, 5, 5) ≥129 R(4, 4, 4) ≥128 R(5, 5, 5) ≥417 R(6, 6, 6) ≥1070 R(7, 7, 7) ≥3214 R(8, 8, 8) ≥5384 R(9, 9, 9) ≥13761

 จำนวนแรมซีย์ที่มากกว่า 3 สีอื่นๆ 
ค่าของจำนวนแรมซีย์ที่มากกว่า 3 สี เท่าที่ทราบในปัจจุบัน
 R(3, 3, 3, 3) 51-62 R(3, 3, 3, 4) 93-153 R(3, 3, 4, 4) 171-462 R(4, 4, 4, 4) ≥634 R(5, 5, 5, 5) ≥3049 R(6, 6, 6, 6) ≥15202 R(7, 7, 7, 7) ≥62017 R(3, 3, 3, 3, 3) 162-307 R(4, 4, 4, 4, 4) ≥3416 R(5, 5, 5, 5, 5) ≥26912 R(3, 3, 3, 3, 3, 3) 538-1838 R(3, 3, 3, 3, 3, 3, 3) 1682-12861

 อ้างอิง 

 F. P. Ramsey: "On a problem of formal logic", Proc. London Math. Soc. series 2, vol. 30 (1930), pp. 264-286
 R. Graham, B. Rothschild, J.H. Spencer, Ramsey Theory, John Wiley and Sons, NY (1980).
 G. Exoo, "A Lower Bound for R(5,5)", J. Graph Theory, 13 (1989), 97-98.
 https://ritdml.rit.edu/handle/1850/14341

หมวดหมู่:คณิตศาสตร์เชิงการจัด