1. 拟随机图

接下来, 我们将介绍一个这个领域非常根本的定理, 它列出了图可以具有的许多伪随机性质. 这些性质看上去两两不同 (有些看似很好验证, 有些看似很难) , 但这个定理却告诉我们, 这些性质全都等价.

定理 1.1 (Chung, Graham, and Wilson (1989)). 令序列 $\{G_n\}$ 是一个图的序列, 其中每个 $G_n$ 都是 $n$ 个点, $(p+o(1))\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 个边的图 (固定一个常数 $0<p<1$) . 我们把 $G_n$ 简写为 $G$. 以下的性质全部是等价的:

1.	$\mathbf{DISC}$ (“discrepancy”) : 对于任意 $X,Y\subset V(G)$, $|e(X,Y)-p|X||Y||=o(n^2)$.
2.	$\mathbf{DIS}{\mathbf{C}}^{\prime }$ : 对于任意 $X\subset V(G)$, $\left|e(X)-p\left(\genfrac{}{}{0ex}{}{|X|}{2}\right)\right|=o(n^2)$.
3.	$\mathbf{COUNT}$ : 对于任意的图 $H$, $H$ 在 $G$ 里 带标号 (也就是说 $H$ 里不同的点看作是有区别的) 地出现了 $(p^{e(H)}+o(1))n^{v(H)}$ 次. 其中低阶项 $o(1)$ 只与 $H$ 有关.
4.	${\mathbf{C}}_4$ : $C_4$ 在 $G$ 里 带标号地出现了至多 $(p^4+o(1))n^4$ 次.
5.	$\mathbf{CODEG}$ (codegree) : 令 $\mathrm{codeg}(u,v)$ 表示 $u$ 和 $v$ 的公共邻居数, 那么 ${\sum }_{u,v\in V(G)}|\mathrm{codeg}(u,v)-p^{2}n|=o(n^3)$.
6.	$\mathbf{EIG}$ (eigenvalue) : 假设图 $G$ 的邻接矩阵的特征值是 ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{v(G)}$, 那么 ${\lambda }_1=pn+o(n)$ 并且 ${\max }_{i\ne 1}|{\lambda }_i|=o(n)$.

注 1.2. 特别的, 对于 $d$-正则图, 最大的特征值就是 $d$ (对应的特征向量就是全 1 向量), $\mathbf{EIG}$ 在 $d$-正则图上相当于说 ${\lambda }_2=o(n)$.

我们可以等价地以 $ϵ$ 语言来叙述这些性质, 比如说 $\mathbf{DISC}$ 可以写成这样: $$\mathbf{DISC}(ϵ):\forall X,Y\subset V(G),|e(X,Y)-p|X||Y||<ϵn^2.$$

我们将会从定理 1.1 的证明中看到, 这些性质全部都在关于 $ϵ$ 的多项式意义下等价, 也就是说, 对于任意两个性质 $Prop1$ 与 $Prop2$, 都存在一个常数 $c$, 使得 $Prop1(ϵ)⟹Prop2({ϵ}^c)$.

在这个定理的证明中, 我们会多次用到 Cauchy–Schwarz 不等式, 所以我们不如从它的一个小练习开始.

引理 1.3. 如果 $G$ 是一个 $n$ 个点的图, 并且 $e(G)\ge p{n}^2/2$, 那么在 $G$ 中 $C_4$ 带标号地出现了 $\ge (p^4-o(1))n^4$ 次.

证明. 这里我们想要的是 $S=\mathrm{Hom}(C_4,G)$ 的大小, 也就是从 $C_4$ 到 $G$ 的图同态的个数. 这里 $S$ 把不是单射的映射也包括在内, 也就是说 $C_4$ 里不同的点可以被映射到 $G$ 中的同一个点. 但这不影响我们的结论, 因为反正这种映射最多也只有 $O(n^3)$ 个.

