On induced subgraphs of $H(n,3)$ with maximum degree $1$

本文研究了汉明图 $H(n,3)$ 中最大度不超过 1 的诱导子图，给出了在特定约束条件下（如与最大独立集不相交或满足特定覆盖条件）该子图顶点数的上界，并确定了部分情形下的最优构造。

要点

这篇论文探讨了一个非常有趣的数学问题，我们可以把它想象成在一个巨大的**“三维乐高积木迷宫”里玩一个“不拥挤”的游戏**。

为了让你轻松理解，我们把这篇论文的核心内容拆解成几个简单的故事：

1. 游戏场地：汉明图 $H(n, 3)$

想象有一个巨大的迷宫，由无数个小房间组成。

• 每个房间都有一个坐标，比如 $(0, 1, 2)$。
• 这个迷宫有 $n$ 个维度（就像有 $n$ 个方向可以走：前后、左右、上下……）。
• 在每个方向上，只有 3 种状态（比如：红、黄、蓝，或者 0、1、2）。
• 规则：如果你把两个房间的坐标只在一个方向上改变（比如从“红”变成“黄”，其他不变），这两个房间就是邻居，它们之间有一条路相连。

这个迷宫就是数学家口中的汉明图 $H(n, 3)$。

2. 游戏目标：选房间，但别太挤

我们要在这个迷宫里选出一组房间（记为集合 $U$），但是有一个严格的限制：

• 限制：你选中的任何一个房间，在你选中的这群人里，最多只能有 1 个邻居。
• 比喻：想象你在选一群朋友去聚会。规则是：在聚会现场，每个人最多只能和 1 个 其他朋友握手。
  • 如果一个人握了 2 只手，那就不行了（度数超过 1）。
  • 如果一个人没握手，或者只握了 1 只手，那就没问题。

核心问题：在这个巨大的迷宫里，我们最多能选出多少个房间，才能满足“每个人最多只握 1 次手”这个规则？

3. 之前的发现：大概能选多少？

以前大家知道，如果我们要选的人完全不碰迷宫里某些特定的“最大安全区”（独立集），那么最多只能选 $3^{n-1} + 1$ 个房间。这就像是在迷宫的一半区域里，稍微多塞进 1 个人。

但是，如果我们不限制必须避开那些“安全区”，能不能塞进更多人呢？

4. 这篇论文的三大发现

作者 Aaron Potechin 和 Hing Yin Tsang 通过精妙的数学推导和计算机辅助，发现了以下三点：

发现一：如果避开“安全区”，上限很死

如果你选的人完全避开了迷宫里最大的那个“互不相邻”的区域（就像避开所有已经有人坐的桌子），那么无论你怎么折腾，人数上限就是 $3^{n-1} + 1$。

• 比喻：如果你坚持不坐任何一张已经有人坐的桌子，那你最多只能多放 1 个人进去，再多就挤不下了。而且，所有能达到这个最大人数的方案，本质上长得都一样（同构）。

发现二：如果不避开，可以塞进更多人！

如果你不介意和那些“安全区”的人混在一起，人数上限可以突破！

• 对于 $n=6$（6 维迷宫），作者发现了一个神奇的方案，能选出 $3^{n-1} + 18$ 个人。
• 这意味着，只要稍微“越界”一点点，就能多塞进 17 个 额外的人（从 +1 变成 +18）。
• 比喻：就像在电影院里，如果非要坐空位，只能多坐 1 个；但如果允许稍微挤一挤，或者利用一些特殊的座位排列，就能多塞进 18 个人。作者证明了对于 6 维及以上的迷宫，18 个就是极限了，再也塞不进第 19 个了。

发现三：如果“每条路”都至少站一个人

作者还研究了一种特殊情况：假设选出的这群人非常“霸道”，迷宫里每一条直线（每个方向）上，都至少有一个被选中的人。

• 在这种情况下，人数上限被限制在 $3^{n-1} + 81$。
• 比喻：如果你要求“每条走廊里都必须站一个我们的人”，那么虽然比之前的 +1 多多了，但也无法无限膨胀，最多只能比基础人数多 81 个。

5. 他们是怎么做到的？（方法论）

为了证明这些结论，作者用了两个主要工具：

1. 乐高积木的递归法：
   他们把高维的迷宫看作是由低维的迷宫拼起来的。就像搭乐高，先研究 2 维、3 维的情况，找出规律，然后一层层往上搭，看看能不能把“额外的人数”（Extra points）带上去。

