จำนวนแรมซีย์
จำนวนแรมซีย์ 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