9. 禁止稀疏二分图

对于任何二分图 $H$, 它总是包含在某些 $K_{s,t}$ 中. 根据定理 5.2, $$\mathrm{ex}(n,H)\le \mathrm{ex}\left(n,K_{s,t}\right)\lesssim n^{2-\frac{1}{s}}$$当 $H$ 是稀疏二分图时, 第一个不等式一般不紧. 在本节中, 我们将看到一些给稀疏二分图 $H$ 提供 $\mathrm{ex}(n,H)$ 更好上界的技术.

第一个结论给出了当 $H$ 是二分图并且一个部分的顶点度数有上界时 $\mathrm{ex}(n,H)$ 的上界.

定理 9.1 (Füredi 1991). 令 $H$ 为顶点集 $A\cup B$ 的二分图, 其中 $A$ 中的每个顶点的度数至多为 $r$. 那么存在一个常数 $C=C_H$ 使得$$\mathrm{ex}(n,H)\le C{n}^{2-\frac{1}{r}}$$

为了证明这个结论, 我们引入下面被称为 “独立随机选择” 的概率技术. 这个引理的主要思想是: 如果 $G$ 有很多边, 那么存在 $V(G)$ 的一个大的子集 $U$, 使得 $U$ 中顶点的所有小子集都有许多共同的邻点.

引理 9.2 (Dependent random choice: Alon, Krivelevich and Sudakov 2003). 设 $u,n,r,m,t\in \mathbb{N},\alpha >0$ 是满足下述不等式的数$$n{\alpha }^t-\left(\genfrac{}{}{0ex}{}{n}{r}\right){\left(\frac{m}{n}\right)}^t\ge u$$则每个至少有 $\alpha n^2/2$ 条边的 $n$ 顶点图 $G$ 包含一个大小至少为 $u$ 的顶点子集 $U$, 且 $U$ 的任意元素个数为 $r$ 的子集 $S$ 至少有 $m$ 个共同邻点.

