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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

สารบัญ

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

กราฟที่มีจุดยอด 5 จุด ซึ่งไม่มีจุดยอด 3 จุดใดๆ ที่เส้นเชื่อมทุกคู่มีสีเดียวกัน
ขยาย
กราฟที่มีจุดยอด 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 จุดใดๆ ที่เส้นเชื่อมทุกคู่มีสีเดียวกัน
ขยาย
กราฟที่มีจุดยอด 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, 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
ภาษาอื่น