用戶:Yirdream/極值圖論

極值圖論（英文：Extremal graph theory）是組合學的一個分支，它本身是一個數學領域，同時屬於極值組合學和圖論。本質上，極值圖論研究圖的不變量如何影響其他的變量。^[1]　極值圖論的結果通常是在處理多個圖的不變量之間的關聯，典型的極值圖論問題中，時常固定某些特定的參數（像是：點的個數、邊的個數），然後在這樣的限制下詢問：另一個參數最大或最小可能是多少？^[2]　如果一個圖是某個最佳化問題（像是前面那樣的問題）的一個解答，那麼我們就稱這個圖是這個問題的極值圖，極值圖是極值圖論研究中很重要的一部分。

極值圖論和許多其他領域有緊密的關聯，像是拉姆齊理論、譜圖論、計算複雜性理論，和加性組合，且常常使用概率方法作為研究的工具。

歷史

極值圖論，嚴格來說，是由匈牙利人發展並愛好的圖論分支

Bollobás (2004) 張鎮華(2017)

曼特爾定理（1907）和圖蘭定理（1941）是極值圖論研究中最早的里程碑之一。^[3]特別是，圖蘭定理後來成為研究艾狄胥-斯通定理（1946）等結果的動力。 ^[1] 這個結果令人驚豔的是一個圖 $H$ 的着色數和擁有最多邊且不包含 $H$ 子圖的圖（ $H$ －free graph）有關。另一個艾狄胥-斯通定理的證明使用了塞邁雷迪正則性引理，一個在極值圖論裏解決問題的基本技巧。

一些常見的主題和概念

圖着色

圖形 $G$ 的一個正常（點）着色是將所有 $G$ 的頂點都著上一個顏色，使得不存在兩個相鄰的頂點有一樣的着色，或者一個更數學的定義是：一個圖 $G$ 的 $k$ -着色 ( $k$ -coloring) 是一個函數 $f:V(G)\rightarrow \{1,2,3,\cdots k\}$ 而一個正常 $k$ 着色 (proper $k$ -coloring) 則代表 $f(x)\neq f(y)\quad \forall xy\in E(G)$ 。而圖 $G$ 的着色數 $\chi (G)$ 代表可以將 $G$ 正常着色的最小值，也就是說，如果 $G$ 存在一個正常 $k$ 着色，則 $\chi (G)\geq k$ 。計算特定的圖的着色數是在極值圖論中一個基本的問題，因為許多問題與領域都需要考慮圖的着色數（像前面提到的艾狄胥-斯通定理）。^[4]

對於着色數我們可以透過點團數 $\omega (G)$ （點團數表示 $G$ 中最大點團的點數）給出一個簡單的下界，因為在點團內的所有點一定着不同的顏色，所以 $\chi (G)\geq \omega (G)$ ；再者，我們考慮圖中最大獨立集的點數， $\alpha (G)$ 因為每個顏色都構成一個獨立集，所以我們可以得到另一個簡單的下界 $\chi (G)\geq {\frac {|V(G)|}{\alpha (G)}}$ ^[5]

貪婪着色法給出了上界 $\chi (G)\leq \Delta (G)+1$ ，在這裏 $\Delta (G)$ 是 $G$ 裏最大的度(degree)。當 $G$ 不是奇圈或完全圖，布魯克斯定理指出這個上界可以再簡化為 $\Delta (G)$ 。當 $G$ 是平面圖，四色定理指出 $G$ 的着色數最多是4。

在一般的情況下，一個圖是否具有最多 $k(\leq |V(G)|)$ 色的正常着色被認為是NP 困難的。

除了考慮點着色之外，也有研究其他方式的着色，例如邊着色就是一個較常出現的問題。一個圖的邊着色數 $\chi '(G)$ 代表 $G$ 能被正常邊着色所需的最小顏色數，維辛定理給出圖 $G$ 邊着色數是 $\Delta (G)$ 或者 $\Delta (G)+1$ 。

禁用子圖問題

禁用子圖問題是極值圖論裏非常重要的問題：固定一個圖 $H$ ，和一個正整數 $n$ ，那一個具有 $n$ 個點且不存在 $H$ 子圖的圖 $G$ 最多能有幾條邊？通常把這個數字記為 $\mathrm {ex} (n,H)$

當 $H=K_{r}$ 是一個完全圖，圖蘭定理給出了精確的 $\operatorname {ex} (n,K_{r})$ 且刻劃最大值發生時的所有圖；此類圖被稱為Turán 圖。對於非二分圖 $H$ ，艾狄胥-斯通定理給出一個用 $H$ 的着色數表示 $\operatorname {ex} (n,H)$ 的漸進最佳上界。如何表達 $\operatorname {ex} (n,H)$ 的漸進最佳上界當 $H$ 是二分圖仍是一個未解的問題（透過艾狄胥-斯通定裏只能知道 $\mathrm {ex} (n,H)=o(n^{2})$ 但我們期待有更好的估計）；當 $H$ 是一個完全二分圖時，這個問題被稱作Zarankiewicz 問題，一個比較顯著的結果是Kővári–Sós–Turán 定理（1954）告訴我們對於兩個正整數 $s\leq t$ 都存在常數 $C=C(s,t)$ 使得 $\forall n\quad \mathrm {ex} (n,K_{s,t})\leq Cn^{2-1/s}$ ^[6]

