ทฤษฎีกราฟเชิงสุดขีด

ทฤษฎีกราฟเชิงสุดขีดศึกษาว่ากราฟจะมีขนาดหรือความหนาแน่นได้มากเพียงใด โดยยังคงหลีกเลี่ยงโครงสร้างย่อยที่กำหนดไว้ และระบุการจัดเรียงเชิงสุดขีด

Definition

การศึกษาค่าสูงสุดหรือต่ำสุดของพารามิเตอร์กราฟ เช่น จำนวนขอบ ภายใต้ข้อจำกัดเชิงโครงสร้าง เช่น การไม่มีกราฟย่อยที่กำหนด

Scope

หัวข้อนี้มุ่งเน้นไปที่ปัญหาประเภททูรัน (Turan-type problems) ซึ่งคือจำนวนขอบสูงสุดในกราฟที่ไม่มีกราฟย่อยที่กำหนดให้ โดยเริ่มต้นจากทฤษฎีบทของมันเทล (Mantel) และทูรัน (Turan) และขยายไปสู่ทฤษฎีบทของเออร์โดส-สโตน (Erdos-Stone) ซึ่งกำหนดความหนาแน่นเชิงสุดขีดเชิงอะซิมโทติก (asymptotic extremal density) สำหรับกราฟย่อยต้องห้ามใดๆ นอกจากนี้ยังแนะนำการทำงานร่วมกันของความหนาแน่น โครงสร้าง และระเบียบวิธีของเซเมเรดี (Szemeredi regularity method)

Core questions

• จำนวนขอบสูงสุดในกราฟที่มี n จุดยอดที่ไม่มีกราฟย่อยที่กำหนดให้คือเท่าใด?
• กราฟใดที่บรรลุขอบเขตเชิงสุดขีดเหล่านี้?
• จำนวนสีของกราฟย่อยต้องห้ามควบคุมคำตอบเชิงอะซิมโทติกได้อย่างไร?
• ระเบียบวิธีความสม่ำเสมอลดกราฟหนาแน่นให้เหลือโครงสร้างที่มีขอบเขตได้อย่างไร?

Key concepts

• กราฟย่อยต้องห้าม
• กราฟทูรัน
• ทฤษฎีบทของมันเทล
• จำนวนเชิงสุดขีด (จำนวนทูรัน)
• ทฤษฎีบทของเออร์โดส-สโตน
• บทตั้งความสม่ำเสมอของเซเมเรดี

Key theories

ทฤษฎีบทของทูรัน

ในบรรดากราฟทั้งหมดที่มี n จุดยอดที่ไม่มีกราฟบริบูรณ์ที่มี r+1 จุดยอด กราฟ r-พาร์ไทต์บริบูรณ์แบบสมดุลจะมีจำนวนขอบมากที่สุด ซึ่งเป็นการสรุปทั่วไปของขอบเขตปราศจากสามเหลี่ยมของมันเทล และเป็นรากฐานของทฤษฎีกราฟเชิงสุดขีด

ทฤษฎีบทของเออร์โดส-สโตน

สำหรับกราฟย่อยต้องห้าม H ใดๆ ที่กำหนดไว้ ความหนาแน่นขอบสูงสุดของกราฟที่ปราศจาก H จะถูกกำหนดโดยจำนวนสีของ H ในเชิงอะซิมโทติก ซึ่งเป็นการรวมผลลัพธ์เชิงสุดขีดประเภททูรันเข้าด้วยกัน

Clinical relevance

ผลลัพธ์ความหนาแน่นเชิงสุดขีดจำกัดโครงสร้างของเครือข่ายขนาดใหญ่และระบบข้อจำกัด และระเบียบวิธีความสม่ำเสมอที่พัฒนาขึ้นในสาขานี้มีการประยุกต์ใช้ในการทดสอบคุณสมบัติ วิทยาการคอมพิวเตอร์เชิงทฤษฎี และคณิตศาสตร์เชิงการจัดหมู่แบบบวก (additive combinatorics)

History

ขอบเขตปราศจากสามเหลี่ยมของมันเทลในปี 1907 และการสรุปทั่วไปของทูรันในปี 1941 ได้ริเริ่มสาขาวิชานี้; ทฤษฎีของเออร์โดส-สโตน-ไซโมโนวิทส์ (Erdos-Stone-Simonovits) และบทตั้งความสม่ำเสมอของเซเมเรดี (Szemeredi's regularity lemma) ทำให้มันเป็นเสาหลักสำคัญของการจัดหมู่สมัยใหม่

Key figures

• Paul Turan
• Paul Erdos
• Endre Szemeredi

Seminal works

• bollobas1998
• diestel2017

Frequently asked questions

ปัญหาประเภททูรันคืออะไร?

เป็นการถามถึงจำนวนขอบที่มากที่สุดที่กราฟสามารถมีได้ในขณะที่หลีกเลี่ยงกราฟย่อยที่กำหนด ตัวอย่างที่เป็นแบบฉบับคือจำนวนขอบสูงสุดในกราฟที่ปราศจากสามเหลี่ยม

ทฤษฎีกราฟเชิงสุดขีดเกี่ยวข้องกับทฤษฎีแรมซีย์อย่างไร?

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