Teori Graf Ekstremal
Teori graf ekstremal menanyakan seberapa besar atau padat suatu graf dapat terbentuk sambil menghindari substruktur yang ditentukan, dan mengidentifikasi konfigurasi ekstremal.
Definition
Studi tentang nilai maksimum atau minimum dari parameter graf, seperti jumlah sisi, dengan batasan struktural seperti tidak adanya subgraf tetap.
Scope
Topik ini berpusat pada masalah tipe Turan – jumlah maksimum sisi dalam graf tanpa subgraf tertentu – dimulai dengan teorema Mantel dan Turan serta meluas ke teorema Erdos-Stone, yang menentukan kepadatan ekstremal asimtotik untuk setiap subgraf terlarang. Ini memperkenalkan interaksi kepadatan, struktur, dan metode keteraturan Szemeredi.
Core questions
- Berapa jumlah maksimum sisi dalam graf dengan n titik yang tidak mengandung salinan subgraf tertentu?
- Graf mana yang mencapai batas ekstremal ini?
- Bagaimana bilangan kromatik dari subgraf terlarang mengatur jawaban asimtotik?
- Bagaimana metode keteraturan mengurangi graf padat menjadi struktur terbatas?
Key concepts
- Subgraf terlarang
- Graf Turan
- Teorema Mantel
- Bilangan ekstremal (bilangan Turan)
- Teorema Erdos-Stone
- Lemma keteraturan Szemeredi
Key theories
- Teorema Turan
- Di antara semua graf dengan n titik tanpa subgraf lengkap pada r+1 titik, graf r-partit lengkap yang seimbang memiliki sisi terbanyak, menggeneralisasi batas bebas segitiga Mantel dan menjadi dasar teori graf ekstremal.
- Teorema Erdos-Stone
- Untuk setiap subgraf terlarang H yang tetap, kepadatan sisi maksimum dari graf bebas-H secara asimtotik ditentukan oleh bilangan kromatik H, menyatukan hasil ekstremal tipe Turan.
Clinical relevance
Hasil kepadatan ekstremal membatasi struktur jaringan besar dan sistem kendala, dan metode keteraturan yang dikembangkan dalam bidang ini memiliki aplikasi dalam pengujian properti, ilmu komputer teoretis, dan kombinatorika aditif.
History
Batasan bebas segitiga Mantel tahun 1907 dan generalisasi Turan tahun 1941 meluncurkan bidang ini; teori Erdos-Stone-Simonovits dan lemma keteraturan Szemeredi menjadikannya pilar sentral kombinatorika modern.
Key figures
- Paul Turan
- Paul Erdos
- Endre Szemeredi
Related topics
Seminal works
- bollobas1998
- diestel2017
Frequently asked questions
- Apa itu masalah tipe Turan?
- Ini menanyakan jumlah sisi terbesar yang dapat dimiliki suatu graf sambil menghindari subgraf tetap; contoh kanonisnya adalah sisi maksimum dalam graf bebas segitiga.
- Bagaimana teori graf ekstremal berhubungan dengan teori Ramsey?
- Keduanya mempelajari struktur yang tak terhindarkan, tetapi teori ekstremal menetapkan subgraf terlarang dan memaksimalkan sisi, sedangkan teori Ramsey menjamin struktur monokromatik setelah graf cukup besar.