2. 禁用子图问题 (一)

这一讲我们来看一些研究不包含某种特定结构的图的相关的结果. 首先我们来回顾 Turán 定理与其证明.

定理 2.1. (Turán 定理) 若图 $G(V,E)$ 不包含 $K_{r+1}$ 作为子图, 且 $|V|=n$. 则 $G$ 为一个每个部分的边数为 $[\frac{n}{r}]$ 或 $[\frac{n}{r}]+1$ 的完全 $r$ 部图时, $|E|$ 取最大值.

证明. 若 $v$ 和 $w$ 不相连, 不妨设 $d(v)\ge d(w)$. 我们考虑以下操作: 将 $w$ 所连出的边全部删去, 并将 $w$ 与所有 $v$ 的邻居全部连接. 那么, 容易验证, 以此法新得到的图 $G^{\prime }$ 的边数大于等于 $G$, 且 $G^{\prime }$ 依然无 $K_{r+1}$.

显然, 我们可以通过若干次上述操作使得不相邻的点度数相同且邻域相同. 此时 $G$ 为完全 $r$ 部图, 容易由凸性知 $G$ 的各部分顶点数之差小于等于 1 时 $G$ 的边数取最大值. 证毕.

$\square$

Turán 定理有很多个证明, 这种使用调整法的证明是其中比较简洁的一种. 事实上, Turán 定理给出了图 $G$ 不含完全图 $K_r$ 作为子图时, $G$ 的边数的最大值的刻画. 自然地, 我们想把完全图推广到一般的图上. 对于图 $H$, 我们记 $\mathrm{ex}(n,H)$ 为一切具有 $n$ 个顶点且不包含 $H$ 作为子图的图 $G$ 的边数的最大值. 关于 $\mathrm{ex}(n,H)$ 的研究一直是组合数学界一个非常关键的问题, 在此上面有许许多多的结果和很多尚待解决的猜想. 我们本讲就来研究和 $\mathrm{ex}(n,H)$ 相关的问题.

首先我们来看看 $H$ 为树的情况. 下文中均用字母 $T$ 来表示树. 不妨设 $T$ 为一个具有 $t+1$ 个顶点的树. 当 $t\mid n$ 时, 我们考虑一个由 $\frac{n}{t}$ 个 $K_t$ 构成的图, 此时我们有 $\mathrm{ex}(n,T)=\frac{n(t-1)}{2}$. 事实上, Erdös 猜测这个界是最紧的, 不过目前我们仍然没有完全解决这个猜想. 不过, 我们可以证明下述的特殊情形:

定理 2.2. 设 $P_{t+1}$ 为具有 $t+1$ 个顶点的链, 则 $\mathrm{ex}(n,P_{t+1})\le \frac{n(t-1)}{2}$.

证明. 我们对 $n$ 归纳. $n\le t$ 时命题平凡, 下设 $n\ge t+1$. 首先, 我们不妨设 $G$ 是连通的, 否则对 $G$ 的连通分支运用归纳假设即可. 若 $G$ 有一个顶点的度数小于等于 $\frac{t-1}{2}$, 我们去掉该顶点运用归纳假设即可证明问题. 下设 $G$ 的每个顶点的度数均大于等于 $\frac{t}{2}$. 我们取出 $G$ 中的最长链 $l=x_1{x}_2\cdots x_k$. 则 $l$ 的两个端点的所有邻居都在 $l$ 上. 若 $k\le t$, 由抽屉原理, 易见要么 $x_1,x_k$ 相连, 要么存在 $i,j$ 使得 $x_1$ 和 $x_i$ 相连, $x_j$ 和 $x_k$ 相连, 且 $|i-j|=1$. 因此, 无论如何都存在长度为 $k$ 的圈, 而其中必有一点和圈外的点相连 (连通性), 故产生更长的链, 矛盾! 因此 $k\ge t+1$. 结论得证.

$\square$

对于一般的情况, 我们有以下的结果:

定理 2.3. 设 $T$ 是一个具有 $t+1$ 个顶点的树, 则 $\mathrm{ex}(n,T)<(t-1)n$.

