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

จำนวนแรมซีย์ 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
{| border="1" cellpadding="6" cellspacing="0"
! 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
| &le;&nbsp;2826
|-
! 8
| 1
| 8
| 28
| 56-84
| 101-216
| 127-495
| 216-1031
| 282-1870
| 317-3583
| &le;&nbsp;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
| &le;&nbsp;2826
| &le;&nbsp;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 สี เท่าที่ทราบในปัจจุบัน
{| border="1" cellpadding="6" cellspacing="0"
| 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 สี เท่าที่ทราบในปัจจุบัน
{| border="1" cellpadding="6" cellspacing="0"
| 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
คณิตศาสตร์เชิงการจัด