3. 禁用子图问题 (二)

这一讲我们首先讨论一些关于 $\mathrm{ex}(n,H)$ 的其他结果.

定理 3.1. 设 $H=A\cup B$ 为二部图, 并且对于任意 $v\in A$, $d(v)\le r$. 那么, 存在 $C=C_H$ 使得$$\mathrm{ex}(n,H)\le C{n}^{2-1/r}.$$

证明. 记 $a=|A|,b=|B|$. 我们先证明如下的引理:

引理 3.2. 设 $H=A\cup B$ 为二部图, 并且对于任意 $v\in A$, $d(v)\le r$. 那么, 对任意图 $G$, 如果 $G$ 中存在 $b$ 个顶点, 其中任意 $r$ 个的公共邻居个数大于等于 $a+b$, 则 $G$ 包含 $H$ 作为子图.

证明. 我们先选取这 $b$ 个顶点作为 $B$(顺序任意). 接下来, 我们再按顺序在 $G$ 中选取 $A$ 中的顶点. 每次选取一个顶点时, 只需要其邻域包含给定的不超过 $r$ 个点. 注意到这些点的公共邻居个数大于等于 $a+b$, 故必可以从中选出一个与已经选取的点均不同的点作为该顶点. 引理证毕.

$\square$

回到原题. 我们证明 $C$ 充分大时满足条件. 由引理, 我们只需从 $G$ 中选出 $b$ 个顶点, 其中任意 $r$ 个的公共邻居个数大于等于 $a+b$. 对任意边数大于 $C{n}^{2-1/r}$ 的图 $G(V,E)$, 我们随机地依次取其 $r$ 个顶点 $v_1,v_2,\cdots ,v_r$(允许重复), 并记这些顶点构成的集合为 $T$, 它们的邻域为 $A$. 则$$\begin{array}{rl}\mathbb{E}(|A|)& =\sum _{v\in V}\mathbb{P}(v\in A)\\ & =\sum _{v\in V}\mathbb{P}(T\subseteq N(v))\\ & =\sum _{v\in V}(\frac{d(v)}{n}{)}^r\\ & \ge n(\frac{1}{n}\sum _{v\in V}(\frac{d(v)}{n}){)}^r\\ & =(\frac{C}{2}{)}^r.\end{array}$$

我们接下来试图从 $A$ 中选出这 $b$ 个顶点. 称 $V$ 的一个 $r$ 元子集为坏的, 如果其公共邻居个数小于 $a+b$. 设 $A$ 中所含坏的子集的个数为 $X$. 如果我们证明了 $\mathbb{E}(|A|)-\mathbb{E}(X)>b,$ 那么, 我们就可以选出一个 $A$, 使得其中所含的坏子集个数小于 $|A|-b$, 然后我们对于每个坏子集, 依次删去 $A$ 中的一个元素, 剩下的元素就满足要求.

对于 $V$ 的一个 $r$ 元子集 $Q$, 我们来考察它是坏子集且属于 $A$ 的概率. 若 $Q$ 属于 $A$, 则 $v_1,v_2,\cdots ,v_r$ 必须均在 $Q$ 的邻域中, 而 $Q$ 的公共邻居个数小于 $a+b$, 因此这一概率就小于 $(\frac{a+b}{n}{)}^r$, 故$$\mathbb{E}(X)<\left(\genfrac{}{}{0ex}{}{n}{r}\right)(\frac{a+b}{n}{)}^r<(a+b{)}^r.$$

因此, 我们可以选取充分大的实数 $C$ 使得了 $\mathbb{E}(|A|)-\mathbb{E}(X)>b$. 结论证毕.

$\square$

注 3.3. 这一例子相较于前面的例子有一些变化, 但是再次向我们展示了 Alterations 的威力: 我们适当的选取了一个集合 $A$ 作为桥梁, 使得我们能够在 $A$ 中进行满足条件的选取. 这样的 $A$ 的构造正是 Alterations 的精妙之处.