证明. 我们分两步证明该结论. 第一步, 我们证明, 若图 $G$ 的每个顶点的度数均大于等于 $t$, 则对于任意一个有 $t+1$ 个顶点的树 $T$, $G$ 均含 $T$. 我们对 $t$ 归纳. $t=1$ 时命题平凡; 若 $t-1$ 时命题成立, 对于 $t$ 的情形, 我们先考虑 $T$ 删掉一片叶子得到的树 $T^{\prime }$, 由归纳假设 $G$ 含 $T^{\prime }$, 再补上这片叶子 (由于每个顶点的度数均大于等于 $t$ 这显然可以做到) 即可.

第二步, 我们证明, 对于任意图 $G$, 若 $G$ 有 $m$ 条边, 则 $G$ 有一个子图 $H$, 满足 $\delta (H)>\frac{m}{n}$. 此时结合这两步结果立即证得原题. 注意到, 若 $G$ 存在一个顶点 $v$ 满足 $d(v)<\frac{m}{n}$, 去掉该顶点后 $G$ 的平均度数增加, 因此这种操作不能一直进行下去, 操作停止时我们就找到了一个满足条件的子图 $H$. 结论得证.

$\square$

我们接下来考虑 $H$ 不是树的情况. 我们首先指出如下的结果:

定理 2.4. 对任意至少有两条边的图 $H$, 总有$$\mathrm{ex}(n,H)\gtrsim n^{2-\frac{v(H)-2}{e(H)-1}}.$$

证明. 待定实数 $p$. 考虑随机图 $G=G(n,p)$, 即 $G$ 的顶点个数为 $n$, 每条边出现的概率为 $p$. 对于任意图 $H$, 显然 $G$ 中含 $H$ 的个数的期望小于等于 $n^{v(H)}{p}^{e(H)}$, 而 $G$ 的边数的期望为 $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. 因此, 记 $G$ 中含 $H$ 的个数为 $X$, 取 $p=\frac{1}{2}{n}^{-\frac{v(H)-2}{e(H)-1}}$, 则$$E(e(G)-X)\ge p\left(\genfrac{}{}{0ex}{}{n}{2}\right)-n^{v(H)}{p}^{e(H)}\ge \frac{1}{16}{n}^{2-\frac{v(H)-2}{e(H)-1}}.$$

因此, 总存在图 $G$ 使得 $e(G)-X\ge \frac{1}{16}{n}^{2-\frac{v(H)-2}{e(H)-1}}.$ 我们在 $G$ 所含的每个 $H$ 中均去掉一条边, 剩下的图就不包含 $H$ 作为子图, 即证得原题.

$\square$

注 2.5. 有时候我们取 $H$ 的子图, $\frac{v(H)-2}{e(H)-1}$ 可能会变小, 因此这个时候给出的界会更好一点.

由于若 $H$ 连通且不是树时 $v(H)\le e(H)$, 这一结果指出, $H$ 不是森林时, $\mathrm{ex}(n,H)$ 当 $n$ 趋于无穷时, 不是 $n$ 的一阶量. 事实上, Turán 定理指出, 当 $H$ 为三角形时, $\mathrm{ex}(n,H)$ 当 $n$ 趋于无穷时是 $n^2$ 级别的量. 关于这一问题, 我们有以下著名的结果:

定理 2.6. (Erdös–Stone–Simonovits 定理) 对任意至少有 1 条边的图 $H$, 有$$\mathrm{ex}(n,H)\le \frac{n^2}{2}\left(1-\frac{1}{\chi (H)-1}\right)+o(n^2),$$其中 $\chi (H)$ 是图 $H$ 的色数.

例 2.7. 完全图 $K_n$ 的色数是 $n$, 此时符合 Erdös–Stone–Simonovits 定理. 事实上, Turán 定理的阶的估计可以看成 Erdös–Stone–Simonovits 定理的一个特殊情况.

