极值圖論

T(13, 4)。在所有 n 個點但不包含 (r + 1)-團的簡單圖中，圖蘭圖 T(n, r) 的邊數最多。]]
極值圖論是數學中組合數學的一個分支，它結合了極值組合學與圖論的研究方法與問題。本質上，極值圖論探討了圖的局部子結構如何影響全域性質，極值圖論的研究多半在描述圖中全域性質（如頂點數、邊數）和局部性質（如子圖存在性）間的定量關係。

極值圖論中的問題多半可以表述為最佳化問題：當一張圖滿足某些限制時，某個圖參數的最大值（或最小值）可以為多少？若一張圖為最佳化問題的最佳解，這張圖就被稱為極值圖，極值圖是極值圖論中重要的研究對象。

極值圖論與拉姆齊理論、圖譜論、計算複雜度理論和加性組合學關係密切，並且經常使用機率方法作為證明手段。

歷史
Mantel 定理（1907）和圖蘭定理（1941）是極值圖論研究的開端：Mantel 定理確定了不含三角形的圖能擁有的最大邊數，而圖蘭定理把 Mantel 定理推廣到不含給定大小團的圖。

作為極值圖論的重要里程碑之一，圖蘭定理促成了許多後續成果的發展，像是艾狄胥－斯通定理（1946）。對於任意子圖 H，艾狄胥－斯通定理給出了沒有 H 的圖的邊數上界，此上界跟 H 的著色數有密切關聯。

1975 年，塞邁雷迪提出塞邁雷迪正則性引理，這個引理是解決極值圖論問題的重要技巧，像是艾狄胥－斯通定理就可以用此引理證明。

研究主體與概念
圖著色
的著色數是 3。]]
一張圖 G 的點著色是一種把每個頂點染色，使得圖上相鄰兩點的顏色都不同的方案。一個點著色需要的最少顏色數量稱為 G 的著色數，記作 \chi(G)。極值圖論的許多問題都可以被改寫為點著色問題，因此找出特定圖的著色數是極值圖論中很重要的一環。

禁止子圖
在所有 n 個點的圖中，不包含 G 為子圖的圖最多能有多少條邊？此問題稱為禁止子圖問題。對於給定的 n, G，問題的答案記作 \text{ex}(n, G)。

當 G 為完全圖.K_r 時，圖蘭定理給出了 \text{ex}(n, K_r) 的數值以及達到這個值的極值圖，這些圖稱為圖蘭圖。對所有不是二分圖的圖 G，艾狄胥－斯通定理則給出 \text{ex} (n, G) 的漸進數值，該數值可用 G 的著色數表示：\text{ex} (n, G) = \left(\frac{\chi(G) - 2}{\chi(G) - 1} + o(1)\right) \binom{n}{2}。

當 G 是二分圖時，\text{ex} (n, G) 的漸進數值仍然是未解問題，就算在 G 是完全二分圖的情況下也是。在 G 是完全二分圖的情況下，這個問題稱為 Zarankiewicz 問題。

同態密度
對於兩張圖 G = (V(G), E(G)) 和 H = (V(H), E(H)) 來說，如果函數 f: V(H) \rightarrow V(G) 滿足 \{u, v\} \in E(H) \Rightarrow \{f(u), f(v)\} \in E(G)，則 f 稱為一個 H 到 G 的圖同態。隨機的 f: V(H) \rightarrow V(G) 是圖同態的機率稱為 H 在 G 中的同態密度 t(H, G) 。

同態密度與子圖密度有密切關聯：禁止子圖問題等價於在滿足 t(H, G) = 0 下最大化 t(K_2, G)，也就是 G 的邊密度。這啟發了圖同態不等式的研究，它們探討不同子圖 H 間同態密度的不等式關係。透過把同態密度延伸到圖極限，同態密度可以寫為積分的形式，因此柯西不等式和赫爾德不等式可以用來證明各種圖同態不等式。

Sidorenko 猜想是同態密度研究中的重要猜想之一，它猜測任意二分圖 H 在任意圖 G 的同態密度 t(H, G) 會大於等於 t(K_2, G)^。也就是說，若 Sidorenko 猜想為真，t(H, G) 會被與 G 的邊密度有關的下界控制。

圖正則性
塞邁雷迪正則性引理斷言所有圖的點集都可以被劃分成數量有界的若干部分，使得絕大多數由兩個部分間形成的二分圖，都具有類似隨機二分圖的性質。這樣的劃分對原圖給出了結構上的近似，從而揭示出一些關於原圖的資訊。

正則性引理是極值圖論中一個核心的結果，它在加性組合學和計算複雜度理論等相關領域也有非常多的應用。除了塞邁雷迪正則性外，其他關於圖正則性的概念也有被研究，像是強正則性、Frieze-Kannan 弱正則性、以及超圖中的正則性。

圖正則性的應用很多時候利用了不同的圖計數引理跟圖移除引理。簡單來說，圖計數引理透過劃分中兩兩部分間的正則性來近似一個子圖在圖出現的次數；圖移除引理則說明如果一個子圖只有在圖中少量地出現，那可以透過移除少數的邊使得子圖不在圖中出現。

评论 (0)