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

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

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

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

สารบัญ 1 R(3, 3) = 6 2 ทฤษฎีบท 3 จำนวนแรมซีย์อื่นๆ 4 จำนวนแรมซีย์ 3 สี: R(3, 3, 3) = 17 5 จำนวนแรมซีย์ 3 สีอื่นๆ 6 จำนวนแรมซีย์ที่มากกว่า 3 สีอื่นๆ 7 อ้างอิง

[แก้] 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)
• 2^r/2 ≤ R(r, r) ≤ 4^r

ซึ่งสามารถใช้ทฤษฎีบทนี้ในการจำกัดช่วงของจำนวนแรมซีย์ที่มีค่ามากๆได้

[แก้] จำนวนแรมซีย์อื่นๆ

จำนวนแรมซีย์สำหรับค่า 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

[แก้] อ้างอิง

• 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.