同態密度

$H$ 在 $G$ 中的同態密度 $t(H,G)$ 表示一個隨機映射 $f:V(H)\rightarrow V(G)$ 構成一個圖同態的概率。它和子圖密度有密切的相關，子圖密度表達 $H$ 是 $G$ 的子圖的可能性。

禁用子圖問題可以被改寫為在 $G$ -密度為0的情況下最大化圖的邊密度，這自然會導致圖同態不等式形式的一般化，這是一個和 $t(H,G)$ 對於各種圖 $H$ 有關的不等式。延伸同態密度至圖極限，是作為稠密圖的極限而出現的現象。圖同態密度可以寫成積分的形式，可以使用柯西-施瓦茨不等式和赫爾德不等式來推導出同態不等式

與同態密度相關的一個主要的開放問題是 Sidorenko 猜想，它以 $G$ 的邊密度給出一個嚴格的下界對於二分圖在圖 $G$ 中的同態密度

圖的正則性

Szemerédi 正則性引理 表示所有圖在以下意義下都是「正則的」：任意圖的點集可以被分割成有限個部分使得在大多數的部分之間都表現得像隨機圖。^[7]這個分割給出了和原圖相近的結構，提供了一些原始圖的訊息

正則性引理是極值圖論重要的一個結果，也在加性組合學和計算複雜性理論有大量的應用。除了正則性之外，許多和圖正則性緊密相關的理論，像是強正則性和Freieze-Kannan弱正則性以及正則性對超圖上的擴展都正在被研究。

圖的正則性的應用通常利用一些計數原理和移除引理的方法，在最簡單的形式下，圖計數引理使用正則分割裏的兩個部分間的正則性來逼近某個特定子圖的數量，而圖刪除引理則是考慮一個具有少量特定子圖的圖，可以透過刪除少量的子圖（有時是少量的邊，像是三角形刪除引理）達到刪除所有子圖的目的。

參見

相關領域

拉姆齊理論
拉姆齊-圖蘭理論
譜圖論
加性組合學
計算複雜性理論
概率方法

一些技巧和方法

概率方法
相依隨機選擇
容器法
超圖正則性法

定理和猜想（除了上面提到的之外）

奧雷定理
魯茲薩-塞邁雷迪問題

參考文獻

^ ^1.0 ^1.1 Diestel, Reinhard, Graph Theory 4th, Berlin, New York: Springer-Verlag: 169–198, 2010 [2013-11-18], ISBN 978-3-642-14278-9, （原始內容存檔於2017-05-28）引用錯誤：帶有name屬性「:0」的<ref>標籤用不同內容定義了多次
^ Template:Princeton Companion to Mathematics
^ Bollobás, Béla, Modern Graph Theory, Berlin, New York: Springer-Verlag: 103–144, 1998, ISBN 978-0-387-98491-9
^ 張, 鎮華. 演算法觀點的圖論. 台北: 臺大出版中心. 2017: 198–198. ISBN 978-986-350-406-1.
^ 張, 鎮華. 演算法觀點的圖論. 台北: 臺大出版中心. 2017: 202–202. ISBN 978-986-350-406-1.
^ Zhao, Yufei. Graph Theory and Additive Combinatorics. Cambridge University Press. 2023: 22–22. ISBN 978-100-931-095-6.
^ Alon, Noga; Krivelevich, Michael. Extremal and Probabilistic Combinatorics. New Jersey: Princeton University Press. 2008. ISBN 978-0-691-11880-2.

[:0-1] 1.0 ^1.1 Diestel, Reinhard, Graph Theory 4th, Berlin, New York: Springer-Verlag: 169–198, 2010 [2013-11-18], ISBN 978-3-642-14278-9, （原始內容存檔於2017-05-28）引用錯誤：帶有name屬性「:0」的<ref>標籤用不同內容定義了多次

[pcm2-2] Template:Princeton Companion to Mathematics

[b104-3] Bollobás, Béla, Modern Graph Theory, Berlin, New York: Springer-Verlag: 103–144, 1998, ISBN 978-0-387-98491-9

[4] 張, 鎮華. 演算法觀點的圖論. 台北: 臺大出版中心. 2017: 198–198. ISBN 978-986-350-406-1.

[5] 張, 鎮華. 演算法觀點的圖論. 台北: 臺大出版中心. 2017: 202–202. ISBN 978-986-350-406-1.

[6] Zhao, Yufei. Graph Theory and Additive Combinatorics. Cambridge University Press. 2023: 22–22. ISBN 978-100-931-095-6.

[7] Alon, Noga; Krivelevich, Michael. Extremal and Probabilistic Combinatorics. New Jersey: Princeton University Press. 2008. ISBN 978-0-691-11880-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]