定理 3.4. 对于偶圈 $C_{2k}$, 存在实数 $c_k$, 使得$$\mathrm{ex}(n,C_{2k})\le c_k{n}^{1+1/k}.$$

证明. 我们来证明, 存在实数 $c_k$, 若图 $G$ 的边数大于等于 $c_k{n}^{1+\frac{1}{k}}$, 则 $G$ 含 $C_{2k}$. 我们先进行一些预处理. 首先, 我们可以不妨设 $G$ 为二部图, 这是由于下述经典的引理:

引理 3.5. 对于任意图 $G$, 存在 $G$ 的一个二部子图 $H$, 满足: 对于任意 $v\in H$, $2e_H(v)\ge e_G(v)$. 特别地, 此时即有 $2e(H)>e(G)$.

证明. 我们选取一切 $G$ 的二部子图中边数最多的那个. 若存在 $v\in H$, 使得 $2e_H(v)<e_G(v)$, 我们将 $v$ 移到另一个部分, 这样诱导的二部子图边数更多, 矛盾. 因此结论成立.

$\square$

由该引理, 我们可以不妨设 $G$ 为二部图 (此时 $c_k$ 减半). 接下来, 我们可以把条件加强为图 $G$ 每个顶点的度数大于等于 $c_k{n}^{\frac{1}{k}}$. 事实上, 我们可以对 $n$ 实行归纳法: $n=1$ 时命题平凡. 若命题对 $n-1$ 的情形成立, 对于 $n$ 的情形, 如果 $G$ 中一个顶点的度数小于等于 $c_k{n}^{\frac{1}{k}}$, 那么去掉该点后, 剩下的边数多于 $c_k{n}^{1+\frac{1}{k}}-n^{\frac{1}{k}}\ge c_k(n-1{)}^{1+\frac{1}{k}}$, 因此使用归纳假设, 就存在 $C_{2k}$. 故我们可以把条件加强为图 $G$ 每个顶点的度数大于等于 $c_k{n}^{\frac{1}{k}}$.

我们现在来证明, 若 $G(V,E)$ 满足 $|V|=n$. 若 $G$ 每个顶点的度数均大于等于 $s=40k{n}^{\frac{1}{k}}$, 则 $G$ 含 $C_{2k}$ 作为子图, 这就证明了原结论. 我们用反证法. 假设 $G$ 中不含 $C_{2k}$. 任取 $G$ 中一顶点 $x$, 并把 $G$ 中的点按到 $x$ 的距离分类为集合 $V_0,V_1,\cdots$, 即 $V_0=\{x\}$, $V_i$ 表示到点 $x$ 距离为 $i$ 的集合. 任取正整数 $1\le i\le k$. 我们归纳证明: $\frac{|V_i|}{|V_{i-1}|}>n^{\frac{1}{k}}$, 这样就有 $|V_k|>n$, 就推出了矛盾.

$i=1$ 时问题显然. 设命题对 $i-1$ 的情况成立, 我们考虑 $i$ 的情况. 设 $H=V_i\cup V_{i-1}$, 且 $H$ 被分为连通分支 $H_1,H_2,\cdots ,H_q$, 并记 $W_1$ 为 $H_1$ 在 $V_{i-1}$ 的那一部分, $X_1$ 为另一部分. 我们首先证明 $e(H_1)<4kv(H_1)$.

$|W_1|=0,1$ 和 $|H_1|=0,1$ 时命题均显然. 下设 $|W_1|,|H_1|\ge 2$. 称 $G$ 中的一条路为单调的, 如果其不经过两个到 $x$ 距离相同的顶点. 我们选最小的整数 $q$, 使得 $V_q$ 中存在一个顶点 $a$, 有两条只相交于 $a$ 的单调路连接 $a$ 与 $W_1$ 中一点 (由于 $|W_1|>2$, 故易于验证这样的路存在), 并记这两条路为 $C,D$. 若 $x\ne q$, 对于 $W_1$ 中任意一点 $w$, $w$ 与 $x$ 有一条单调路相连, 且这条路必须与 $a$ 到 $W_1$ 的单调路相交 (否则, 将 $a$ 到 $W_1$ 的单调路任意扩展成 $a$ 到 $x$ 的路, 考察它与 $w$ 到 $x$ 的这条单调路的距 $x$ 最远的交点即与 $q$ 的最小性矛盾.) 因此, $W_1$ 中所有点均与 $a$ 有单调路相连.

