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

จากวิกิพีเดีย สารานุกรมเสรี
Jump to navigation Jump to search

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

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

R(3, 3) = 6[แก้]

กราฟที่มีจุดยอด 5 จุด ซึ่งไม่มีจุดยอด 3 จุดใดๆ ที่เส้นเชื่อมทุกคู่มีสีเดียวกัน

เราสามารถพิสูจน์ได้ว่า 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[แก้]

กราฟที่มีจุดยอด 16 จุด ซึ่งไม่มีจุดยอด 3 จุดใดๆ ที่เส้นเชื่อมทุกคู่มีสีเดียวกัน

เราสามารถพิสูจน์ได้ว่า 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