固定 $C_4$ 的对角线在 $G$ 中的两个端点 $u$ 和 $v$, 分别考虑对角线上下对称的两部分 (见图 ??) , 我们可以发现, $|S|={\sum }_{u,v}\mathrm{codeg}(u,v{)}^2$. 我们应用两次 Cauchy–Schwarz 不等式就可以得到$$\begin{array}{rl}\left|\mathrm{Hom}\left(C_4,G\right)\right|& =\sum _{u,v\in V(G)}\mathrm{codeg}(u,v{)}^2\\ & \ge \frac{1}{n^2}{\left(\sum _{u,v\in V(G)}\mathrm{codeg}(u,v)\right)}^2\\ & =\frac{1}{n^2}{\left(\sum _{x\in V(G)}\mathrm{deg}(x{)}^2\right)}^2\\ & \ge \frac{1}{n^2}{\left(\frac{1}{n}{\left(\sum _{x\in V(G)}\mathrm{deg}(x)\right)}^2\right)}^2\\ & =\frac{1}{n^2}{\left(\frac{1}{n}{\left(p{n}^2\right)}^2\right)}^2\\ & =p^4{n}^4\end{array}$$

其中第二行, 我们对长度为 $2$ 的路径的条数用 “算两次” 的办法, 得到了 ${\sum }_{u,v\in V(G)}\mathrm{codeg}(u,v)={\sum }_{x\in V(G)}\mathrm{deg}(x{)}^2$.

注 1.4. 我们可以可视化的展示两次应用 Cauchy–Schwarz 的过程, 见图 ??. 我们可以发现 Cauchy–Schwarz 其实是利用了图的对称性. ¹

(...) Cauchy–Schwarz 的可视化

$\square$

接下来我们来证明定理 1.1.

证明. $\mathbf{DISC}⟹\mathbf{DIS}{\mathbf{C}}^{\prime }$: 在 $\mathbf{DISC}$ 中, 令 $Y=X$.

$\mathbf{DIS}{\mathbf{C}}^{\prime }⟹\mathbf{DISC}$: 我们把在 $e(X,Y)$ 中的边分类, 应用容斥原理把它表示出来:

$$e(X,Y)=e(X\cup Y)+e(X\cap Y)-e(X\setminus Y)-e(Y\setminus X).$$

这样我们就可以用 $\mathbf{DISC}$ 得到: $$\begin{array}{rl}& p\left(\left(\begin{array}{c}|X\cup Y|\\ 2\end{array}\right)+\left(\begin{array}{c}|X\cap Y|\\ 2\end{array}\right)+\left(\begin{array}{c}|X\setminus Y|\\ 2\end{array}\right)+\left(\begin{array}{c}|Y\setminus X|\\ 2\end{array}\right)+o(n^2)\right)\\ =& p|X||Y|+o(n^2)\end{array}$$

$\mathbf{DISC}⟹\mathbf{COUNT}$: 在图计数引理 (定理 5.0.3) 中, 令 $V_i=G$ ($i=1,\dots ,v(H)$), 就可以直接得到这个结论.

$\mathbf{COUNT}⟹{\mathbf{C}}_4$: ${\mathbf{C}}_4$ 只是 $\mathbf{COUNT}$ 的一个特殊情况.

${\mathbf{C}}_4⟹\mathbf{CODEG}$: 假设 ${\mathbf{C}}_4$ 成立, 我们有$$\sum _{u,v\in G}\mathrm{codeg}(u,v)=\sum _{x\in G}\mathrm{deg}(x{)}^2\ge n{\left(\frac{2e(G)}{n}\right)}^2=\left(p^2+o(1)\right)n^3.$$

与此同时 ${\sum }_{u,v}\mathrm{codeg}(u,v{)}^2$ 等于 $C_4$ 有标号地在 $G$ 中出现的次数, 也就是: $$\begin{array}{rl}\sum _{u,v}\mathrm{codeg}(u,v{)}^2& =\text{ Number of labeled copies of }{C}_4+o(n^4)\\ & \le \left(p^4+o(1)\right)n^4\end{array}$$

