5. Kovári–Sós–Turán 定理: 禁止完全二分图

Erdős-Stone-Simonovits 定理 (定理 4.4) 给出了当 $\chi (H)>2$ 时 $\mathrm{ex}(n,H)$ 的一阶近似. 不幸的是, 定理 4.4 还并不完整. 例如当 $\chi (H)=2$ 时, 也就是 $H$ 是二分图时, 定理 4.4 告诉我们 $\mathrm{ex}(n,H)=o\left(n^2\right)$, 这就迫使我们询问是否可以获得更精确的界限? 如果我们将 ex $(n,H)$ 写成 $n$ 的函数, 它相对于 $n$ 的增长是怎样的? 对于大多数二分图 (例如, $K_{4,4}$ ) 这是一个未完全解决的问题, 也是本章其余部分的重点.

令 $K_{s,t}$ 是完全二分图, 其中二分图的两部分分别有 $s$ 个点和 $t$ 个点. 在本节中, 我们考虑 $\mathrm{ex}\left(n,K_{s,t}\right)$, 并试图回答以下主要问题:

问题 5.1 (Zarankiewicz). 对于 $s,t\ge 1$, 不包含子图 $K_{s,t}$ 的 $n$ 顶点图的最大边数是多少?

每个二分图 $H$ 都是某个完全二分图 $K_{s,t}$ 的子图. 如果 $H\subseteq K_{s,t}$, 那么 $\mathrm{ex}(n,H)\le \mathrm{ex}\left(n,K_{s,t}\right)$. 因此, 如果得到了禁止完全二分图的极值的上界, 那么它也是禁止一般二分图的极值的一个上界. 稍后我们将给出几个禁止特定二分图的改进上界. Kövári、Sós 和 Turán 给出了禁止 $K_{s,t}$ 时的上限:

定理 5.2 (Kövári-Sós-Turán 1954). 对于任意整数 $1\le s\le t$, 都存在常数 $C$, 使得$$\mathrm{ex}\left(n,K_{s,t}\right)\le C{n}^{2-\frac{1}{s}}$$

证明. 令 $G$ 是一个 $K_{s,t}$-free 的 $n$ 顶点 $m$ 边图.

首先, 我们删除所有 $d(v)<s-1$ 的顶点 $v\in V(G)$. 由于我们以这种方式最多只删除 $(s-2)n$ 条边 (阶数为 1, 小于 $2-\frac{1}{s}$) , 因此假设所有顶点的度数至少为 $s-1$ 对该命题没有影响.

我们将 $G$ 中 $K_{s,1}$ 的数量记作 $\#K_{s,1}$. 我们用算两次的方法, 以两个方式分别给出 $\#K_{s,1}$ 的上界和下界, 然后结合上界和下界得到 $m$ 的上界. ¹

由于 $K_{s,1}$ 是一个完整的二分图, 我们可以将有 $s$ 个顶点的一侧称为 “左侧”, 将有 1 个顶点的一侧称为 “右侧”.

一方面, 我们可以通过枚举 “左侧” 计算 $\#K_{s,1}$ . 对于任何 $s$ 个顶点的子集, 以这 $s$ 个顶点作为 “左侧” 的 $K_{s,1}$ 的数量正是这 $s$ 个顶点的公共邻点的数量. 由于 $G$ 是 $K_{s,t}$-free 的, $s$ 个顶点的任何子集的公共邻点数最多为 $t-1$. 因此, 我们有 $\#K_{s,1}\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)(t-1)$.

另一方面, 对于每个 “右侧” 顶点 $v\in V(G)$, $K_{s,1}$ 的数量正好是 $\left(\genfrac{}{}{0ex}{}{d(v)}{s}\right)$. 因此$$\#K_{s,1}=\sum _{v\in V(G)}\left(\genfrac{}{}{0ex}{}{d(v)}{s}\right)\ge n\left(\genfrac{}{}{0ex}{}{\frac{1}{n}{\sum }_{v\in V(G)}d(v)}{s}\right)=n\left(\genfrac{}{}{0ex}{}{2m/n}{s}\right)$$其中不等号成立是因为 $x\mapsto \left(\genfrac{}{}{0ex}{}{x}{s}\right)$ 在 $[s-1,+\infty )$ 上的凸性. 结合 $\#K_{s,1}$ 的上界和下界, 我们得到 $n\left(\genfrac{}{}{0ex}{}{2m/n}{s}\right)\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)(t-1)$. 对于常量 $s$, 我们可以使用 $\left(\genfrac{}{}{0ex}{}{x}{s}\right)=(1+$ $o(1))\frac{n^s}{s!}$ , 从而得到 $n{\left(\frac{2m}{n}\right)}^s\le (1+o(1))n^s(t-1)$. 该不等式简化为$$m\le \left(\frac{1}{2}+o(1)\right)(t-1{)}^{1/s}{n}^{2-\frac{1}{s}}$$

$\square$

现在让我们讨论定理 5.2 在几何上的应用.

问题 5.3 ((单位距离问题)). ${\mathbb{R}}^2$ 上的 $n$ 个点中, 最多有多少对点之间距离为 $1$?

给定 $n$ 个点, 我们将距离为 $1$ 的点对个数称为单位距离数.

当 $n$ 取较小的值, 我们精确地知道单位距离问题的答案. 图 5 列出了最佳方案. 可以将这些结构中的一些推广到任意 $n$.

