extremal · Turán · 正则性引理

极值图论：边一多就躲不开的子结构

极值图论 (extremal graph theory) 问的是同一个母题：一张 n 点图最多能放多少条边，才仍然不含某个固定的子结构？边数一旦越过这条阈值，那个子结构就必然出现——再怎么精心避让也躲不掉。本页以最经典的 Turán 定理为主线：不含完全图 K_{r+1} 的图，边数上界恰好由 Turán 图 T(n,r) 取到。拖动滑块换 n 与 r，看这张「把点尽量均分成 r 个部、部间全连、部内无边」的极值图长什么样，以及它的精确边数。

母题： 给定一个「禁用图」H，记 ex(n; H) 为不含 H 作为子图的 n 点图的最大边数。极值图论研究这个函数，以及取到上界的极值图长什么样。H = K_{r+1}（含 r+1 个两两相邻的点）这一情形有完全的答案，就是 Turán 定理。

Turán 定理 (1941)：任何不含 K_{r+1} 的 n 点图，边数至多为 Turán 图 T(n,r) 的边数，且唯一的极值图就是 T(n,r)。这里 T(n,r) 是把 n 个点尽量均匀地分成 r 个部、部之间所有点对全连、部之内一条边都不连得到的完全 r 部图。它不含 K_{r+1}：任取 r+1 个点，鸽巢原理保证至少两个落在同一部，而同部不相邻。

精确边数：把 n 写成 r 个部，其中 b = n mod r 个部大小为 $\lceil n/r\rceil$ ，其余 $r - b$ 个部大小为 $\lfloor n/r\rfloor$ 。完全 r 部图的边 = 全部点对减去同部点对，于是 $|E(T(n,r))| = ( n^2 - Σ s_i^2 ) / 2$ ，其中 $s_i$ 是各部大小。这是精确值，本页 scorecard 用的就是它；常被引用的 $(1 - 1/r)\cdot n^2/2$ 只是 n 被 r 整除时的形式、一般情况下是上界近似，不要当作答案。

Mantel 定理是 r = 2 的特例：不含三角形 K₃ = K_{2+1} 的 n 点图，边数至多 $\lfloor n^2/4\rfloor$ ，极值图是把点平分成两部的完全二部图 T(n,2)。下面的「Mantel 紧」按钮演示：在 T(n,2) 的某一个部内补上一条边，这条边的两个端点连同另一部里任意一点，立刻构成一个三角形——说明 $\lfloor n^2/4\rfloor$ 这条上界一步都不能再松。

Hadwiger 猜想 (1943):把着色与子式 (minor) 拴在一起的极值型断言——若图 G 的色数 $χ(G) \ge t$ ，则 G 必含 K_t 作为子式。它把四色定理放进一个更宏大的框架（t = 5 的情形等价于四色定理）； $t \le 6$ 已被证明，一般情形至今未决，是结构图论里最负盛名的公开问题之一。子式的定义见子图谱系。

Szemerédi 正则性引理 (regularity lemma):极值图论在稠密图上的「万能划分工具」。它断言任何足够大的图，其顶点集都能划分成有限个大小近似相等的块，使得几乎所有块对之间的边分布都近似随机（任取两块各自的大子集，子集间的边密度都接近该块对的整体密度，这种块对称 $\varepsilon -regular$ ）。划分块数只依赖精度 $\varepsilon$ 、与图本身大小无关。配合「计数引理」，它把一张杂乱的稠密图近似成有限个随机二部块的拼接，从而把 Turán 型、Ramsey 型的极值问题化归为对这有限结构的分析。