6. 下界: 随机构造

我们推测定理 5.2 的上界是紧的. 换句话说, $\mathrm{ex}\left(n,K_{s,t}\right)=\Theta \left(n^{2-1/s}\right)$. 尽管对于任意的 $K_{s,t}$ 问题仍然是开放的, 但它已经在一些 $t$ 远大于 $s$ 的案例中得到了证明. 在本节和接下来的两节中, 我们将展示构造 $H$-free 图的技术. 以下是我们将介绍的三种主要结构类型:

•	随机构造. 这种方法强大且通用, 但引入随机性意味着构造得到的界通常是不紧的.
•	代数构造. 这种方法使用数论或代数中的工具来辅助构造. 它给出了更紧的结果, 但它们通常是 “奇妙的” 并且只适用于一小部分情况.
•	随机代数构造. 这种方法是上述两种方法的混合, 结合了两者的优点.

本节将重点介绍随机结构. 我们从极值的一般下界开始.

定理 6.1. 对于任何至少有 2 条边的图 $H$ , 令 $e(H)$ 为 $H$ 的边数, $v(H)$ 为 $H$ 的点数, 存在一个常数 $c>0$, 使得对于任意 $n\in \mathbb{N}$, 存在具有至少 ${cn}^{2-\frac{v(H)-2}{e(H)-1}}$ 条边的 $n$ 顶点 $H$-free 图. 换句话说, $$\mathrm{ex}(n,H)\ge c{n}^{2-\frac{v(H)-1}{e(H)-2}}.$$

证明. 证明的想法是使用调整法 (alteration method): 我们可以构建一个图使其与 $H$ 同构的子图很少, 然后我们在每个这样的子图中删除一条边, 从而消除其中所有 $H$.

令 $G=G(n,p)$ 为 $n$ 顶点的随机图, 其中任意两点间存在边的概率为 $p$ ($p$ 待定) ¹. 令 $\#H$ 为 $G$ 中与 $H$ 同构的子图个数. 那么, $$\mathbb{E}[\#H]=\frac{n(n-1)\cdots (n-v(H)+1)}{|\mathrm{Aut}(H)|}{p}^{e(H)}\le p^{e(H)}{n}^{v(H)},$$其中 $\mathrm{Aut}(H)$ 是图 $H$ 的自同构群 ², 并且$$\mathbb{E}[e(G)]=p\left(\genfrac{}{}{0ex}{}{n}{2}\right).$$令 $p=\frac{1}{2}{n}^{-\frac{v(H)-2}{e(H)-1}}$, 此时满足$$\mathbb{E}[\#H]\le \frac{1}{2}\mathbb{E}[e(G)].$$进一步有$$\mathbb{E}[e(G)-\#H]\ge \frac{1}{2}p\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge \frac{1}{16}{n}^{2-\frac{v(H)-2}{e(H)-1}}.$$因此, 存在一个图 $G$, 使得 $(e(G)-\#H)$ 的值至少是期望值. 从 $G$ 中 $H$ 的每个副本中删除一条边, 我们得到一个满足条件的 $H$-free 图.

$\square$

笔记 6.2. 例如, 如果 $H$ 是下图

根据定理 6.1 我们有$$\mathrm{ex}(n,H)\gtrsim n^{11/7}.$$但是, 如果我们禁止 $H$ 的子图 $K_4$ (禁止 $H$ 的子图将自动禁止图 $H$) , 定理 6.1 实际上给了我们一个更好的下界: $$\mathrm{ex}(n,H)\ge \mathrm{ex}\left(n,K_4\right)\gtrsim n^{8/5}.$$对于一般的 $H$, 我们将定理 6.1 应用于使 $(e-1)/(v-2)$ 取值最大的子图. 为此, 我们定义 $H$ 的 2-密度$$m_2(H):=\underset{\begin{array}{c}{H}^{\prime }\subset H\\ v(H^{\prime })\ge 3\end{array}}{\max }\frac{e(H^{\prime })-1}{v(H^{\prime })-2}.$$我们有以下推论.

推论 6.3. 对于任何具有至少两条边的图 $H$, 存在常数 $c=c_H>0$ 使得$$\mathrm{ex}(n,H)\ge c{n}^{2-1/m_2(H)}.$$

例 6.4. 我们将上述下界与 Kóvári-Sós-Turán 定理 (定理 5.2) 的上界结合, 得到: 对于任意的 $2\le s\le t$, $$n^{2-\frac{s+t-2}{st-1}}\lesssim \mathrm{ex}\left(n,K_{s,t}\right)\lesssim n^{2-1/s}.$$当 $t$ 远大于 $s$ 时, 上述两个边界中的指数彼此接近 (但永远不会相等) . 当 $t=s$ 时, 有不等式$$n^{2-\frac{2}{s+1}}\lesssim n^{2-\frac{s+t-2}{st-1}}\lesssim n^{2-1/s}.$$特别地, 对于 $s=2$, 我们得到$$n^{4/3}\lesssim \mathrm{ex}\left(n,K_{2,2}\right)\lesssim n^{3/2}$$事实上, 这里的上界是比较紧的. 我们将用一个基于代数方法的 $K_{2,2}$-free 图构造来说明这一点.

1.	^ $G(n,p)$ 对应的随机图模型叫做 Erdős–Rényi 随机图.
2.	^ 一个图的自同构是顶点集上的一个置换, 使得边与非边保持不变: 两个顶点若有边连接, 则在置换下这两顶点的像有边连接, 反之亦然.