证明. 令 $T$ 是从 $V(G)$ 中均匀随机选择的一个有 $t$ 个顶点的序列 (允许顶点重复) . 令 $A$ 是 $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}{\left(\frac{d(v)}{n}\right)}^t\\ & \stackrel{\text{convexity}}{\ge }n{\left(\frac{1}{n}\sum _{v\in V}\frac{d(v)}{n}\right)}^t\ge n{\alpha }^t\end{array}$$对于 $V$ 的任意元素个数为 $r$ 的子集 $S$, 事件 $A$ 包含 $S$ 发生, 当且仅当 $T$ 包含在 $S$ 的公共邻域中, 该事件发生的概率为$${\left(\frac{\#S\text{的公共邻居}}{n}\right)}^t$$

我们称公共邻点少于 $m$ 的集合为坏集. 则根据上面所得到的概率我们知道, 所有由 $r$ 个元素构成的坏子集 $S\subset V$ 包含在 $A$ 中的概率小于 $(m/n{)}^t$ . 由期望的线性性质, $$\mathbb{E}[\text{the number bad r-element subset of A }]<\left(\genfrac{}{}{0ex}{}{n}{r}\right){\left(\frac{m}{n}\right)}^t$$为了确保没有坏子集, 我们可以去掉每个坏子集中的一个元素. 剩余元素的个数至少为 $|A|$ 减去 $A$ 中元素个数为 $r$ 的坏子集的数量, 其期望值至少为$$n{\alpha }^t-\left(\genfrac{}{}{0ex}{}{n}{r}\right){\left(\frac{m}{n}\right)}^t\ge u$$

因此, 存在一个顶点序列 $T$, 使得在去掉所有坏的 $r$ 元素子集后, $A$ 中至少还剩下 $u$ 个元素. 剩下的 $u$ 个元素构成的集合 $U$ 满足所需的属性.

$\square$

将引理 9.2 的参数设置为证明定理 9.1 所需的参数, 我们得到以下推论.

推论 9.3. 对于任何顶点集为 $A\cup B$ 的二分图 $H$, 其中 $A$ 中的每个顶点的度数最多为 $r$, 存在 $C$ 使得以下结果成立: 每个至少有 ${Cn}^{2-\frac{1}{r}}$ 条边的图包含一个顶点子集 $U$ , $|U|=|B|$, 且 $U$ 中的每个元素个数为 $r$ 的子集至少有 $|A|+|B|$ 个共同邻点.

证明. 根据引理 9.2, $u=|B|,m=|A|+|B|,t=r$ , 只需检查是否存在 $C$, 使得$$n{\left(2C{n}^{-\frac{1}{r}}\right)}^r-\left(\genfrac{}{}{0ex}{}{n}{r}\right){\left(\frac{|A|+|B|}{n}\right)}^r\ge |B|$$第一项化简为 $(2C{)}^r$, 第二项化简为 $O_H(1)$. 因此我们可以选择足够大的 $C$ 来使这个不等式成立.

$\square$

现在我们准备证明定理 9.1.

定理 9.1.

令 $G$ 是一个至少有 ${Cn}^{2-\frac{1}{r}}$ 条边的 $n$ 顶点图, 其中 $C$ 是推论 9.3 的 $C$ . 首先, 使用推论 9.3 中的 $U$ 将 $B$ 嵌入到 $V(G)$ 中. 我们计划将这种嵌入进一步扩展到 $A\cup B\hookrightarrow V(G)$. 为此, 假设我们已经有一个嵌入 $\varphi :A^{\prime }\cup B\hookrightarrow V(G)$ , 其中 $A^{\prime }\subseteq A$ , 并且我们想要扩展 $\varphi$ 到任意 $v\in A\backslash A^{\prime }$. 我们必须确保 $\varphi (v)$ 是 $G$ 中 $\varphi (N(v))$ 的公共邻点. 注意到, 根据假设, $|\varphi (N(v))|=|N(v)|\le r$, 并且通过选择合适的 $B$, 集合 $\varphi (N(v))$ 至少有 $|A|+|B|$ 个共同邻点. $\varphi (v)$ 可以是这些公共邻点中的任何一个, 但不能与 $\varphi (u)$ 相同 ($\forall u\in A^{\prime }\cup B$) . 由于至少有 $|A|+|B|$ 个顶点可供选择, 我们可以通过将 $\varphi (v)$ 设置为其余可选顶点之一来扩展 $\varphi$. 通过这个过程, 我们可以将嵌入扩展到 $A\cup B\hookrightarrow V(G)$, 这说明 $G$ 中存在 $H$ 的副本.

$\square$

定理 9.1 是可以应用于所有二分图的一般性结论. 但是, 对于某些特定的二分图 $H$, 我们可能还有改进的余地. 例如, 通过这个定理我们知道的 $C_6$ 与 $C_4$ 的上界相同, 即 $O\left(n^{3/2}\right)$. 但这个上界并不紧.

定理 9.4 (Even cycles: Bondy and Simonovits 1974). 对于所有整数 $k\ge 2$, 存在一个常数 C 使得$$\mathrm{ex}\left(n,C_{2k}\right)\le C{n}^{1+\frac{1}{k}}$$

笔记 9.5. 目前已知当 $k=2,3,5$ 时, $\mathrm{ex}\left(n,C_{2k}\right)=\Theta \left(n^{1+1/k}\right)$ (Benson 1966) . 但是, 对于 $k$ 的其他值是否也是如此, 这问题开放的.

我们不准备证明这个定理而是关注一个弱一些的结论:

定理 9.6. 对于任何整数 $k\ge 2$, 都存在一个常数 $C$, 使得每个至少有 ${Cn}^{1+1/k}$ 条边的 $n$ 顶点图 $G$ 包含一个长度最多为 $2k$ 的偶数圈.

为了证明这个定理, 我们将首先对图进行 “清理”, 使得图的最小度足够大并且图是二分图. 下面两个引理允许我们专注于这些满足好性质的 $G$ 的子图.

引理 9.7. $t\in \mathbb{R}$ , 令 $G$ 是一个平均度数为 $2t$ 的图, 则 $G$ 包含一个最小度数大于 $t$ 的子图.

证明. 我们有 $e(G)=v(G)t$ . 删除度数小于等于 $t$ 的顶点不能降低平均度数. 我们可以继续删除度数小于等于 $t$ 的顶点, 直到每个顶点的度数都大于 $t$. 该算法一定在到达空子图之前终止, 否则平均度数不可能为 $2t$. 算法终止时剩余的子图就是最小度数大于 $t$ 的子图.

$\square$

引理 9.8. 每个 $G$ 都有一个二部子图, 该二分图至少有 $e(G)/2$ 条边.

证明. 用两种颜色中均匀随机地为每个顶点着色. 那么非单色边的期望值为 $e(G)/2$. 因此存在至少具有 $e(G)/2$ 非单色边的着色方案.

$\square$

定理 9.6.

假设 $G$ 不包含长度最多为 $2k$ 的偶数圈. 由引理 9.7 和引理 9.8 知, 存在一个最小度至少为 $\delta :=C{n}^{1/k}/2$ 二部子图 $G^{\prime }$. 令 $A_0=\{u\}$, 其中 $u\in V(G^{\prime })$. 令 $A_{i+1}=N_{G^{\prime }}\left(A_i\right)\backslash A_{i-1}$. $A_i$ 是一组顶点, 因为 $G^{\prime }$ 是二分图, 它们到起始顶点 $u$ 的距离正好为 $i$. (图 9)

(...) 定理 9.6 的证明示意图

$1\le i\le k$, 对于 $A_{i-1}$ 中两个不同的顶点 $v,v^{\prime }$ , 如果它们在 $A_i$ 中有一个共同的邻点 $w$, 那么从 $u$ 到 $w$ 有两条不同的最短路径. 两个不同路径的并集 (即使它们重叠) 包含一个长度最多为 $2i\le 2k$ 的偶数圈, 这与我们的假设矛盾. 因此 $A_{i-1}$ 中任意两个顶点的公共邻点只能在 $A_{i-2}$ 中, 这意味着 $\left|A_i\right|\ge (\delta -1)\left|A_{i-1}\right|$. 因此 $\left|A_k\right|\ge (\delta -1{)}^k\ge {\left(C{n}^{1/k}-1\right)}^k$. 如果选择的 $C$ 足够大, 就会有 $\left|A_k\right|>n$, 矛盾.

$\square$

如果 $H$ 是一个二分图, 顶点集 $A\cup B$ 且 $A$ 中每个顶点的度数最多为 2, 则 $\mathrm{ex}(n,H)=O\left(n^{3/2}\right)$. 指数 $3/2$ 是最优的, 因为 $\mathrm{ex}\left(n,K_{2,2}\right)=\Theta \left(n^{3/2}\right)$. 事实上, 只要 $H$ 不包含 $K_{2,2}$ 的任何副本, 我们就可以改进该指数.

定理 9.9 (Colon and Lee 2019+). 令 $H$ 是顶点集为 $A\cup B$ 的二分图且 $A$ 中的每个顶点的度数最多为 2, 并且 $H$ 不包含 $K_{2,2}$ . 则存在依赖于 $H$ 的 $c,C>0$ 满足$$\mathrm{ex}(n,H)\le C{n}^{\frac{3}{2}-c}$$

为了证明这个定理, 我们展示了一个使用细分 (subdivision) 概念表述的等效陈述. 对于图 $H$, $H$ 的 $1$ -细分 $H^{1\text{ -sub }}$ 是通过在 $H$ 的每条边的中间添加一个额外的顶点来获得的 (图 9) . 请注意, 定理 9.9 中的任一 $H$ 都是某个 $K_t^{1-\text{ sub }}$ 的子图, 因此我们可以考虑以下定理 9.9 的替代表述

定理 9.10 (Janzer 2018). 对于任意 $t\ge 3$, 存在 $c_t>0$ 使得$$\mathrm{ex}\left(n,K_t^{1-\text{sub}}\right)=O\left(n^{\frac{3}{2}-c_t}\right)$$

(...)1-subdivision of $K_4$

现在我们给出 Janzer 关于定理 9.10 的证明. 在定理 9.6 中, 将参数传递给子图是很有用的, 这帮助我们在在子图中能够更好地控制顶点的度数. 为此, 我们将使用以下引理 (省略证明) 来找到一个几乎正则的子图.

引理 9.11. 对于所有 $0<\alpha <1$, 存在常数 $\beta ,k>0$ 使得对于所有 $C>0$, 当 $n$ 足够大时, 每个边数大于等于 $C{n}^{1+\alpha }$ 的 $n$ 顶点图 $G$ 都有一个子图 $G^{\prime }$ 满足

1.	$v\left(G^{\prime }\right)\ge n^{\beta }$
2.	$e\left(G^{\prime }\right)\ge \frac{1}{10}Cv{\left(G^{\prime }\right)}^{1+\alpha }$
3.	$\max \mathrm{deg}\left(G^{\prime }\right)\le K\min \mathrm{deg}\left(G^{\prime }\right)$
4.	$G^{\prime }$ 是二分的, 且有两个顶点集的大小最多相差 $2$ .

从现在开始, 我们将 $t$ 视为一个常数. 对于任意两个顶点 $u,v\in$ $A$, 如果 $u$ 和 $v$ 的公共邻点数至少为 1 且小于 $\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ , 我们称点对 $uv$ 是轻的; 相反, 如果 $u$ 和 $v$ 的公共邻点数大于等于 $\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ , 我们称点对 $uv$ 是重的. 声明, $u,v$ 没有任何共同邻点时点对 $uv$ 既不轻也不重. 下面的引理给出了轻点对数量的下界.

引理 9.12. 令 $G$ 是一个顶点集为 $U\cup B$ 的 $K_t^{1-\text{sub}}$-free 二分图, 且对于所有 $x\in U$ 有 $d(x)\ge \delta$ , 并且满足 $|U|\ge 4|B|t/\delta$. 那么存在 $u\in U$ , 出现在 $U$ 中 $\Omega \left({\delta }^2|U|/|B|\right)$ 个轻点对中.

证明. 令 $S$ 是 $\{(\{u,v\},x)\mid u,v\in U,x\in B\}$ 的集合, 其中 $\{u,v\}$ 是 $U$ 中的无序点对, $x$ 是 $\{u,v\}$ 的公共邻点. 首先, 我们通过选择 $x\in B$ 来计算: $$|S|=\sum _{x\in B}\left(\genfrac{}{}{0ex}{}{d(x)}{2}\right)\ge |B|\left(\genfrac{}{}{0ex}{}{e(G)/|B|}{2}\right)\ge \frac{|B|}{4}{\left(\frac{\delta |U|}{|B|}\right)}^2=\frac{{\delta }^2|U{|}^2}{4|B|}$$请注意, $B$ 中的低度顶点贡献很小, 因为$$\sum _{\genfrac{}{}{0ex}{}{x\in B}{d(x)<2t}}\left(\genfrac{}{}{0ex}{}{d(x)}{2}\right)\le 2t^2|B|\le \frac{{\delta }^2|U{|}^2}{8|B|}$$因此$$\sum _{\genfrac{}{}{0ex}{}{x\in B}{d(x)\ge 2t}}\left(\genfrac{}{}{0ex}{}{d(x)}{2}\right)\ge \frac{{\delta }^2|U{|}^2}{8|B|}$$

注意, 如果 $U$ 中有 $t$ 个互相之间是重点对的顶点, 那么我们可以为每对 $\left\{v_i,v_j\right\}$ 选择一个共同的邻点 $u_{ij}$ , 在这里 $i<j$. 由于每一对 $\left\{v_i,v_j\right\}$ 至少有 $\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ 个这样的邻点, 所以我们选择所有的 $u_{ij}$ 可以是不同的. 这会产生一个 $K_t^{1-\text{ sub }}$ 子图, 矛盾. 因此 $U$ 中不存在 $t$ 个互相之间是重点对的点, 根据图兰定理, $x\in B$, $N(x)$ 中的重点对的数目至多为 $e\left(T_{d(x),t-1}\right)$. 这是因为 $N(x)$ 中的任何两个顶点至少有一个共同的邻点 $x$, 它们要么形成轻点对或重点对. 这表明在 $N(x)$ 中至少有 $\left(\genfrac{}{}{0ex}{}{d(x)}{2}\right)-e\left(T_{d(x),t-1}\right)$ 个轻点对. 如果 $d(x)\ge 2t$, 则有$$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{d(x)}{2}\right)-e\left(T_{d(x),t-1}\right)& \ge \left(\genfrac{}{}{0ex}{}{d(x)}{2}\right)-\left(\genfrac{}{}{0ex}{}{t-1}{2}\right){\left(\frac{d(x)}{t-1}\right)}^2\\ & =\frac{1}{2(t-1)}d(x{)}^2-\frac{1}{2}d(x)\\ & \gtrsim d(x{)}^2\end{array}$$

如果我们对所有 $x\in B$ 求和, 根据定义, 那么每个轻点对最多只会被计算 $\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ 次. 因为我们将 $t$ 视为常数所以 $\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ 是常数. 因此$$\text{ \#light pairs in }U\gtrsim \sum _{x\in B}d(x{)}^2\gtrsim |S|\gtrsim \frac{{\delta }^2|U{|}^2}{|B|}$$并且根据鸽巢原理, 存在一个顶点 $u\in U$ 在 $\Omega \left({\delta }^2|U|/|B|\right)$ 个轻点对中.

$\square$

有了这些引理, 我们准备来证明定理 9.10.

定理 9.10.

令 $G$ 是任意 $K_t^{1-\text{ sub }}$ -free 图. 首先选择 $\alpha =(t-2)/(2t-3)$ 时引理 9.11 中的 $G^{\prime }$ , 两个部分分别记作 $A$ 和 $B$. 设 $\delta$ 为 $G^{\prime }$ 的最小度数. 我们将反证法证明 $\delta \le Cv{\left(G^{\prime }\right)}^{(t-2)/(2t-3)}$ . 假设 $\delta >Cv{\left(G^{\prime }\right)}^{(t-2)/(2t-3)}$. 我们的计划是选择这样的 $v_1,v_2,\dots ,v_t$ : 对于所有 $i<j$ , $v_i{v}_j$ 都是轻的, 并且 $v_1,\dots ,v_t$ 的任意三个没有共同的邻点. 这会给我们带来一个 $K_t^{1\text{ -sub }}$ , 从而矛盾.

我们将通过重复使用引理 9.12 并介绍一个更强的假设来做到这一点: 对于任意 $1\le i\le t$, 存在 $A=U_1\supseteq U_2\supseteq \cdots \supseteq U_i$ 和 $v_j\in U_j$ 使得

1.	对于所有 $1\le j\le$ $i-1$ , $v_j$ 至少在 $U_j$ 中 $\Theta \left({\delta }^2\left|U_j\right|/v\left(G^{\prime }\right)\right)$ 个轻点对中.
2.	对于所有 $1\le j\le i-1$, $v_j$ 对 $U_{j+1}$ 中的所有顶点都是轻的.
3.	$v_1,\dots ,v_i$ 中任意三个没有共同邻点.
4.	对于所有 $1\le j\le i-1$, $\left|U_{j+1}\right|\gtrsim {\delta }^2\left|U_j\right|/v\left(G^{\prime }\right)$ 成立.

当 $i=1$ 时, 根据引理 9.12, 可以找到 $v_1$ 作为所需的顶点. 现在假设我们已经构造出了 $A=U_1\supseteq \cdots \supseteq U_{i-1}$ 与 $v_j\in U_j$ , $j=1,\dots ,i-1$. 为了构造 $U_i$, 令 $U_i^{\prime }$ 是与 $v_{i-1}$ 形成轻点对的顶点集. 然后由归纳假设 (a) 我们有 $\left|U_i^{\prime }\right|\gtrsim {\delta }^2\left|U_{i-1}\right|/v\left(G^{\prime }\right)$ . 现在我们去掉 $U_i^{\prime }$ 中所有违反 $(\mathrm{c})$ 的顶点得到 $U_i$. 检查每一对 $v_j{v}_k$, 查看它们的共同点 $u$, 从 $U_i^{\prime }$ 中删除 $u$ 的所有邻点. $U_i^{\prime }$ 中一共有 $\left(\genfrac{}{}{0ex}{}{i-1}{2}\right)$ 个 $v_j{v}_k$, 它们最多有 $\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ 公共邻点 (因为它们形成一个轻点对) , 并且每个这样的邻点的度数最多为 $K\delta$. 因此移除的顶点数最多为$$\left(\genfrac{}{}{0ex}{}{i-1}{2}\right)\left(\genfrac{}{}{0ex}{}{t}{2}\right)K\delta =O(\delta )$$

因为 $t$ 和 $K$ 是常数. 因此, 在进行修改之后, 只要 $C$ 选择得足够大且等式 $\left|U_i^{\prime }\right|=\Omega (\delta )$ 继续成立, (d) 就仍然成立. (d) 确实仍然成立, 因为$$\left|U_i^{\prime }\right|\gtrsim {\left(\frac{{\delta }^2}{V\left(G^{\prime }\right)}\right)}^{i-1}|A|\gtrsim {\delta }^{2t-2}V{\left(G^{\prime }\right)}^{t-2}=\Theta (\delta )$$当 $i\le t$ 时成立. 因此 (d) 对 $i$ 成立, 我们只需要根据引理 9.12 从 $U_i$ 选择出顶点 $v_i$, $(\mathrm{a}),(\mathrm{b}),(\mathrm{c})$ 直接自动满足. 因此, 通过归纳, 这也适用于 $i=t$. 现在通过 $(\mathrm{b})$ 和 $(\mathrm{c})$, 在 $G^{\prime }$ 中存在 $K_t^{1-\mathrm{sub}}$ 的副本, 矛盾.

上面的论证表明 $\delta \le Cv{\left(G^{\prime }\right)}^{(t-2)/(2t-3)}$, 所以最大度数最多为 $KCv{\left(G^{\prime }\right)}^{(t-2)/(2t-3)}$. 因此 $e\left(G^{\prime }\right)\le$ $KCv{\left(G^{\prime }\right)}^{1+\alpha }$, 假设我们有 $e(G)>10KC{n}^{1+\alpha }$ , 根据引理 9.11 $(\mathrm{c})$ 得到的结果与 $e\left(G^{\prime }\right)\le$ $KCv{\left(G^{\prime }\right)}^{1+\alpha }$ 矛盾. 所以有 $e(G)\le 10KC{n}^{1+\alpha }$ , 这是我们想要的.

(...) 重复利用引理 9.10 得到 $v_i$ 和 $U_i$

$\square$