我们将在第五讲中证明这个结果. 我们可以看到, Erdös–Stone–Simonovits 定理给出了当图 $H$ 的色数大于等于 $2$ 的时候, 关于 $\mathrm{ex}(n,H)$ 的阶的一个基础的刻画. 然而, 不幸的是, 对于色数为 $2$ 的图, 我们仍然无法完全弄清楚 $\mathrm{ex}(n,H)$ 的阶. 关于这一问题, 有以下著名的猜想:

猜想 2.8. (Turán 有理指数猜想) 对于任意有理数 $1\le a<2$, 存在图 $H$, 使得 $\mathrm{ex}(n,H)=\Theta (n^a)$.

本节和下一节我们接下来将研究一些关于这一问题的一些经典结果. 本节我们研究 $H$ 为 $K_{s,t}$ 时候的情形. 事实上, 注意到若 $H\subseteq G$, 则 $\mathrm{ex}(n,H)\le \mathrm{ex}(n,G)$, 因此如果我们能够理解 $\mathrm{ex}(n,K_{s,t})$ 的阶, 我们就可以获得关于一般的图的 $\mathrm{ex}(n,H)$ 的一些刻画. Kövári, Sós, Turán 对于这一问题有以下经典的结果:

定理 2.9. 对每个正整数 $1\le s\le t$, 存在正实数 $C=C(s,t)$, 使得$$\mathrm{ex}(n,K_{s,t})\le C{n}^{2-1/s}.$$

证明. 假设 $G$ 是一个 $n$ 个顶点且不包含 $K_{s,t}$ 的图, 我们对 $G$ 中 $K_{s,1}$ 的个数算两次, 即考虑一切 $s+1$ 元顶点对 $(v,v_1,v_2,\cdots ,v_s)$ 的个数 $T$, 其中 $v$ 与顶点 $v_1,v_2,\cdots ,v_s$ 相连. 一方面, 注意到对于任意的 $s$ 个点 $v_1,v_2,\cdots ,v_s$, 由于 $G$ 不含 $K_{s,t}$, 这样的 $v$ 至多 $(t-1)$ 个, 因此$$H\le (t-1)\left(\genfrac{}{}{0ex}{}{n}{s}\right).$$

另一方面, 对每个顶点 $v$, 这样的顶点对恰有 $\left(\genfrac{}{}{0ex}{}{d(v)}{s}\right)$ 个, 因此, 由凸性, 我们有$$H=\sum _{v\in V(G)}\left(\genfrac{}{}{0ex}{}{d(v)}{s}\right)\ge n\left(\genfrac{}{}{0ex}{}{\frac{m}{n}}{s}\right).$$

利用 $\left(\genfrac{}{}{0ex}{}{x}{s}\right)=(1+o(1))\frac{x^s}{s!}$, 我们可以得到$$m\le \left(\frac{1}{2}+o(1)\right)(t-1{)}^{1/s}{n}^{2-1/s}.$$

$\square$

这一定理里中的界被猜想是紧的. 然而, 目前仍然无法完全证明这一猜想 (例如, 我们仍然不知道对于 $K_{4.4}$ 的情况, 这一界是否是紧的.) 不过, 我们能够确定, 对于一部分的 $s,t$, 这个界的确是紧的. 目前我们使用的构造主要来自于以下三种技巧:

•	概率方法. 概率方法是基本而有效的, 不过往往概率方法给出的界不是紧的.
•	代数方法. 这一方法利用一些数论或代数结构来给出一些构造. 不过, 这些构造往往只能运用于少数的情形.
•	随机代数构造. 这一方法结合以上两种技巧, 能够同时吸收这两种方法的优点, 但往往实施困难, 并且需要一些高深的工具.

我们前面已经运用概率方法给出了一个关于 $\mathrm{ex}(n,K_{s,t})$ 的下界. 不过, 这个方法给出的界和我们前文中所述的定理的界有一定差距. 本节我们再给出另外两种方法的构造.