从而我们可以用 Cauchy-Schwartz 来得到我们想要的: $$\begin{array}{rl}\sum _{u,v\in G}\left|\mathrm{codeg}(u,v)-p^{2}n\right|& \le n{\left(\sum _{u,v\in G}{\left(\mathrm{codeg}(u,v)-p^{2}n\right)}^2\right)}^{1/2}\\ & =n{\left(\sum _{u,v\in G}\mathrm{codeg}(u,v{)}^2-2p^{2}n\sum _{u,v\in G}\mathrm{codeg}(u,v)+p^4{n}^4\right)}^{1/2}\\ & \le n{\left(p^4{n}^4-2p^{2}n\cdot p^2{n}^3+p^4{n}^4+o(n^4)\right)}^{1/2}\\ & =o(n^3)\end{array}$$

注 1.5. 这个技巧类似于概率组合 (probabilistic combinatorics) 里的二阶矩方法: 我们希望证明 $\mathrm{codeg}(u,v)$ 的方差不会太大. ²

$\mathbf{CODEG}⟹\mathbf{DISC}$: 我们首先注意到$$\begin{array}{rl}\sum _{u\in G}|\mathrm{deg}(u)-pn|& \le n^{1/2}{\left(\sum _{u\in G}(\mathrm{deg}(u)-pn{)}^2\right)}^{1/2}\\ & =n^{1/2}{\left(\sum _{u\in G}(\mathrm{deg}(u){)}^2-2pn\sum _{u\in G}\mathrm{deg}(u)+p^2{n}^3\right)}^{1/2}\\ & =n^{1/2}{\left(\sum _{u,v\in G}\mathrm{codeg}(u,v)-4pn\cdot e(G)+p^2{n}^3\right)}^{1/2}\\ & =n^{1/2}{\left(p^2{n}^3-2p^2{n}^3+p^2{n}^3+o(n^3)\right)}^{1/2}\\ & =o(n^2).\end{array}$$

从而有

$$\begin{array}{rl}|e(X,Y)-p|X||Y||& =\left|\sum _{x\in X}(\mathrm{deg}(x,Y)-p|Y|)\right|\\ & \le n^{1/2}{\left(\sum _{x\in X}(\mathrm{deg}(x,Y)-p|Y|{)}^2\right)}^{1/2}.\end{array}$$

因为求和的每一项都是非负的, 我们可以把求和范围从 $X$ 扩大到 $V(G)$, 从而得到: $$\begin{array}{rl}|e(X,Y)-p|X||Y||& \le n^{1/2}{\left(\sum _{x\in V(G)}\mathrm{deg}(x,Y{)}^2-2p|Y|\sum _{x\in V(G)}\mathrm{deg}(x,Y)+p^{2}n|Y{|}^2\right)}^{1/2}\\ & =n^{1/2}{\left(\sum _{y,y^{\prime }\in Y}\mathrm{codeg}\left(y,y^{\prime }\right)-2p|Y|\sum _{y\in Y}\mathrm{deg}(y)+p^{2}n|Y{|}^2\right)}^{1/2}\\ & =n^{1/2}{\left(|Y{|}^2{p}^{2}n-2p|Y|\cdot |Y|pn+p^{2}n|Y{|}^2+o(n^3)\right)}^{1/2}\\ & =o(n^2).\end{array}$$

现在我们已经证明了这些定理间的一个 “$C_4$”, $\mathbf{DISC}⟹\mathbf{COUNT}⟹{\mathbf{C}}_4⟹\mathbf{CODEG}⟹\mathbf{DISC}$, 我们最后证明 $\mathbf{EIG}$ 与 ${\mathbf{C}}_4$ 的等价性.

