跳转至

固定大小扩张图构造

错误原文（第 227 页最后一行）

…… 做 \((G_{\mathbb{F}} \otimes G_{\mathbb{F}}) ~ {\bigcirc\kern{-0.8em}{z}\kern{0.6em}} G_{\mathbb{F}}\) 和 \(G_{\mathbb{F}}\) 的路径积，得到一个 \((F^6, F, 3/F)\)-扩张图。

注意到路径积需要两张图的顶点个数相同，但是 \((G_{\mathbb{F}} \otimes G_{\mathbb{F}}) ~ {\bigcirc\kern{-0.8em}{z}\kern{0.6em}} G_{\mathbb{F}}\) 有 \(F^6\) 个顶点，\(G_{\mathbb{F}}\) 只有 \(F^2\) 个顶点，不能做路径积。

正确的做法可以参考 Reingold, Vadhan, Wigderson (2002) 1 中命题 5.2 的构造。按照下面的方式递归定义一组扩张图 \((G_{\mathbb{F}}^{(i)})_{i \in \mathbb{N}}\)：

\[ \begin{align} G_{\mathbb{F}}^{(1)} &= G_{\mathbb{F}} \otimes G_{\mathbb{F}}\\ G_{\mathbb{F}}^{(i + 1)} &= G_{\mathbb{F}}^{(i)} ~ {\bigcirc\kern{-0.8em}{z}\kern{0.6em}} G_{\mathbb{F}}\\ \end{align} \]

可以证明 \(G_{\mathbb{F}}^{(i)}\) 是 \((F^{2(i + 1)}, F^2, O(i/\sqrt{F}))\)-扩张图。因此 \(G_{\mathbb{F}}^{(5)}\) 是 \((F^{12}, F^2, O(1/\sqrt{F}))\)-扩张图。取 \(F\) 足够大，并令 \(D = F^2\)，就可以得到一个具体的 \((D^6, D, 1/4)\)-扩张图。

致谢

感谢王文茜同学在 2024 年春季学期的课上指出了这个问题。

  1. O. Reingold, S. Vadhan, and A. Wigderson, “Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders,” The Annals of Mathematics, vol. 155, no. 1. JSTOR, p. 157, Jan. 2002. doi: 10.2307/3062153. Arxiv version: https://arxiv.org/pdf/math/0406038.pdf. ↩