对于素数 $p$ 和正整数 $s\ge 2$, 考虑图 ProjNormGraph${}_{p,s}=G(V,E)$, 其中 $V={\mathbb{F}}_{p^{s-1}}\times {\mathbb{F}}_p^{\times }$. 此时, $n=(p-1)p^{s-1}$. 对于点 $(X,x)$ 和 $(Y,y)$, 连接这两点间有边当且仅当$$N(X+Y)=xy,$$其中映射 $N:{\mathbb{F}}_{p^{s-1}}\to {\mathbb{F}}_p^{\times }$ 按如下法则定义:$$N(x)=x^{\frac{p^{s-1}-1}{p-1}}.$$

定理 2.10. 在图 ProjNormGraph${}_{p,s}$ 中, 有以下结论:

a. 若 $|V|=n$, 则$$|E|=(\frac{1}{2}-o(1))n^{2-1/s}.$$

b. 图 ProjNormGraph${}_{p,s}$ 不包含 $K_{s,(s-1)!+1}$ 作为子图.

例 2.11. 我们来考虑一个例子. $s=2$, 时, $V={\mathbb{F}}_p\times {\mathbb{F}}_p^{\times }$, $N(x)=x$. 此时, 对于任意一点 $(X,x)$ 和任意的 $y$, 恰存在唯一的 $Y$ 使得 $X+Y=xy$, 故总边数为 $\frac{1}{2}p(p-1{)}^2$, 顶点数为 $p(p-1)$, 因此 a 成立; 若 $X+Y_1=x{y}_1$, $X+Y_2=x{y}_2$, 则要么 $y_1=y_2$, 要么相减即解出唯一一组 $(X,x)$, 故图中不存在 $K_{2,2}$. 因此这个构造符合条件.

注 2.12. 图 ProjNormGraph${}_{p,s}$ 不一定是简单图, 可能有自己连自己的边. 但这样的边的数量至多为 $n$, 因此我们去掉这些边后就得到了满足条件的简单图.

事实上, 根据图 ProjNormGraph${}_{p,s}$ 的构造, 我们可以看出, 若 $t\ge (s-1)!+1$, 结合定理 $1.2.2$, 我们即知 $\mathrm{ex}(n,K_{s,t})=\Theta (n^{2-\frac{1}{s}})$.

证明.

为了证明这个结论, 我们先不加证明地指出代数几何中的如下引理.

引理 2.13. 设 $\mathbb{F}$ 是域, $a_{i,j},b_{i,j}\in \mathbb{F}$, 并且若 $i\ne i^{\prime }$, 则 $a_{i,j}\ne a_{i,j^{\prime }}$. 那么, 如下的方程组$$\begin{array}{rl}(x_1-a_{11})(x_2-a_{12})\cdots (x_s-a_{1s})& =b_1\\ (x_1-a_{21})(x_2-a_{22})\cdots (x_s-a_{2s})& =b_2\\ & ⋮\\ (x_1-a_{s1})(x_2-a_{s2})\cdots (x_s-a_{ss})& =b_s\end{array}$$至多只有 $s!$ 组解.

回到原题. 首先, 对于任意满足 $N(X+Y)\ne 0$ 的 $Y$, 均存在唯一的 $y$ 使得 $xy=N(X+Y)$, 故每个顶点 $(X,x)$ 的度数是 $p^{s-1}-1$, 这就显然推出了 a.

接下来我们证明 b. 固定 $s$ 个点 $(Y_i,y_i)$, 那么与它们均相连的 $(X,x)$ 满足方程组 $N(X+Y_i)=y_i(1\le i\le s)$. 将这些式子均与最后一式相除, 方程组化为$$N(\frac{X+Y_i}{X+Y_s})=\frac{y_i}{y_s},$$两边同时除以 $N(Y_i-Y_s)$, 方程组即$$N(\frac{1}{X+Y_s}+\frac{1}{Y_i-Y_s})=\frac{y_i}{y_{s}N(Y_i-Y_s)}.$$注意到$$\begin{array}{rl}N(x+y)=(x+y{)}^{\frac{p^{s-1}-1}{p-1}}& =(x+y)(x+y{)}^p\cdots (x+y{)}^{p^{s-1}}\\ & =(x+y)(x^p+y^p)\cdots (x^{p^{s-1}}+y^{p^{s-1}}),\end{array}$$因此, 记$$x_i=(\frac{1}{X+Y_s}{)}^{p^{i-1}},a_{ij}=-(\frac{1}{Y_i-Y_s}{)}^{p^{j-1}},b_i=\frac{y_i}{y_{s}N(Y_i-Y_s)},$$上式就化成引理所述形式, 至多只有 $(s-1)!$ 组解, 且每一组至多对应一组满足条件的 $(X,x)$. 因此 b 得证.

