ทฤษฎีบทของแรมซีย์และจำนวนแรมซีย์

ทฤษฎีบทของแรมซีย์รับประกันว่ากราฟบริบูรณ์ที่มีสองสีขนาดใหญ่พอสมควรใดๆ จะมีคลิกเอกรงค์ และจำนวนแรมซีย์จะระบุว่าขนาดที่เพียงพอคือเท่าใด

Definition

จำนวนแรมซีย์ R(s,t) คือจำนวนเต็ม n ที่น้อยที่สุด ซึ่งการระบายสีขอบของกราฟบริบูรณ์บน n จุดยอดด้วยสีแดง-น้ำเงินใดๆ จะมีคลิกสีแดงบน s จุดยอด หรือคลิกสีน้ำเงินบน t จุดยอด

Scope

หัวข้อนี้ครอบคลุมรูปแบบกราฟของทฤษฎีบทของแรมซีย์, นิยามของจำนวนแรมซีย์ R(s,t), กรณีคลาสสิกขนาดเล็ก เช่น R(3,3)=6, ขอบเขตบนของ Erdos-Szekeres และขอบเขตล่างเชิงความน่าจะเป็นของ Erdos, และการขยายไปสู่จำนวนแรมซีย์แบบหลายสีและไฮเปอร์กราฟ นี่คือหัวใจเชิงปริมาณของทฤษฎีแรมซีย์

Core questions

• กราฟบริบูรณ์ต้องมีขนาดใหญ่เพียงใดจึงจะบังคับให้เกิดคลิกเอกรงค์ที่มีขนาดที่กำหนด?
• ค่าที่แน่นอนและขอบเขตสำหรับจำนวนแรมซีย์ที่ทราบมีอะไรบ้าง?
• การให้เหตุผลเชิงความน่าจะเป็นให้ขอบเขตล่างของจำนวนแรมซีย์ได้อย่างไร?
• ทฤษฎีบทนี้ขยายไปสู่หลายสีและไฮเปอร์กราฟได้อย่างไร?

Key concepts

• ทฤษฎีบทของแรมซีย์สำหรับกราฟ
• จำนวนแรมซีย์ R(s,t)
• คลิกเอกรงค์
• ขอบเขต Erdos-Szekeres
• ขอบเขตล่างเชิงความน่าจะเป็น
• จำนวนแรมซีย์แบบหลายสีและไฮเปอร์กราฟ

Key theories

ขอบเขตบนของ Erdos-Szekeres

จำนวนแรมซีย์มีค่าจำกัดและถูกจำกัดโดย R(s,t) ซึ่งมีค่าไม่เกินสัมประสิทธิ์ทวินามของ s+t-2 เลือก s-1 ซึ่งเป็นขอบเขตที่อิงกับการเกิดซ้ำที่พิสูจน์ทฤษฎีบทของแรมซีย์พร้อมกับการประมาณค่าที่ชัดเจน

ขอบเขตล่างเชิงความน่าจะเป็นของ Erdos

โดยการนับคลิกเอกรงค์ที่คาดหวังในการระบายสีแบบสุ่ม Erdos ได้แสดงให้เห็นในปี 1947 ว่าจำนวนแรมซีย์แนวทแยง R(s,s) เติบโตแบบทวีคูณเป็นอย่างน้อย ซึ่งเป็นการประยุกต์ใช้ระเบียบวิธีเชิงความน่าจะเป็นครั้งแรกๆ

Clinical relevance

ระเบียบวิธีเชิงความน่าจะเป็นที่นำมาใช้ผ่านขอบเขตล่างของจำนวนแรมซีย์ได้กลายเป็นเครื่องมือสำคัญในสาขาวิชาคณิตศาสตร์เชิงการจัดและวิทยาการคอมพิวเตอร์เชิงทฤษฎี และการรับประกันแบบแรมซีย์เป็นพื้นฐานของขอบเขตล่างในการสื่อสารและโครงสร้างข้อมูล

History

Erdos และ Szekeres ได้ค้นพบและระบุปริมาณทฤษฎีบทของแรมซีย์อีกครั้งในปี 1935 ขณะศึกษาพหุโกณนูน; ขอบเขตล่างของการระบายสีแบบสุ่มของ Erdos ในปี 1947 ได้ริเริ่มระเบียบวิธีเชิงความน่าจะเป็น

Key figures

• Frank Ramsey
• Paul Erdos
• George Szekeres

Seminal works

• graham1990

Frequently asked questions

ทำไม R(3,3) เท่ากับหก?

ในบรรดาคนหกคนใดๆ จะมีสามคนที่รู้จักกันและกัน หรือสามคนที่ไม่รู้จักกันและกัน ในขณะที่คนห้าคนสามารถจัดเรียงเพื่อหลีกเลี่ยงทั้งสองกรณีได้ ดังนั้นหกจึงเป็นเกณฑ์ที่แน่นอน

จำนวนแรมซีย์ที่แน่นอนเป็นที่ทราบหรือไม่?

มีเพียงไม่กี่จำนวนเท่านั้นที่ทราบค่าที่แน่นอน แม้แต่ R(5,5) ก็ยังไม่ทราบค่าที่แน่นอน โดยความรู้ปัจจุบันจำกัดอยู่เพียงช่วงค่าเท่านั้น เนื่องจากพื้นที่การค้นหาเติบโตเร็วเกินไปที่จะคำนวณหาได้