3. 拟随机 Cayley 图

我们已经看到 Chung–Graham–Wilson 定理 (定理 1.0.1) 在稀疏情形下的版本并不成立. 但是有些惊讶的是, 如果我们只考虑群的 Cayley 图 (包括非 Abel 群) , 无论边密度是多少, 稀疏版本的 $\mathbf{DISC}$ 和 $\mathbf{EIG}$ 都是等价的.

对一般的稀疏图而言, 稀疏版本的 $\mathbf{DISC}$ 并不能推出稀疏版本的 $\mathbf{EIG}$. 考虑一个很大的随机 $d$-正则图和一个 $K_{d+1}$ 的不交并, 这个图满足稀疏版本的 $\mathbf{DISC}$ (因为那个很大的随机 $d$-正则图满足稀疏版本的 $\mathbf{DISC}$) , 但是最大的两个特征值是 ${\lambda }_1={\lambda }_2=d$ (因为两个连通分量上的两个全壹向量都分别是特征向量) , 这违背了稀疏版本的 $\mathbf{EIG}$ 对 ${\lambda }_2=o(d)$ 的要求.

定理 3.1 (Conlon-Zhao). 令 $\Gamma$ 是一个有限群, 并且 $S\subset \Gamma$ 是一个满足 $S=S^{-1}$ 的子集. 令 $G=\mathrm{Cay}(\Gamma ,S)$, $n=|\Gamma |$ 并且 $d=|S|$. 对于任意 $ϵ>0$, 我们定义以下两个性质:

•	$\mathrm{DISC}(ϵ)$ : 对所有 $X,Y\subseteq G$, 我们有 $|e(X,Y)-\frac{d}{n}|X||Y||\le ϵdn$
•	$\mathrm{EIG}(ϵ)$ : $G$ 是一个 $(n,d,\lambda )$ -图, 并且 $\lambda \le ϵd$.

那么如果 $G$ 满足 $\mathrm{EIG}(ϵ)$, 它就会满足 $\mathrm{DISC}(ϵ)$. 如果 $G$ 满足 $\mathrm{DISC}(ϵ)$, 那么它就会满足 $\mathrm{EIG}(8ϵ)$.

定理 $\text{ref}th:4.12$ 的证明需要用到 Grothendieck 不等式.

定理 3.2 (Grothendieck 不等式). 存在一个绝对常数 $K>0$, 满足对于任意矩阵 $A=(a_{i,j})\in {\mathbb{R}}^{n\times n}$,

$$\underset{\begin{array}{c}{x}_i\in B\\ y_i\in B\end{array}}{\sup }\sum _{i,j}{a}_{i,j}⟨x_i,y_j⟩\le K\underset{\begin{array}{c}{x}_i\in \{\pm 1\}\\ y_i\in \{\pm 1\}\end{array}}{\sup }{a}_{i,j}{x}_i{y}_j$$

在式子左边, 上极限的范围是某个空间 ${\mathbb{R}}^m$ 里的单位球 $B$.

Grothendieck 不等式的右边是一个离散定义域的二次型 $⟨x,Ay⟩$. 它 (往往) 有很重要的组合意义, 但是很难优化. 左边是右边的一个 “半正定松弛”, 有许多高效的算法. 左边的求和始终比右边大求和, 并且 Grothendieck 不等式告诉我们, 左边的求和比右边的求和至多大了常数倍. 所以左边的求和是右边的求和的一个近似.

注 3.3. 人们知道 $K=1.78$ 可以让这个不等式成立, 但是最优的值 (被称作 “实数 Grothendieck 常数”) 还是未知的.

定理 3.1. 由 expander mixing 引理可知, $\mathrm{EIG}(ϵ)$ 可以推出 $\mathrm{DISC}(ϵ)$. 具体来说, 用这个引理可以推出对于所有的 $X,Y\subseteq V(G)$ 有, $$\left|e(X,Y)-\frac{d}{n}|X||Y|\right|\le \lambda \sqrt{|X||Y|}\le ϵdn.$$这正是我们想要的.

为了证明另外一个方向, 假设 $\mathrm{DISC}(ϵ)$ 成立, 对于每个 $x,y\in \{\pm 1{\}}^{\Gamma }$, 我们定义 $x^{+},x^{-},y^{+},y^{-}\in \{0,1{\}}^{\Gamma }$, 使得$$x_g^{+}=\{\begin{array}{ll}1& \text{ if }{x}_g=1\\ 0& \text{ otherwise }\end{array}\text{and}{x}_g^{-}=\{\begin{array}{ll}1& \text{ if }{x}_g=-1\\ 0& \text{ otherwise }\end{array}$$

那么 $x=x^{+}-x^{-}$. 我们类似的定义 $y^{+}$ 和 $y^{-}$.

考虑矩阵 $A\in {\mathbb{R}}^{\Gamma \times \Gamma }$, $A_{g,h}=1_S(g^{-1}h)-\frac{d}{n}$ (这里 $1_S$ 是 $S$ 的指示函数). 那么, $$x_g^{+}=\{\begin{array}{ll}1& \text{ if }{x}_g=1\\ 0& \text{ otherwise }\end{array}\text{and}{x}_g^{-}=\{\begin{array}{ll}1& \text{ if }{x}_g=-1\\ 0& \text{ otherwise }\end{array}$$

这里面每一项都可以被 $\mathrm{DISC}$ 控制住. 比如说, $$⟨x^{+},A{y}^{+}⟩=e\left(X^{+},Y^{+}\right)-\frac{d}{n}\left|X^{+}\right|\left|Y^{+}\right|$$

这里 $X^{+}=\{g\in \Gamma :x_g=1\},Y^{+}=\{g\in \Gamma :y_g=1\}$. 所以我们知道 $|⟨x^{+},A{y}^{+}⟩|\le ϵdn$. 这对于其它项也成立, 所以我们有$$\begin{array}{r}|⟨x,Ay⟩|\forall x,y\in \{\pm 1{\}}^{\Gamma }\end{array}$$

我们接下来用极大极小的方式来表示特征值$$\max \{|{\lambda }_2|,|{\lambda }_n|\}=\underset{\begin{array}{c}|x|,|y|=1\\ x,y\in {\mathbb{R}}^{\Gamma }\end{array}}{\sup }⟨x,Ay⟩.$$

对于每个 $x\in {\mathbb{R}}^{\Gamma }$, 我们用 $x_s^g=x_{sg}$ (其中 $s$ 遍历 $\Gamma$) 来定义向量 $x^g\in R^{\Gamma }$. 那么由于 $x^g$ 只是把 $x$ 的下标重新排列了一下, 我们有 $|x|=|x^g|$. 所以对于任意 $|x|,|y|=1$ 的 $x,y\in {\mathbb{R}}^{\Gamma }$, 我们有

$$\begin{array}{rl}⟨x,Ay⟩& =\sum _{g,h}{A}_{g,h}{x}_g{y}_h\\ & =\frac{1}{n}\sum _{g,h,s}{A}_{sg,sh}{x}_{sg}{y}_{sh}\\ & =\frac{1}{n}\sum _{g,h,s}{A}_{g,h}{x}_{sg}{y}_{sh}\\ & =\frac{1}{n}\sum _{g,h}{A}_{g,h}⟨x^g,y^h⟩\le 8ϵd\end{array}$$

最后的不等式是应用了 Grothendieck 不等式 ($K<2$) 与 (3). 所以 $\mathrm{EIG}(8ϵ)$ 成立.

$\square$