对于 $W_1$ 中任意一点, 如果存在从它到 $a$ 的单调路, 只与路 $C$ 交于点 $a$, 则称该点为好的, 否则称其为坏的. 那么, 路 $C,D$ 的顶点分别为好的和坏的, 因此好的和坏的顶点均存在; 对于一个好的顶点 $p$ 和坏的顶点 $q$, 考察从 $p$ 到 $a$ 的一条只与路 $C$ 交于点 $a$ 的单调路和 $q$ 到 $a$ 的任意一条单调路. 由于 $q$ 是坏的, 它与路 $C$ 有别的交点, 我们考察其中距 $x$ 最远的那个点 $r$. 我们断言: 从 $q$ 到 $r$ 再沿着 $C$ 走的这条路与从 $p$ 到 $a$ 的这条路没有除 $a$ 以外的交点. 否则, 若它还有交点 $s$, 则 $s$ 肯定比 $r$ 离 $x$ 更远, 因此从 $q$ 到 $s$ 再沿着 $p$ 到 $a$ 的这条路就与路 $C$ 没有交点, 这与 $q$ 是坏的矛盾! 结论得证.

因此, 对于任意一个好的顶点和坏的顶点, 它们均可以用一条的通过 $a$ 的长度为 $2(q+1-i)$ 的路连接. 由于 $G$ 中没有 $C_{2l}$, 因此它们不能在 $H_1$ 中用长度为 $2(t+i-q-1)$ 的路连接. 于是, 我们可以把 $H_1$ 按好的, 坏的, 和 $X_1$ 中的点来三染色. 由奇偶性, 一条长度为 $2(t+i-q-1)$ 的路只能连接两个 $W_1$ 中的点或 $X_1$ 中的点, 因此只能好的连好的, 坏的连坏的, $X_1$ 中的连 $X_1$ 中的. 我们接下来说明这就可以导出我们想要的不等式.

引理 3.6. 给定正整数 $t$. 若连通图 $G$ 满足 $e(G)\ge 2tv(G)$, 则无论怎么将 $G$ 的顶点三染色, 一定存在一条长度为 $t$ 的路, 端点异色.

证明. 我们对 $|V(G)|$ 归纳. $|V(G)|=4t+1$ 时 $G$ 为完全图, 结论成立. 假设 $|V(G)|=k$ 时结论成立, 考虑 $|V(G)|=k+1$ 的情况. 我们分三种情况讨论:

•	若 $G$ 中存在一个点 $v$, 去掉它之后的每个连通分支均有三种颜色点, 且 $d(v)<2t$, 则去掉该点后必存在一个连通分支 $G^{\prime }$, 有三种颜色的点, 且 $e(G^{\prime })\ge 2tv(G^{\prime })$, 此时由归纳假设即证;
•	若 $G$ 中存在一个点 $v$, 去掉它之后的某个连通分支不存在某种颜色的点, 不妨设为黄色. 则距 $v$ 最近的黄点到 $v$ 的距离若超过 $t$, 则该黄点到 $v$ 有一条长度至少为 $t$ 的路, 这上面没有其他黄点, 这就产生了一个从黄点出发到一个非黄点的长度为 $t$ 的路; 若不超过 $t$, 不妨设为 $r$, 我们再在不含黄点的这个连通分支中找一条从 $v$ 出发的长度为 $t-r$ 的路, 就诱导了一条从黄点出发到一个非黄点的长度为 $t$ 的路. 而这样的路一定能找到, 是因为若我们选取一条在该连通分支中的从 $v$ 出发的最长路, 则其另一个端点若不是割点, 则 $d(v)\ge 2t$, 因此就可以继续再连一个其他的点; 若为割点, 则由于该割点是第一次经过, 必然可以再连向一个新的连通分支. 因此这种情况证毕.
•	若 $G$ 中每个点均满足 $d(v)\ge 2t$, 则对于任意一点 $r$ 和两个其邻域中的点 $p,q$, 我们可以从 $r$ 出发, 连出一条不经过点 $p,q$ 的长度为 $t-1$ 的路, 设其端点为 $s$. 那么, 点 $p,q$ 中若有点与 $s$ 异色, 结论得证; 否则, 任意两个具有公共顶点的点均同色. 此时, 递推易见所有到 $s$ 距离为偶数的点均同色, 到 $s$ 距离为奇数的点也均同色, 因此所有点只能有两种颜色, 矛盾! 因此这种情况也证毕. 综上所述, 根据归纳原理, 引理得证.

