用户:Yirdream/极值图论

极值图论（英文：Extremal graph theory）是组合学的一个分支，它本身是一个数学领域，同时属于极值组合学和图论。本质上，极值图论研究图的不变量如何影响其他的变量。^[1]　极值图论的结果通常是在处理多个图的不变量之间的关联，典型的极值图论问题中，时常固定某些特定的参数（像是：点的个数、边的个数），然后在这样的限制下询问：另一个参数最大或最小可能是多少？^[2]　如果一个图是某个最佳化问题（像是前面那样的问题）的一个解答，那么我们就称这个图是这个问题的极值图，极值图是极值图论研究中很重要的一部分。

极值图论和许多其他领域有紧密的关联，像是拉姆齐理论、谱图论、计算复杂性理论，和加性组合，且常常使用机率方法作为研究的工具。

历史

极值图论，严格来说，是由匈牙利人发展并爱好的图论分支

Bollobás (2004) 张镇华(2017)

曼特尔定理（1907）和图兰定理（1941）是极值图论研究中最早的里程碑之一。^[3]特别是，图兰定理后来成为研究艾狄胥-斯通定理（1946）等结果的动力。 ^[1] 这个结果令人惊艳的是一个图 $H$ 的著色数和拥有最多边且不包含 $H$ 子图的图（ $H$ －free graph）有关。另一个艾狄胥-斯通定理的证明使用了塞迈雷迪正则性引理，一个在极值图论里解决问题的基本技巧。

一些常见的主题和概念

图著色

Petersen 图的著色数是 3。

图形 $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]