$0/1$-Polytopes with Exponentially Small Edge Expansion

技术摘要：具有指数级微小边扩张性的 0/1-多胞形

问题陈述
本文探讨了 Mihail–Vazirani 猜想，该猜想认为每个 0/1-多胞形的图（1-骨架）的边扩张（Cheeger 常数）至少为 1。边扩张是多面组合学和马尔可夫链蒙特卡洛方法中的一个关键指标，因为它决定了用于近似采样和计数随机游走的混合时间。虽然该猜想已在许多子类中得到验证（例如：匹配多胞形、拟阵基多胞形以及低维情况），但在全一般性情形下仍是一个开放问题。该猜想的一个较弱版本曾建议存在关于维度的反多项式下界，这足以满足多项式时间算法的应用需求。

方法论与构造
作者展示了一个显式的 0/1-多胞形族 $(P_n)_{n \ge 1}$ 的构造，旨在设计出其边扩张随维度增加而呈指数级减小的特性。该构造依赖于两个特定布尔点集的凯莱和（Cayley sum）。

1. 基础组件：
   • 令 $C = \{0, 1\}^2$（单位正方形的顶点）且 $D = \{0, e_1, e_2\}$（标准 2-单纯形的顶点）。
   • 定义 $Q = \text{conv}(C)$ 以及 $\Delta = \text{conv}(D)$。
2. 层构造：
   • 在 $\mathbb{R}^{4n}$ 中定义两组点：$X_n = C^n \times D^n$ 和 $Y_n = D^n \times C^n$。
   • 多胞形 $P_n$ 被构造为凯莱和 $X_n * Y_n = \text{conv}((X_n \times \{0\}) \cup (Y_n \times \{1\}))$。这产生了一个位于 $\mathbb{R}^{4n+1}$ 中的多胞形。
3. 结构分析：
   • 顶点： 根据事实 3，顶点集 $V(P_n)$ 正是生成集 $V_n = (X_n \times \{0\}) \cup (Y_n \times \{1\})$。
   • 边： 边被分为两类：
     • 同层边（Same-layer edges）： 位于下层（$t=0$）或上层（$t=1$）内部的边。这些边对应于笛卡尔积 $Q^n \times \Delta^n$ 和 $\Delta^n \times Q^n$ 中的边。
     • 跨层边（Cross-layer edges）： 连接下层顶点与上层顶点的边。这些边由“兼容关系” $R \subseteq C \times D$ 来刻画，其中一对 $(c, d)$ 是兼容的，如果存在单个线性目标函数在 $C$ 上于 $c$ 处取得唯一最大值，且在 $D$ 上于 $d$ 处取得唯一最大值。
   • 不变分解： 作者基于顶点的“活跃块（active blocks）”识别了一个关于跨层边的不变量。具体而言，对于顶点 $u$，令 $I(u)$ 为前 $n$ 个块非零的索引集合，$J(u)$ 为后 $n$ 个块非零的索引集合。跨层边保持这些集合不变（即 $I(u)=I(v)$ 且 $J(u)=J(v)$）。

核心结果与证明策略
本文的核心在于证明边扩张 $h(G(P_n))$ 随 $n$（并随维度 $4n+1$）呈指数级衰减。

1. 割集（The Cut）： 作者构造了一个特定的顶点子集 $S_n \subset V(P_n)$，其定义条件为 $|I(u)| < |J(u)|$。
   • $S_n$ 由前一组活跃块数量少于第二组活跃块数量的顶点组成。
   • 由于 $I$ 和 $J$ 在跨层边下具有不变性，没有任何跨层边跨越割集 $(S_n, V_n \setminus S_n)$。边界 $\delta(S_n)$ 完全由同层边组成。
2. 割集大小：
   • 通过对具有剖面 $(k, \ell)$ 的顶点计数进行求和来计算 $S_n$ 的大小。总顶点数为 $2 \cdot 12^n$。$S_n$ 的大小通过计算得出为 $12^n - \sum_{r=0}^n A_{r,r}$，其中 $A_{r,r}$ 代表具有对角剖面（$k=\ell=r$）的顶点计数。
   • 证明了 $|S_n| < |V_n|/2$，使其成为边扩张定义中的有效集合。
3. 边界大小：
   • 边界边必须连接一个具有对角剖面 $(r, r)$ 的顶点与一个非对角剖面的顶点。
   • 此类边的数量通过涉及 $A_{r,r}$ 以及与激活/去激活块方式相关的因子的求和来限制。
4. 渐近衰减：
   • 扩张比率 $h(G(P_n)) = \frac{|\delta(S_n)|}{|S_n|}$ 被限制在 $\frac{4n \sum A_{r,r}}{12^n - \sum A_{r,r}}$ 之下。
   • 利用恒等式 $\sum A_{r,r} \le (1+\sqrt{6})^{2n}$，作者定义 $\beta = \frac{(1+\sqrt{6})^2}{12} \approx 0.96 < 1$。
   • 证明了扩张率被限制在 $O(n \beta^n)$，呈指数级衰减。

主定理
本文证明了定理 1：存在一个常数 $c > 0$ 和一个维度趋于无穷大的全维 0/1-多胞形序列 $(P_n)$，使得对于所有足够大的 $n$：
$$h(G(P_n)) \le \exp(-c \cdot \dim(P_n))$$
因此，对于较大的 $n$，有 $h(G(P_n)) < 1$。

意义与主张

• 对猜想的驳斥： 该构造明确驳斥了 Mihail–Vazirani 猜想的最强形式（扩张 $\ge 1$）及其较弱形式（反多项式下界）。
• 范围： 该结果适用于全维 0/1-多胞形，这区别于以往涉及半整（half-integral）多胞形（Cardinal 和 Pournin）或糟糕顶点扩张（Kwok 等）的负面证据，后者并不一定意味着 0/1-多胞形的边扩张也差。
• AI 归属： 本文明确指出，该构造与分析是由 GPT-5.6 Sol 以“单次生成（one-shot）”方式生成的，作者独立验证并精简了证明过程。
• 局限性： 本文并未提出新的算法应用或未来的研究方向，仅专注于提供该反例家族的存在性证明。

综上所述，本文为长期存在的组合学猜想提供了一个严谨的反例，证明了 0/1-多胞形的边扩张可以随维度呈指数级消失，从而使“此类多胞形普遍支持快速混合随机游走”的假设失效。