因此, 根据引理, 我们就有 $e(H_1)<4kv(H_1)$. 对所有连通分支求和, 我们有 $e(H)<4kv(H)$. 类似地, 记 $H^{\prime }=V_{i-1}\cup V_{i-2}$, 则 $e(H^{\prime })<4kv(H^{\prime })$. 将两式相加, 我们有$$4k(|V_{i-1}|+|V_i|+|V_i|+|V_{i+1}|)=4t(v(H)+v(H^{\prime }))>e(H)+e(H^{\prime })\ge 40k{n}^{\frac{1}{k}}|V_i|.$$由归纳假设, $\frac{|V_{i-1}|}{|V_{i-2}|}>n^{\frac{1}{k}}$, 故 $|V_{i-1}|\ge |V_{i-2}|$. 因此, 我们有$$|V_{i+1}|>10n^{\frac{1}{k}}|V_i|-2|V_i|-|V_{i-1}|\ge n^{\frac{1}{k}}|V_i|.$$因此命题得证.

$\square$

这个界是目前最好的上界. 然而, 我们目前只能证明, $k=2,3,5$ 时我们可以取到这个上界. 我们已经证明了 $k=2$ 的情况, 我们在这里陈述 $k=3$ 的构造.

我们考虑 ${\mathbb{F}}_q$ 上的 4 维射影空间中的二次超曲面 $S:x_0^2+x_1{x}_2+x_3{x}_4=0$. 我们作一个二部图 $G(V,E)$, 顶点集分别是 $\mathcal{L}$ 和 $S$, 其中 $\mathcal{L}$ 是 $S$ 中所有直线的集合. 对于 $\mathcal{L}$ 中一条直线 $\ell$, 我们连接它和 $S$ 中一点 $s$ 当且仅当 $\ell$ 经过 $s$. 我们来考虑这个图.

首先, 这个图中没有 $C_6$. 这只需说明, 任意三条直线均不共面. 注意到任何二次曲面若不包含于该超曲面, 和该超曲面的交就是一个二次曲线, 故不可能含三条直线. 而 $x_0^2+x_1{x}_2$ 为不可约多项式, 故显然没有任何二次曲面包含于其中.

我们接下来研究这个二部图. 显然 $|S|=\Theta (q^3)$; 我们只需说明 $S$ 中任意一点在 $q+1$ 条直线上, 注意一条直线显然经过 $q+1$ 个点, 这就说明 $|\mathcal{L}|=\Theta (q^3)$, 从而 $|V|=\Theta (q^3),|E|=\Theta (q^4)$, 这就说明了结论.

我们首先考虑 $S$ 中一点 $[0,1,0,0,0]$. 过该点的直线可以写为 $[a_{1}t,0,a_{2}t,a_{3}t,a_{4}t]$. 代入二次曲面的方程, 我们有 $a_2=0$ 且 $a_1^2+a_3{a}_4=0$. 注意到 $a_1,a_3,a_4$ 差一个比表示同一直线, 显然此时直线共有 $q+1$ 条 ($a_4=0$ 时一条, $a_4\ne 0$ 时 $q$ 条).