$\square$

我们接下来给出关于 $\mathrm{ex}(n,K_{s,t})$ 的一个随机代数构造. Bukh 在 2015 年运用这一方法证明, 存在函数 $t_0(s)$, 使得若 $t\ge t_0(s)$, 则 $\mathrm{ex}(n,K_{s,t})=\Theta (n^{2-\frac{1}{s}})$. 注意, 目前这一结果给出的 $t_0$ 远大于我们上一个方法中给出的界 $(s-1)!+1$. 尽管如此, 这一方法由于结合了代数构造和概率方法, 因此比纯粹的代数方法更加具有一般性, 也有更多的推广价值.

在进行我们的构造之前, 我们首先需要陈述一个代数几何中的引理作为我们的准备工作. 这个引理的证明需要用到复杂的代数几何知识, 因此不会在这里给出.

引理 2.14. 对于任意正整数 $s,d$, 存在实数 $C=C(s,d)$, 满足: 若 $f_1(Y),\cdots ,f_s(Y)$ 是 ${\mathbb{F}}_q^s$ 上的次数不超过 $d$ 的多项式, 则它们的公共零点个数要么少于 $C$, 要么多于 $q-C\sqrt{q}$.

现在我们来介绍 Bukh 的构造. 对于任意正整数 $s\ge 4$, 记 $d=s^2-s+2$, 并待定一个素数 $q$. 我们从一切满足下述条件的多项式 $f\in {\mathbb{F}}_q[x_1,x_2,\cdots ,x_s,y_1,y_2,\cdots ,y_s]$ 中随机选取一个多项式 $f$: $f$ 关于 $X=(x_1,x_2,\cdots ,x_s)$ 和 $Y=(y_1,\cdots ,y_s)$ 的次数均不超过 $d$. 对于给定的 $f$, 构造二部图 $G$ 如下: $G$ 的两个部分 $L=R={\mathbb{F}}_q^s$, 当 $f(X,Y)=0$ 时, 连接边 $(X,Y)\in L\times R$. 记 $n$ 为 $G$ 一个部分的顶点数. 注意到对任意给定的 $u,v$, $f(u,v)=0$ 的概率恰为 $\frac{1}{q}$(对于任意 $f$, 恰有唯一常数 $c$ 使得 $f(u,v)+c=0$), 因此我们有 $\mathbb{E}(e(G))=\frac{n^2}{q}.$

对任意正整数 $r\le d$, 我们考虑集合 $U,V\in {\mathbb{F}}_q^s$, 其中 $|U|=r,|V|=s$. 我们指出, $f(u,v)=0$ 对一切 $u\in U,v\in V$ 的概率为 $q^{-sr}$. 首先, 我们取一个映射 $F:{\mathbb{F}}_q^s\to {\mathbb{F}}_q$, 使得对于一切 $u\in U$, $F(u)$ 两两不同. 注意到对于不同的 $u,v$, 满足 $f(u)=f(v)$ 的映射占全部映射的 $\frac{1}{q}$, 而我们可以取 $q>s^2$, 此时 $F$ 显然可以找到. 于是, 我们可以把 $F$ 延拓成 $F^{\prime }:{\mathbb{F}}_q^s\to {\mathbb{F}}_q^s$, 使得对于一切 $u\in U$, $F^{\prime }(u)$ 的第一个分量两两不同. 因此, 用 $F^{\prime }(u)$ 代替 $u$, 我们可以不妨设一切 $u\in U$ 的第一个分量两两不同. 同理, 我们可以不妨设一切 $v\in V$ 的第一个分量两两不同. 记$$g(x_1,y_1)=\sum _{\genfrac{}{}{0ex}{}{0\le i\le s-1}{0\le j\le r-1}}{a}_{ij}{x}_1^i{y}_1^j=\sum _{0\le j\le r-1}{a}_j(x_1)y_1^j,$$

