图的极值图论 极值图论是图论的一个重要分支，主要研究在满足某些特定条件限制下，图的结构参数（如边数、顶点数等）的最大或最小值问题。其核心思想是：给定一个图的性质P，以及一个或多个被禁止的子图（称为“禁用子图”），我们要确定具有n个顶点的、不包含任何禁用子图的图所能拥有的最大边数。反过来，也可以研究在边数给定的情况下，为了确保图必然具有性质P，所需要的最少顶点数。 第一步：基本问题与Turán定理 极值图论最经典的问题是：如果一个简单的n个顶点的图不允许包含一个完全子图K_ r（即一个r个顶点的团），那么这个图最多能有多少条边？ 这个问题的答案由Turán定理给出。该定理指出，不含K_ {r+1}的n顶点图的最大边数，由Turán图 T(n, r) 达到。Turán图 T(n, r) 是将n个顶点尽可能平均地划分成r个部分，并且连接任意两个不同部分的所有顶点对，但同一部分内的顶点之间没有边。这样的图是一个完全r部图。 例如，禁止K_ 3（即三角形）时，最大的图是完全二部图。如果n是偶数，将顶点平均分为两部分，边数就是 (n/2) * (n/2) = n²/4。Turán定理精确地给出了最大边数的公式。 第二步：禁用子图与极值函数 将上述问题一般化，我们固定一个图H作为“禁用子图”。我们定义极值函数 ex(n, H) 为：所有n个顶点且不包含H作为子图的图所能拥有的最大边数。 Turán定理解决的就是当H是完全图K_ r时的情形。 另一个著名结果是Mantel定理，它是Turán定理在r=2时的特例，即禁止三角形（K_ 3）时，最大边数为 floor(n²/4)。 如果H不是完全图，问题会变得复杂。例如，禁止的图H是一个圈（比如C_ 4，一个4个顶点的正方形）。那么，ex(n, C_ 4) 是多少？也就是说，一个n个顶点的图，如果任意两个顶点之间最多只有一条长度为2的路径（即不含C_ 4），最多能有多少条边？这个问题比Turán定理要困难，其精确值至今未完全解决，但已知其数量级大约是n^(3/2)。 第三步：Erdős–Stone定理——渐近里程碑 对于大多数非二部图H，极值图论的渐近行为由一个强大的定理描述，即Erdős–Stone定理。该定理指出，对于任意一个图H，其极值函数ex(n, H)满足： lim_ {n→∞} ex(n, H) / (n choose 2) = 1 - 1/(χ(H) - 1) 其中χ(H)是图H的色数。 这个定理的意义在于，它将极值问题与染色问题深刻地联系了起来。它告诉我们，一个不含H的图，其边数的渐近上界主要由H的色数决定。如果H是二部图（χ(H)=2），那么定理给出的极限是0，这意味着ex(n, H)的增长速度远低于n²，即o(n²)。这种情况下，我们需要更精细的工具来研究。 第四步：二部图禁用的稀疏极值图论 当禁用子图H是二部图时，情况变得非常丰富且困难，这构成了“稀疏极值图论”的研究内容。因为H是二部图，它本身可以被二染色，所以包含H的图可以非常稠密。因此，要避免H，图必须相对稀疏。 退化与非退化问题 ：如果H包含一个圈，则ex(n, H)的数量级是n^c，其中c>1（例如C_ 4是n^(3/2)）。如果H是森林（无圈的二部图，如一条路径或一颗树），则ex(n, H)是线性的，即O(n)。我们称前者为“非退化”极值问题，后者为“退化”极值问题。 Kővári–Sós–Turán定理 ：这是处理特定二部图的一个关键结果。它给出了禁止完全二部图K_ {s,t}的极值函数上界：ex(n, K_ {s,t}) = O(n^{2 - 1/s})。当s=2, t=2时（即禁止C_ 4），就是O(n^(3/2))。 第五步：图兰型问题与超图推广 极值图论的思想可以推广到更复杂的结构上。 图兰型问题 ：不仅仅是禁止一个子图，我们可以禁止一个子图族F。研究在n顶点图中，不包含F中任何子图的最大边数。这包含了上述所有情况作为特例。 超图极值问题 ：图是二元关系，超图则可以表示多元关系。超图极值问题研究在禁止某些子超图的条件下，超图的最大边数（此时“边”是顶点集的一个子集）。这个问题比图的情形要复杂得多，许多在图中简单的问题在超图中都是公开难题。 概率方法的应用 ：极值图论与随机图理论紧密相连。Erdős等人利用概率方法证明了存在边数很多但围长（最短圈的长度）也很大的图，这为许多极值问题提供了下界。 总之，极值图论从“最多能有多少条边”这样一个朴素的问题出发，发展出了一套深刻而丰富的理论，连接了图的结构、染色、随机性以及组合数学的多个核心领域。