4. Erdős–Stone–Simonovits 定理: 禁止一般子图

(除了超图以外) 人们可能还想知道, 如果定理 2.3 中的 $K_{r + 1}$ 被替换为任意图 $H$ 会发生什么:

问题 4.1. 固定图 $H$ . 如果 $G$ 是一个 $n$ 顶点图, 并且 $H$ 不在其中作为子图出现, 那么 $G$ 最多有多少条边?

定义 4.2. 对于图 $H$ 和 $n \in N$ , 将 $ex (n, H)$ 定义为 $n$ 顶点 $H$ -free 图的最大边数.

例如, 定理 2.3 告诉我们对于任何给定的 $r$ , $ex (n, K_{r + 1}) = e (T_{n, r}) = (1 - \frac{1}{r} + o (1)) (2 n)$ 乍一看, 人们可能不会期望问题 4.1 有一个明确的答案. 实际上, 该解决方案似乎取决于 $H$ 的各种特征 (例如, 其直径 ¹或最大度数) . 令人惊讶的是, 一个单一的参数—— $H$ 的色数, 控制着 $ex (n, H)$ 的增长.

定义 4.3. 图 $G$ 的色数 $χ (G)$ , 是给 $G$ 的顶点着色所需的最小颜色数. 其中, 一个着色方案必须满足任意两个相邻的顶点具有不同的颜色.

轻而易见的,

χ (K_{r + 1}) = r + 1

和

χ (T_{n, r}) = r

.

可以观察到, 如果 $H \subseteq G$ , 则 $χ (H) \leq χ (G)$ . 实际上, 当 $H \subseteq G$ , $G$ 的任意正确着色都是 $H$ 的一个正确着色 (也就是说如果 $χ (H) > χ (G)$ , 则 $H \neq \subseteq G$ ) . 由此, 我们得出如果 $χ (H) = r + 1$ , 则 $T_{n, r}$ 是 $H$ -free 的. 所以, $ex (n, H) \geq e (T_{n, r}) = (1 - \frac{1}{r} + o (1)) (2 n)$ 这是我们能做的最好的结果吗? 答案是肯定的.

定理 4.4 (Erdős-Stone-Simonovits 1966). 对于任意图 $H$ , 我们有 $n \to \infty lim \frac{ex ( n , H )}{( 2 n )} = 1 - \frac{1}{χ ( H ) - 1}$

我们暂时跳过证明.

笔记 4.5. 在本书的后面, 我们将展示如何使用 Szemerédi 正则性引理从定理 2.3 推导出定理 4.4.

当

H = K_{3}

时, 定理 4.4 告诉我们

n \to \infty lim \frac{ex ( n , H )}{( 2 n )} = \frac{1}{2}

符合定理 2.3. 当

H = K_{4}

时, 我们得到

n \to \infty lim \frac{ex ( n , H )}{( 2 n )} = \frac{2}{3}

也符合定理 2.3 . 当

H

是 Peterson 图 (图 4) 时, 定理 4.4 告诉我们

$n \to \infty lim \frac{ex ( n , H )}{( 2 n )} = \frac{1}{2}$ 这与 $H = K_{3}$ 的答案相同! 这令人惊讶, 因为 Peterson 图似乎比三角形复杂得多.

(...) 一个 Peterson 图的 3-着色方案

名字空间

视图

4. Erdős–Stone–Simonovits 定理: 禁止一般子图