其中 $a_{ij}$ 为 ${\mathbb{F}}_q$ 上的独立均匀分布随机变量, $a_j$ 为关于 $x_1$ 的多项式. 注意到 $f$ 和 $f+g$ 有相同的分布, 因此我们只需证明, 对于任意 $b_{uv}\in {\mathbb{F}}_q(u\in U,v\in V)$, 均存在 $a_{ij}$ 使得 $g(u,v)=b_{uv}$, 即证明了 $f(u,v)=0$ 对一切 $u\in U,v\in V$ 的概率为 $q^{-sr}$. 对一切 $u\in U$, 由拉格朗日插值公式, 我们可以取一个次数不超过 $r-1$ 的多项式 $g_u(y_1)$ 使得对一切 $v\in V$, 有 $g_u(v)=b_{uv}$, 再用拉格朗日插值公式依次取出多项式 $a_i$ 使得 $g(u,y_1)=g_u(y_1)$, 就有 $g(u,v)=b_{uv}$. 因此, 我们证明了 $f(u,v)=0$ 对一切 $u\in U,v\in V$ 的概率为 $q^{-sr}$.

任取 $L$ 的一个 $s$ 元子集 $U$, 并设 $X$ 为 $U$ 中所有点的公共邻居个数. 对于 $v\in R$, 若 $v$ 与 $U$ 中所有点均相邻, 记 $I(v)=1$, 否则记 $I(v)=0$. 此时$$\begin{array}{rl}\mathbb{E}(X^d)=\mathbb{E}(\sum _{v\in R}I(v){)}^d)& =\sum _{v_1,\cdots ,v_d\in {\mathbb{F}}_q^s}\mathbb{E}(I(v_1)\cdots I(v_d))\\ & =\sum _{r\le d}\left(\genfrac{}{}{0ex}{}{q^s}{r}\right)q^{-rs}{M}_r\le \sum _{r\le d}{M}_r,\end{array}$$

其中 $M_r$ 为从 $\{1,2,\cdots ,d\}$ 到 $\{1,2,\cdots ,r\}$ 的满射个数. 记 $M={\sum }_{r\le d}{M}_r$. 设多项式 $f_1(Y),f_2(Y),\cdots ,f_s(Y)$ 为一切多项式 $f(u,Y)$, 其中 $u\in U$. 对 $f_i(Y)$ 用引理 1.2.7 知, 存在实数 $C=C(s,d)$, 使得 $X>C$ 时 $X>q-C\sqrt{q}$. 我们取 $q$ 充分大使得 $q-C\sqrt{q}\ge \frac{q}{2}$. 因此, 由马尔可夫不等式,$$\mathbb{P}(X\ge C)=\mathbb{P}(X\ge \frac{q}{2})\le \frac{\mathbb{E}(X^d)}{(\frac{q}{2}{)}^d}\le \frac{M}{(\frac{q}{2}{)}^d}.$$

我们从 $R$ 的每个公共邻居个数大于等于 $C$ 的 $s$ 元子集中去掉一个顶点, 剩下的图就不包含 $K_{s,C+1}$ 作为子图. 此时, 剩下的图 $G^{\prime }$ 的顶点个数的期望$$\mathbb{E}(e(G^{\prime }))\ge \frac{n^2}{q}-\left(\genfrac{}{}{0ex}{}{n}{s}\right)\frac{M}{(\frac{q}{2}{)}^d},$$

注意到 $n=q^s,d=s^2-s+2$, 代入知 $\mathbb{E}(e(G^{\prime }))\ge (1-o(1))n^{2-\frac{1}{s}}$, $v(G^{\prime })\le 2n$. 因此我们的构造就符合要求. 结论得证. .