我们最后说明, $S$ 中所有点均可以通过一个保持 $S$ 不动的线性变换变成这个点, 从而说明过 $S$ 中所有点的直线数目相等. 对于任意一点 $[a_0,a_1,a_2,a_3,a_4]$, 我们首先不妨设 $a_1\ne 0$. 考虑线性变换: $$[x_0,x_1,x_2,x_3,x_4]\to [x_0+k{x}_1,x_1,x_2-(k^2+ml)x_1-2k{x}_0-l{x}_3-m{x}_4,x_3+m{x}_1,x_4+l{x}_1],$$

易于验证该线性变换保证 $S$ 不动. 因此, 我们可以选取合适的 $k,m,l$, 将 $[a_0,a_1,a_2,a_3,a_4]$ 变为 $[0,a_1,a_2,0,0]$, 此时自然 $a_2=0$, 因此即变换到点 $[0,1,0,0,0]$. $a_1=0$ 的情形只需先复合一个线性变换使 $a_1\ne 0$ 即可. 结论得证.

$\square$

本讲的最后我们来讨论 Erdös-Turán 问题. 我们知道, 图 $G$ 没有 $K_t$ 时, $G$ 的边数的最大值在 $G$ 为完全 $t-1$ 部图时取等. 然而, 在这种取等中, $G$ 有一个很大的独立集. 一个问题是, 我们限制 $G$ 的最大独立集元素个数, 例如设 $G$ 的最大独立集的元素个数是 $o(n)$ 级别且 $G$ 中没有 $K_t$, $G$ 最多能有几条边? 我们定义 $RT(n,K_t,o(n))$ 为 $G$ 的最大独立集的元素个数是 $o(n)$ 级别且 $G$ 中没有 $K_t$ 时 $G$ 边数的最大值. 为对于三角形的情形, 这个问题是不困难的: 由于 $G$ 中任意一个点的邻域都是独立集, 所以最多 $o(n)$ 条边, 因此总边数最多 $o(n^2)$. 对于 $t>3$, 这个问题就没有那么明显了. 事实上, 在本讲中, 我们要证明以下的结果:

定理 3.7. 当 $t$ 为奇数时, $RT(n,K_t,o(n))=(\frac{t-3}{2t-2}+o(1))n^2.$

$t$ 为偶数的情形比较复杂, 且需要使用 Regularity lemma, 因此我们将在第五讲中证明. 我们本节中先来解决奇数的情况.

证明. 我们首先给出构造. 首先, 我们考虑一个完全 $K_{\frac{t-1}{2}}$ 部图, 每个部分的点数均为 $\frac{2n}{t-1}$. 此时有 $\frac{t-3}{2t-2}{n}^2$ 条边. 接下来, 我们证明, 对任意正整数 $n$, 存在一个有 $n$ 个顶点的图 $H$, 无三角形, 最大独立集数为 $o(n)$. 如果这样的图 $H$ 存在, 我们在这个完全 $K_{\frac{t-1}{2}}$ 部图的每个部分放入一个 $H$, 得到的新的图的最大的独立集数为 $o(n)$, 且无 $K_t$(否则, 由抽屉原理, 必有一个部分有三个点, 矛盾.) 这样就构造出了一个边数大于等于 $\frac{t-3}{2t-2}{n}^2$ 的, 无 $K_t$, 最大独立集数为 $o(n)$ 的图.

我们运用概率方法. 我们考虑随机图 $G(n,p)$, $p$ 待定. 那么, 对任意实数 $c<0.1$, $G$ 中含一个大小为 $cn$ 的独立集的概率不超过$$\left(\genfrac{}{}{0ex}{}{n}{cn}\right)(1-p{)}^{\frac{cn(cn-1)}{2}}<e^{-pc{n}^2+cn\ln n},$$而 $G$ 中含三角形的个数的期望为 $p^3{n}^3$. 因此, 取 $p=1/(n^{\frac{3}{4}})$, 那么 $G$ 含大小为 $cn$ 的独立集的概率就不超过 $0.1$, $G$ 中含超过 $cn$ 个三角形的概率也不超过 $0.1$. 我们取 $G$ 使得 $G$ 不含超过 $cn$ 个三角形, 且不含大小为 $cn$ 的独立集, 那么我们从 $G$ 中每个三角形中删去一条边, 剩下的图就不含三角形, 也不含大小为 $3cn$ 的独立集. 结论得证.

