禁用子图问题

此页面尚不符合香蕉空间的百科写作风格, 并需要改进. 请编辑者参照已有的与之内容相近的条目, 以及香蕉空间:写作指引的要求, 对此页面进行修改.

禁用子图问题是极值图论中的一类重要问题. 大致地说, 它问当图中不出现某子图时其边数最多能取几.

1定义

定义 1.1 (极值函数). $\mathrm{ex}(n,G):=\max \{|E(H)|:|V(H)|=n,G⊈H\}$, 其中

•	$n$ 是自然数.
•	$G,H$ 是图.
•	$V(\cdot ),E(\cdot )$ 分别是顶点集和边集.
•	$|\cdot |$ 是集合的基数.

在这个定义里, 我们称 $G$ 是禁用子图.

2例子

命题 2.1. $\mathrm{ex}(n,K_2)=0$.

证明. $K_2$ 仅有一边. 若 $K_2$ 是禁用子图, 则图无边.

$\square$

命题 2.2 (Mantel). $\mathrm{ex}(n,K_3)=\lceil \frac{n}{2}\rceil \lfloor \frac{n}{2}\rfloor$.

这是禁用 $K_3$ 时 Turán 定理的特殊情况 (详见讲义: 极值图论基础/禁用子图问题_(一)). 简单来讲, 该定理说若 $n$-顶点图禁止三角形作为其子图, 那它的边数至多是 $\lceil \frac{n}{2}\rceil \lfloor \frac{n}{2}\rfloor$. 下面给出一个归纳证明.

证明. 使用归纳法.

当 $n<3$, 显然任何图都不可能包含 $K_3$. 故容易验证情况 $\mathrm{ex}(1,K_3)=0,\mathrm{ex}(2,K_3)=1$, 这是符合的.

当 $n\ge 3$, 我们假设 $\forall k<n,\mathrm{ex}(k,K_3)=\lceil \frac{k}{2}\rceil \lfloor \frac{k}{2}\rfloor$ 都真. 现在令 $G$ 是禁用 $K_3$ 的 $n$-顶点图. 我们进行如下操作: 首先, 从 $G$ 任取一边 $\{u,v\}$ 并删去 $G$ 中顶点 $u,v$ 和所有包含 $u,v$ 的边得到图 $H\subseteq G$. 显然 $K_3⊈H,|V(H)|=n-2$. 根据归纳假设, 有 $\mathrm{ex}(n-2,K_3)=\lceil \frac{n-2}{2}\rceil \lfloor \frac{n-2}{2}\rfloor$. 然后, 把边 $\{u,v\}$ 连回 $H$, 尽量多连. 为保证禁用 $K_3$, $u$ 和 $v$ 不能连接同一顶点, 所以至多获得 $n-2$ 条边. 外加 $\{u,v\}$ 本身, 我们总共至多获得 $n-1$ 条边. 经此操作, 我们说明了 $G$ 的边数至多是 $\lceil \frac{n-2}{2}\rceil \lfloor \frac{n-2}{2}\rfloor +n-1=\lceil \frac{n}{2}\rceil \lfloor \frac{n}{2}\rfloor$ , 即 $\mathrm{ex}(n,K_3)=\lceil \frac{n}{2}\rceil \lfloor \frac{n}{2}\rfloor$.

证完了.

$\square$

3性质

基本性质

•	$H,G$ 是图, $H\subseteq G⟹\mathrm{ex}(n,H)\le \mathrm{ex}(n,G)$ (不严谨地说: 禁用小图限制更大, 故边数更少).

与染色的关系

$G$ 是图,

•	$\chi (G)=2$ ($G$ 是二部图) $⟹\mathrm{ex}(n,G)$ 较小, 不到 $O(n^2)$(Kővári–Sós–Turán 定理);
•	$\chi (G)\ge 3⟹\mathrm{ex}(n,G)$ 较大, 至少在 $O(n^2)$;
•	$\chi (G)$ 越大, $\mathrm{ex}(n,G)$ 越大. 例如, 若图 $\chi (G)\ge 3=\chi (K_3)$, 则 $\mathrm{ex}(n,G)\ge \lceil \frac{n}{2}\rceil \lfloor \frac{n}{2}\rfloor =\mathrm{ex}(n,K_3)$.

4相关讲义

讲义: 极值图论基础

术语翻译

禁用子图问题 • 英文 forbidden subgraph problem

极值函数 • 英文 extremal function

禁用子图 • 英文 forbidden subgraph