จำนวนแรมซีย์
จากวิกิพีเดีย สารานุกรมเสรี
ในคณิตศาสตร์เชิงการจัด จำนวนแรมซีย์ 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, 5) | ≥81 |
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 |
R(3, 3, 3, 4) | ≥93 |
R(3, 3, 4, 4) | ≥171 |
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 |
R(4, 4, 4, 4, 4) | ≥3416 |
R(5, 5, 5, 5, 5) | ≥26912 |
R(3, 3, 3, 3, 3, 3) | ≥538 |
R(3, 3, 3, 3, 3, 3, 3) | ≥1682 |