我们接下来证明, 如果图 $G$ 的边数大于等于 $(\frac{t-3}{2t-2}+2r)n^2$, 且 $nr>10$, 则图 $G$ 就至少有一个大小为 $\frac{r\sqrt{r}}{2}n$ 的独立集, 或一个 $K_t$. 注意, 这就导出了原结论. 我们首先证明一个引理:

引理 3.8. 给定实数 $ϵ,c$. 若图 $G(V,E)$ 满足 $|V|=n,|E|=\frac{c}{2}{n}^2$, $nϵ>2$, 则图 $G$ 存在一个子图 $G^{\prime }(V^{\prime },E^{\prime })$, 满足 $n^{\prime }\ge \frac{\sqrt{ϵ}}{2}n$, 且 $G^{\prime }$ 的每个顶点度数均大于等于 $(c-ϵ)n^{\prime }$.

证明. 首先, 我们可以不妨设 $ϵ<c<1$. 我们执行如下操作: 记 $G_0=G$. 若 $G_i$ 的某个顶点度数大于等于 $(c-ϵ)|G_i|$, 则去掉该顶点, 剩下的图记为 $G_{i+1}$. 假设最后操作结束时为 $G_{n-k}$. 则$$\frac{c}{2}{n}^2\le \sum _{i=0}^{n-k-1}(n-i)(c-ϵ)+\frac{k(k-1)}{2}\le \frac{1}{2}(k^2+(c-ϵ)(n^2-k^2+n-k)),$$移项变形, 我们有$$ϵn^2\le (1+ϵ-c)k^2+n-k<2k^2+\frac{1}{2}ϵn^2,$$即 $k>\frac{\sqrt{ϵ}}{2}n$. 引理得证.

$\square$

由引理, 我们取 $ϵ=r$, 我们就只需证明, 若图 $G$ 每个顶点的度数均大于等于 $(\frac{t-3}{t-1}+r)n$, 则含 $K_t$ 或含大小为 $rn$ 的独立集. 我们用反证法. 考察 $G$ 中的最大团 $U$, 并设其顶点为 $v_1,v_2,\cdots ,v_m$, 剩下的点构成集合 $V$, 则 $m\le t-1$.

我们现在来对 $e(U,V)$ 算两次. 一方面, 对 $U$ 计算, 我们有$$e(U,V)\ge (\frac{t-3}{t-1}+r)mn-\frac{m(m-1)}{2}.$$另一方面, 我们把 $V$ 中的点分成两类: 第一类, 和 $v_1,v_2,\cdots ,v_m$ 中至多 $m-2$ 个点相连的点. 第二类, 和 $v_1,v_2,\cdots ,v_m$ 中 $m-1$ 个点相连的点. 那么, 和 $v_1,v_2,\cdots ,v_m$ 中固定的 $m-1$ 个点相连的点构成独立集, 因此至多 $rn$ 个, 即第二类的点总共至多 $(m-1)rn$ 个. 因此, 我们有$$e(U,V)\le (m-2)|V|+(m-1)rn=(m-2)(n-m)+(m-1)rn.$$

$\square$

联立两式, 我们有$$\frac{t-3}{t-1}mn-\frac{m(m-1)}{2}\le (m-2)(n-m)-rn.$$由于 $t\ge m+1$, 故 $\frac{t-3}{t-1}\le \frac{m-2}{m}$, 代入整理得$$(m-2)m+rn\le \frac{m(m-1)}{2},$$矛盾! 因此反证假设不成立, 结论得证.