2. 计算机 SAT 求解器（像是一个超级逻辑侦探）：
   在证明某些复杂情况（比如 6 维迷宫）时，人类的大脑很难穷尽所有可能性。作者把问题写成了逻辑公式，扔给计算机（SAT Solver）。计算机像侦探一样，检查了所有可能的排列组合，最终确认：“是的，在 6 维迷宫里，确实不可能塞进超过 18 个额外的人。”

6. 总结与意义

• 简单总结：这篇论文告诉我们，在一个由 0、1、2 组成的 $n$ 维迷宫里，如果我们想选出一群人，让每个人最多只认识 1 个同伴，那么：

  • 如果我们要避开某些特定区域，最多只能多 1 个人。
  • 如果不避开，在 6 维及以上，最多可以多 18 个人。
  • 如果要求每条路都有人，最多可以多 81 个人。

• 为什么重要：
  这个问题不仅仅是玩积木游戏。它和计算机科学中的“敏感度猜想”（Sensitivity Theorem）紧密相关。这个猜想解释了计算机处理信息时的复杂程度。这篇论文通过研究这种特殊的“稀疏”结构，帮助数学家们更好地理解高维空间中的几何性质，为未来解决更复杂的计算理论问题提供了新的线索。

一句话概括：
作者们在高维迷宫里玩“不拥挤”游戏，发现只要稍微打破一点规则，就能塞进比想象中多得多的人，并且用数学和计算机算出了这个“多出来的人数”的绝对上限。

技术摘要

这是一份关于论文《On induced subgraphs of H(n, 3) with maximum degree 1》（关于最大度为 1 的汉明图 $H(n, 3)$ 的诱导子图）的详细技术总结。

1. 研究背景与问题定义

背景：
该研究源于布尔函数敏感性定理（Sensitivity Theorem）的证明。Huang (2019) 证明了布尔超立方体（Boolean hypercube）中，任何包含超过一半顶点的诱导子图，其最大度至少为 $\sqrt{n}$。这一结果引发了对更广泛图类（如汉明图 $H(n, k)$）中诱导子图最大度与顶点数量之间关系的探索。

核心问题：
本文聚焦于汉明图 $H(n, 3)$，其顶点集为 $\mathbb{Z}_3^n$，边连接汉明距离为 1 的点。
问题 1： 设 $U \subseteq \mathbb{Z}_3^n$。如果 $U$ 诱导出的子图最大度至多为 1（即子图由孤立点和匹配边组成），那么 $|U|$ 最大可以是多少？

已知背景：

• 当 $U$ 与最大独立集不相交时，已知存在大小为 $3^{n-1} + 1$ 的集合。
• 当 $n \ge 3$ 时，存在大小为 $3^{n-1} + 1$ 的集合。
• 对于 $k \ge 3$，Dong 和 Tanday 等人构造了大小为 $\alpha(H(n, k)) + 1$ 且最大度为 1 的诱导子图。

2. 主要贡献与结果

本文通过组合分析、递归构造以及计算机辅助证明（SAT 求解器），得出了以下主要结论：

2.1 与最大独立集不相交的情况

定理 1.1： 如果 $U \subseteq \mathbb{Z}_3^n$ 诱导出的子图最大度为 1，且 $U$ 与 $H(n, 3)$ 的某个最大独立集不相交，则 $|U| \le 3^{n-1} + 1$。

• 唯一性： 所有满足上述条件且大小为 $3^{n-1} + 1$的集合$U$在图自同构下是同构的。作者定义了这种唯一的集合为**规范集（Canonical Set）**，记为$D_n$。

2.2 一般情况下的下界构造

如果不要求 $U$ 与最大独立集不相交，集合可以更大。
定理 1.2： 对于 $n \ge 6$，存在一个集合 $U \subseteq \mathbb{Z}_3^n$，其诱导子图最大度为 1，且大小为 $|U| = 3^{n-1} + 18$。

• 作者通过 SAT 求解器找到了 $n=4, 5, 6$ 时的最优构造，分别比 $3^{n-1}$ 多出 2, 6, 18 个点。
• 对于 $n \ge 6$，可以通过将 $n=6$ 的构造扩展到更高维度来保持“额外点数”为 18。

2.3 饱和集（Saturated Sets）的上界

为了证明上界，作者引入了$i$-饱和的概念：如果 $U$ 在方向 $e_i$ 上的每一条线（即形如 $\{x, x+e_i, x+2e_i\}$ 的集合）都至少包含一个 $U$ 中的点，则称 $U$ 是 $i$-饱和的。

• 观察发现，$n \le 6$ 时的所有极值构造都是某个方向的饱和集。
  定理 1.3（主要上界）： 如果 $U \subseteq \mathbb{Z}_3^n$ 诱导子图最大度为 1，且 $U$ 是某个方向 $i$ 的 $i$-饱和集，则 $|U| \le 3^{n-1} + 81$。
