極值圖論研究圖的整體參數（如邊密度或著色數）對局部結構的影響。例如對於給定的整數r，有多少條邊可以保證n個頂點的圖無論邊怎么放置都必須包含一個K(r)完全子圖，多少條邊可以保證某種子結構出現。
基本介紹
- 中文名：極值圖論
- 外文名：Extremal graph theory
內容,歷史背景,相關定理,曼特爾定理,Turán's 定理,Erdős–Stone 定理,
內容
極值圖論是數學的一個分支，研究圖的全局特性如何影響局部子結構。它包含了大量的結果，這些結果描述了某些圖屬性- 例如頂點數（大小）、邊數、邊密度、項組笑腿色數和周長- 保證某些局部子結構的存在。
圖論這一領域的主要研究對象之一是極值圖，它們相對於探少某些全局參數是最大或最小的，並且它們包含（或不包含）局部子結構——例如團重連項，或邊緣著色等。
歷史背景
曼特爾定理 Mantel's Theorem （1907 年）和圖蘭定理 Turán's Theorem （1941 年）是極值圖論研究的第一個里程碑。特別是，Turán 的定理後來成駝淋嘗拳為發現Erdős-Stone-Simonovits 定理(1946)等結果的前提。
相關定理
曼特爾定理
在不存在三邊迴路的n頂點圖中，邊數最大為
換句話說，必須刪除K_n中幾乎一半的邊才能獲得無三角圖。證明如下：
設A為n個點中，向外連線最多的點，設它向外連k條線，則與A相連的點之間不允許連線
而剩餘(n-1-k)中的任意一點不可能向外連線數大於k，設這些點連線總數為y，則有
當
時，槓挨剃y是整數，所以y的最大值為
所以
Turán's 定理
令G為具有n個頂點的任套戰道何圖，使得G為K_(r+1)-free。謎糠格 那么G中的邊數最多為
曼特爾定理可看作Turán's定理的特殊情況
等效表達如下：
在沒有(r+1)點團的n個頂點的簡單圖中，T(n,r)的邊數最大。
Erdős–Stone 定理
它可視為對Turán 定理加強來限制非完全圖H的無H圖中的邊數。Paul Erdős和Arthur Stone 在 1946 年證明了該定理，並稱為極值圖論的基本定理。
固定一個圖H, ex(n, H)表示滿足G⊉H的圖的最大的邊數，則有
極值圖論