$\mathbf{EIG}⟹{\mathbf{C}}_4$: $C_4$ 在 $G$ 中的带标号出现次数与长度为 $4$ 的封闭路径的个数, 最多只相差 $O(n^3)$, 而长度为 $4$ 的封闭路径个数等于 $\mathrm{tr}(A_G^4)$ (这里 $A_G$ 是图 $G$ 的邻接矩阵) . 由线性代数我们知道, $\mathrm{tr}(A_G^4)={\sum }_{i=1}^n{\lambda }_i^4$. 其中最大的一项是 ${\lambda }_i^4$, 而根据我们的假设, ${\lambda }_1^4=p^4{n}^4+o(n^4)$. 那么接下来, 我们就是要证明其它 ${\lambda }_i^4$ 的和不会太大, 如果你把它们分开一个一个 bound, 你会得到一个 $o(n^5)$ 的误差项 (这太大了! ) . 所以我们放在一起 bound, 我们有$$\sum _{i\ge 2}{\lambda }_i^4\le \underset{i\ne 2}{\max }{\left|{\lambda }_i\right|}^2\sum _{i\ge 1}{\lambda }_i^2$$注意到 ${\sum }_{i\ge 1}{\lambda }_i^2=\mathrm{tr}(A_G^2)=2e(G)$, 从而$$\sum _{i=1}^n{\lambda }_i^4=p^4{n}^4+o(n^4)+o(n^2)n^2=p^4{n}^4+o(n^4).$$${\mathbf{C}}_4⟹\mathbf{EIG}$: 我们要用 Courant-Fischer 定理 (也叫极大极小定理) : 对于一个实对称矩阵 $A$, 最大的特征值是$${\lambda }_1=\underset{x\ne 0}{\sup }\frac{x^{T}Ax}{x^{T}x}.$$

令矩阵 $A_G$ 的特征值是 ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$, 然后令 $\text{mathbbm}1$ 是 $R^{V(G)}$ 中的全壹向量. 那么我们有$${\lambda }_1\ge \frac{\text{mathbbm}{1}^T{A}_G\text{mathbbm}1}{\text{mathbbm}{1}^T\text{mathbbm}1}=\frac{2e(G)}{n}=(p+o(1))n.$$另一方面, 因为 ${\mathbf{C}}_4$ 成立, 我们有$${\lambda }_1^4\le \sum _i^n{\lambda }_i^4=\mathrm{tr}{A}_G^4\le p^4{n}^4+o(n^4),$$这就意味着 ${\lambda }_1\le pn+o(n)$. 从而 ${\lambda }_1=pn+o(n)$. 余下就是, $$\underset{i\ne 1}{\max }{\left|{\lambda }_i\right|}^4\le \mathrm{tr}\left(A_G^4\right)-{\lambda }_1^4\le p^4{n}^4-p^4{n}^4+o(n^4)=o(n^4)$$

$\square$

定理 1.1 最精彩的就是 ${\mathbf{C}}_4$ 性质, 它看上去是所有性质中最弱的, 但是却能够推出其它所有性质.

我们说过这个定理是关于稠密图的 (也就是说 $p$ 是个常数) , 当然也可以写出它在稀疏情形下的推广 (在这个情形下, 随着 $n\to \infty$, $p=p_n\to 0$) . 比如说, 对 $\mathbf{DISC}$ 而言, 我们需要把 $o(n^2)$ 改成 $o(p{n}^2)$, 从而使其可以蕴含这样的事实: 一个拟随机图的边数应该接近于真随机图中的期望边数. 类似的, 在 $\mathbf{COUNT}$ 里, $H$ 带标号地出现的次数应该是 $(1+o(1))p^{e(H)}{n}^{v(H)}$. 但是对稀疏图来说, 这些性质并不等价. 具体来说, 稀疏图上计数引理不再成立了. 比如说, 下面这个图满足了 $\mathbf{DISC}$ 在稀疏情形下的推广, 但是它甚至不包含任何的 $C_3$.

例 1.6. 令 $p=o(n^{-1/2})$, 那么我们期望中, $C_3$ 带标号出现的次数应该接近于 $\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3$, 并且图中的边数应该是 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)p$. 但是因为我们现在 $p=o(n^{-1/2})$, 图中 $C_3$ 的出现次数要比边数低阶. 所以我们可以在在这个 $G(n,p)$ 图里面, 每个三角形都删去一条边, 这样也只删了 $o(n^{2}p)$ 条边, 从而 $\mathbf{DISC}$ 的稀疏推广仍然成立, 但是现在这个图却没有三角形了. 这个图在 $\mathbf{DISC}$ 性质的意义下是伪随机的, 但是在三角形个数的意义上就不是伪随机的了.