•	直线图 2的单位距离数是 $(n-1)$ .
•	对于 $n\ge 3$, 三角形链的单位距离数是 $(2n-3)$ (图 5 中 $n=3$、$n=5$) .
•	我们还有一个递归构造. 给定 $n/2$ 个点的方案 $P$ 具有 $f(n/2)$ 单位距离, 我们可以复制 $P$ 得到 $P^{\prime }$ 并用单位向量与其连接. 方案 $P\cup P^{\prime }$ 至少有 $2f(n/2)+n/2$ 对单位距离. 我们可以求解递归得到 $f(n)=\Omega (n\log n)$.

(...) 注: 除了 $n=6$, 这些构造在同构前是唯一的

Erdős 给出了已知最大单位距离数的最佳下界 (1946) .

命题 5.4. 在 ${\mathbb{R}}^2$ 中存在一组点 ($n$ 个) , 对于某个常数 $c$, 它们的单位距离数是 $n^{1+c/\log \log n}$ .

概要.

考虑具有 $\lfloor \sqrt{n}\rfloor \times \lfloor \sqrt{n}\rfloor$ 顶点的单位方形网格. 对于任意整数 $r$, 我们可以都可以把图形缩小 $\sqrt{r}$ 倍, 所以我们只要最大化距离为 $\sqrt{r}$ 的点对数量即可. 由勾股定理, 我们应该选择可以多种不同的方式表示为两个平方的和的 $r$. $r$ 的一个合适候选是许多模 $4$ 余 $1$ 的素数的乘积. 我们可以使用一些数论定理来分析最佳的 $r$, 并得到下界 $n^{1+c/\log \log n}$ .

$\square$

(...)An example grid graph where n = 25 and r = 10.

定理 5.2 可用于证明单位距离数的上限.

定理 5.5. ${\mathbb{R}}^2$ 中的每组点 ($n$ 个) 单位距离数最多为 $O\left(n^{3/2}\right)$ .

证明. 给定任意一组点 $S\subset {\mathbb{R}}^2$, 我们可以创建单位距离图 $G$ 如下:

•	$G$ 的顶点集是 $S$.
•	对于任意 $d(p,q)=1$ 的点 $p,q$, 我们在 $p$ 和 $q$ 之间添加一条边.

因为对于每对点 $p,q$, 至多有 2 个点与它们都有单位距离 (见图 5) , 所以图 $G$ 是 $K_{2,3}$-free 的. 通过应用定理 5.2, 我们得到 $e(G)=O\left(n^{3/2}\right)$.

$\square$

(...) 单位距离图中顶点 $p$, $q$ 最多有两个共同邻点

笔记 5.6. 最著名的单位距离数上界是 $O\left(n^{4/3}\right)$ (Spencer, Szemerédi and Trotter 1984) .

下面是另一个与单位距离问题密切相关的问题:

问题 5.7 ((不同距离问题)). 由 ${\mathbb{R}}^2$ 中的 $n$ 个点形成的不同距离的最少有多少种?

例 5.8. 考虑 $x$ 轴上的 $n$ 个点, 其中第 $i$ 个点的坐标为 $(i,0)$, 这些点的不同距离的数量是 $n-1$.

目前最小不同距离的最佳构造也是由网格图给出的. 考虑具有 $\lfloor \sqrt{n}\rfloor \times$ $\lfloor \sqrt{n}\rfloor$ 顶点的方形网格. 两个顶点之间可能的距离是可以表示为两个最多为 $\lfloor \sqrt{n}\rfloor$ 的数的平方和. 借助数论的知识, 我们可以得到不同距离数是 $\Theta (n/\sqrt{\log n})$ 的. 注意到, 不同距离数和单位距离数之间有以下关系: $$\text{ \#distinct distances }\ge \frac{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}{\text{ max \#unit distances }}$$如果我们将定理 5.5 应用于上述不等式, 我们立即得到不同距离数的下界 $\Omega \left(n^{0.5}\right)$ . 许多数学家在七年的时间里相继改进了这个下界的指数. 最近, Guth 和 Katz 给出了下面这个著名的定理, 它几乎与上界相匹配 (仅相差 $O\left(\sqrt{\log n}\right)$ ) .

定理 5.9 (Guth-Katz 2015). ${\mathbb{R}}^2$ 中的任意组点 ($n$ 个) , 对于某些常数 $c$, 至少有 $cn/\log n$ 个不同的距离.

定理 5.9 的证明非常复杂, 它使用了包括多项式方法、代数几何等各种工具, 我们不会在本书中介绍它 ³.

1.	^ 译者注: 证明的思想如下, 我们希望证明图中的边数不会太多, 如果边数太多那么每个点度数都会比较大, 从而会有很多子图 $K_{s,1}$ 以这个点作为 “右侧”. 而因为禁止了 $K_{s,t}$, $G$ 中的的子图 $K_{s,1}$ 不能太多, 这是因为以任意 $s$ 个点作为 “左侧”, 都最多会有 $t-1$ 个这样的子图. 从而就证明了图中的边数不能太多.
2.	^ 即第 $i$ 个点的坐标是 $(i,0)$
3.	^ 译者注: Terry Tao 有一篇博客介绍了这个证明的基本思路. https://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/