• 注： 如果不使用计算机辅助证明，仅通过纯数学推导（弱线扩展引理），可以得到一个较弱的上界 $3^{n-1} + 729$。

3. 方法论与技术细节

3.1 函数表示法与降维

作者将子集 $U \subseteq \mathbb{Z}_3^n$ 表示为函数 $U_f: \mathbb{Z}_3^{n-1} \to \mathcal{P}(\mathbb{Z}_3)$。

• 定义基集 $A=\{0\}, B=\{1\}, C=\{2\}$ 以及补集 $X=\{1,2\}, Y=\{0,2\}, Z=\{0,1\}$。
• 诱导度 $\le 1$ 的条件转化为 $U_f$ 在相邻点上的取值约束（Proposition 2.13）。例如，如果 $U_f(x)=X$，则其邻居必须取 $A$ 或空集。

3.2 规范集（Canonical Sets）与规范路径

• 规范集 $D_n$： 作者递归定义了唯一的最大度 1 且与最大独立集不相交的集合 $D_n$。
• 规范路径（Canonical Paths）： 定义了一种从点 $x$ 出发的路径，若 $U_f(x) \in \{X, Y, Z\}$（即“额外点”），路径会沿着特定方向移动，最终汇聚到唯一的“额外点” $x_U$。
• 这一结构表明，如果 $U$ 是 1-饱和的，那么所有“额外点”对应的规范路径必须汇聚到同一个点，这极大地限制了额外点的数量。

3.3 线扩展引理（Line Extension Lemma）

这是证明上界的核心引理（Lemma 5.6）：

• 内容： 对于 $n \ge 6$，如果 $U_f$ 诱导度为 1 且 $U_f(0) = X$，那么对于任意方向 $i$，存在另一个方向 $j$，使得 $U_f$ 在 $\text{Span}(e_i, e_j)$ 上的限制是规范集。
• 验证方法： 该引理对于 $n=6$ 的验证依赖于 SAT 求解器。作者将寻找反例（即 $i$-skew 函数）转化为布尔可满足性问题，并确认在 $n=6$ 时无解。
• 对于 $n \ge 8$，作者给出了不依赖 SAT 求解器的纯数学证明（Lemma 5.8），虽然这导致上界从 81 放宽到 729。

3.4 上界证明逻辑

1. 利用线扩展引理，证明对于每个 $x$ 使得 $U_f(x) \in \{X, Y, Z\}$，都存在一个高维仿射子空间 $H_x$（维度至少 $n-5$），在该子空间上 $U_f$ 表现为规范集。
2. 利用规范集的唯一性和结构性质（引理 3.17），证明不同 $x$ 对应的 $H_x$ 必须是不相交的。
3. 由于 $\mathbb{Z}_3^{n-1}$ 中最多只能容纳 $3^4 = 81$个互不相交的$n-5$维仿射子空间，因此$U_f$取值为${X, Y, Z}$ 的点数不超过 81。
4. 总大小 $|U| = 3^{n-1} + |\{x : U_f(x) \in \{X, Y, Z\}\}| \le 3^{n-1} + 81$。

4. 结论与开放问题

结论：

• 在 $H(n, 3)$ 中，最大度为 1 的诱导子图的大小被严格限制在 $3^{n-1} + O(1)$ 的范围内。
• 对于 $n=6$，最优解为 $3^5 + 18$。
• 对于 $i$-饱和集，上界为 $3^{n-1} + 81$。

开放问题（Conjecture 1）：
作者猜想，即使去掉"$i$-饱和”的假设，所有诱导度为 1 的子集大小也满足 $|U| \le \alpha(H(n, 3)) + O(1)$。即额外点的数量是一个与 $n$ 无关的常数。

其他问题：

• 对于诱导度 $d > 1$ 的情况，最大子集大小是多少？作者给出了一个构造，表明至少有 $3^{n-1} + 3^{\lfloor (d-1)n/d \rfloor}$ 个额外点，但这可能不是最优的。

5. 意义

这篇论文将 Huang 关于布尔超立方体的敏感性结果推广到了三元汉明图 $H(n, 3)$。它展示了在更复杂的图结构中，最大度约束如何严格限制子集的大小。研究结合了精细的组合结构分析（规范集、路径）与现代计算工具（SAT 求解器），为处理高维离散结构中的极值问题提供了新的范式。特别是证明了在 $n \ge 6$ 时，即使允许与最大独立集相交，子集大小的增长也是极其有限的（常数级），这加深了对图论中局部约束与全局结构关系的理解。