AFTD Auto-Formalizing Theoretical Domains

Research Blogs

相交阈值为二的二部子集图对每一个不小于五的参数都是列表可染色的

low tier2026-11-11OP-861审阅: Claude CodeEnglish

摘要

对于整数 $k \ge 2$ 以及整数阈值 $r \ge 0$,二部子集图 $G(k,r)$ 具有顶点部类 $A$ 和 $B$,它们是 $\{1, \dots, 2k-1\}$ 的所有 $k$ 元子集族 $\binom{[2k-1]}{k}$ 的两个不相交副本,且在 $a_S \in A$ 与 $b_T \in B$ 之间存在一条边当且仅当 $|S \cap T| \le r$。为每个顶点分配其自身的子集作为其列表,并设 $r^*(k)$ 为使得这些标准列表不存在正常染色的最小 $r$。arXiv:2610.42094 表明 $r^2 > 2(2k-1)\ln(2k-1)$ 会导致不可染色性,从而 $r^*(k) = O(\sqrt{k \ln k})$,并指出其方法对于真正的最小 $r$ 未给出任何信息。我们在另一方面证明了两个事实。第一,在固定阈值 $r$ 下的标准列表可染色性可由 $k$ 传递至 $k+1$,因此 $r^*(k)$ 关于 $k$ 是非递减的。第二,通过在两侧使用 $\mathbb{Z}_9$ 上的单一规则,$G(5,2)$ 从其标准列表中是可染色的。两者结合可得,对于每一个 $k \ge 5$,$G(k,2)$ 从其标准列表中都是可染色的,即对所有 $k \ge 5$ 均有 $r^*(k) \ge 3$。所有命题均已在 Lean 4 中得到验证。

1. 引言

图的列表色数或选择数是图论中的一个核心参数。在 arXiv:2610.42094 中,一项关于二部图列表可染色性的研究引入了一族二部子集图,它们在标准列表分配下的列表可染色性性质提供了二部图选择数的下界。

对于整数 $k \ge 2$ 和整数 $r \ge 0$,二部子集图 $G(k,r)$ 定义为具有两个顶点部类 $A$ 与 $B$,二者均同构于具有 $2k-1$ 个元素的基础集(记为 $[2k-1] = \{1, \dots, 2k-1\}$)的所有 $k$ 元子集族 $\binom{[2k-1]}{k}$。两个顶点 $a_S \in A$ 与 $b_T \in B$ 之间有边相连当且仅当其定义子集满足相交条件 $|S \cap T| \le r$。在 $A$ 内部或 $B$ 内部不存在边,这使得 $G(k,r)$ 成为一个二部图。每个顶点都被分配其下标子集作为其可用颜色列表:对所有 $a_S \in A$ 有 $L(a_S) = S$,对所有 $b_T \in B$ 有 $L(b_T) = T$。来自这些标准列表的正常列表染色是指为每个 $a_S \in A$ 选择一种颜色 $c(a_S) \in S$,并为每个 $b_T \in B$ 选择一种颜色 $c(b_T) \in T$,使得只要 $|S \cap T| \le r$,所选的颜色就不同:$c(a_S) \ne c(b_T)$。

最小不可染色相交参数 $r^*(k)$ 定义为使得 $G(k,r)$ 从其标准列表分配 $L$ 不存在正常列表染色的最小整数 $r \ge 0$。在 arXiv:2610.42094 中,定理 1.3 确立了条件 $r^2 > 2(2k-1)\ln(2k-1)$ 足以保证 $G(k,r)$ 从 $L$ 不存在正常列表染色。该条件给出了 $r^*(k)$ 的一个量级为 $\sqrt{k \ln k}$ 的上界。然而,正如 arXiv:2610.42094 在推论 1.4 之后明确指出的: 'Part (c) concerns only the lower bound produced by Theorem 1.3 ; it says nothing about the true choosability of $G(k,r)$ , which could be larger, nor about the true least $r$ for which $G(k,r)$ is uncolorable from its standard lists.' 该论文因此将 $r^*(k)$ 的真实值留作公开问题。$r^*(k) = \Theta(\sqrt{k \ln k})$ 还是在某个 $r = o(\sqrt{k \ln k})$ 处就已经开始出现不可染色性,是它所提出的自然问题;该论文未给出 $r^*(k)$ 的任何下界。

在这项工作之前,已经确立了关于 $G(k,r)$ 和 $r^*(k)$ 的若干基准界和结构限制:

  • 平凡上界:对于任意 $k \ge 1$ 以及任意 $r \ge k$,图 $G(k,r)$ 从其标准列表中不存在正常列表染色,这已在 bipartite_subset_uncolorable_of_ge 中形式化。事实上,因为任意两个 $k$ 元子集 $S, T \subseteq [2k-1]$ 都满足 $|S \cap T| \le k \le r$,所以 $A$ 与 $B$ 之间的每一对顶点都由一条边相连。因此 $G(k,r)$ 是一个完全二部图,它不容许任何正常的标准列表染色,从而表明 $r^*(k) \le k$。
  • 阈值一的可染色性:对于每一个 $k \ge 2$,图 $G(k,1)$ 从其标准列表中是可染色的,这已在 bipartite_subset_colorable_at_one 中确立。这给出了对所有 $k \ge 2$ 均成立的下界 $r^*(k) \ge 2$。
  • 对称性阻碍:在参数 $k = 6$ 和阈值 $r = 3$ 处,op861_no_right_equivariant_k6_r3 中证明了,在 $11$ 种循环颜色的 $6$ 元子集上不存在两个颜色选择函数,使得它们都选择可用颜色、在相交至多 $3$ 个元素的所有子集对上均取不同值,并且第二个选择器满足循环等变性。

本博文证明对于每个 $k \ge 5$,$G(k, 2)$ 从其标准列表中都是可染色的(bipartite_subset_colorable_two_from_five),因此对所有 $k \ge 5$ 均有 $r^*(k) \ge 3$,这比阈值一的界大了一。该证明包含两个部分:一个对每个阈值 $r$ 均成立的提升引理,表明 $G(k,r)$ 的标准列表染色可诱导出 $G(k+1,r)$ 的标准列表染色(因此 $r^*(k)$ 随着 $k$ 的增长绝不减少);以及一个通过 $\mathbb{Z}_9$ 上的单一规则给出的 $G(5,2)$ 的显式染色。

2. 预备知识

我们遵循 Lean 形式化中使用的定义来形式化图、染色和参数。

在全文中,对于正整数 $m$,我们用 $\mathrm{Fin}(m)$ 表示基数为 $m$ 的有限集 $\{0, 1, \dots, m-1\}$。$\mathrm{Fin}(2k-1)$ 的大小为 $k$ 的子集表示为基数为 $k$ 的子集构成的子类型(subtype)的元素。

定义 1(二部子集图). 对于正整数 $k$ 和非负整数 $r$,二部子集图(记为 $G(k, r)$)是一个无向简单二部图,其顶点集划分为两个不相交的集合: $$V = A \sqcup B$$ 其中 $A$ 与 $B$ 都是 $\mathrm{Fin}(2k-1)$ 的所有 $k$ 元子集族 $\binom{\mathrm{Fin}(2k-1)}{k}$ 的副本。在 Lean 形式化中,顶点类型为和类型(sum type): $$V = \left\{ S \subseteq \mathrm{Fin}(2k-1) : |S| = k \right\} \oplus \left\{ T \subseteq \mathrm{Fin}(2k-1) : |T| = k \right\}$$ 其中 $A$ 中的顶点表示为左直和项的项,$B$ 中的顶点表示为右直和项的项。边关系的定义使得 $A$ 中的任意两个顶点均不相邻,$B$ 中的任意两个顶点均不相邻,并且一条边连接 $a_S \in A$ 与 $b_T \in B$ 当且仅当: $$|S \cap T| \le r.$$

注 1. 在定义 1 中,邻接条件使用的是弱不等式 $|S \cap T| \le r$。对于 $r = 0$,一条边连接 $a_S$ 与 $b_T$ 当且仅当 $S$ 与 $T$ 不相交。因为 $S$ 与 $T$ 是大小为 $2k-1$ 的基础集中的大小为 $k$ 的子集,容斥原理表明: $$|S \cap T| = |S| + |T| - |S \cup T| \ge 2k - (2k-1) = 1.$$ 因此,对于任意两个子集 $S, T \in \binom{\mathrm{Fin}(2k-1)}{k}$,它们的交集永不为空,所以 $|S \cap T| \ge 1$。从而,当 $r = 0$ 时,$G(k, 0)$ 的边集为空。当 $r \ge k$ 时,由于 $|S \cap T| \le |S| = k \le r$,不等式 $|S \cap T| \le r$ 对所有 $S$ 和 $T$ 均成立;因此 $G(k, r)$ 是两个部的顶点数均为 $\binom{2k-1}{k}$ 的完全二部图。

定义 2(标准列表分配). 对于二部子集图 $G(k, r)$,标准列表分配 $L$ 为每个顶点分配其对应的颜色子集: $$L(a_S) = S, \quad L(b_T) = T.$$ 在 Lean 中,每个子集 $S$ 都是一个子类型的项,该子类型表示 $\mathrm{Fin}(2k-1)$ 中基数为 $k$ 的有限颜色集合(finset)。列表分配通过在每个直和项上的标准子类型投影,将每个顶点映射到其底层的颜色子集。

定义 3(标准列表可染色性). 谓词 bipartite_subset_standard_list_colorable $k$ $r$ 断言存在一个取值于 $\mathrm{Fin}(2k-1)$ 的 $G(k, r)$ 的正常图染色 $c$,使得每个顶点都从其所分配的列表中获得一种颜色: $$\text{bipartite\_subset\_standard\_list\_colorable } k\ r \iff \exists c : (G(k,r)).\text{Coloring}(\mathrm{Fin}(2k-1)), \; \forall v \in V, \; c(v) \in L(v).$$ 展开该条件,这意味着存在两个选择器函数: $$c_A : \binom{\mathrm{Fin}(2k-1)}{k} \to \mathrm{Fin}(2k-1) \quad \text{and} \quad c_B : \binom{\mathrm{Fin}(2k-1)}{k} \to \mathrm{Fin}(2k-1)$$ 满足:

  1. 列表有效性:对每个 $S \in \binom{\mathrm{Fin}(2k-1)}{k}$ 有 $c_A(S) \in S$,且对每个 $T \in \binom{\mathrm{Fin}(2k-1)}{k}$ 有 $c_B(T) \in T$;
  2. 正常染色:对所有 $S, T \in \binom{\mathrm{Fin}(2k-1)}{k}$,若 $|S \cap T| \le r$,则 $c_A(S) \ne c_B(T)$。

定义 4(最小不可染阈值). 最小不可染阈值参数(记为 $r^*(k)$)是使得 $G(k, r)$ 从其标准列表中不可染色的最小非负整数 $r$: $$r^*(k) = \min \{ r \in \mathbb{N} : \neg \text{bipartite\_subset\_standard\_list\_colorable } k\ r \}.$$

注 2. 参数 $r^*(k)$ 对所有 $k \ge 1$ 都是良定义的,因为根据 bipartite_subset_uncolorable_of_ge,只要 $r \ge k$ 图就是不可染色的,这保证了集合 $\{ r \in \mathbb{N} : \neg \text{bipartite\_subset\_standard\_list\_colorable } k\ r \}$ 非空且以 $k$ 为上界。

3. 主要结果

主定理确立了对于每个整数 $k \ge 5$,阈值 $r = 2$ 的二部子集图容许来自其标准列表的正常列表染色。

定理 1 (bipartite_subset_colorable_two_from_five). 对于每个整数 $k \ge 5$,二部子集图 $G(k, 2)$ 从其标准列表分配中是可染色的: $$\forall k \ge 5, \quad \text{bipartite\_subset\_standard\_list\_colorable } k\ 2.$$

由于 $G(k,r)$ 的边集随 $r$ 的增大而增大,因此 $G(k,2)$ 的标准列表染色也是 $G(k,0)$ 和 $G(k,1)$ 的标准列表染色,故定理 1 给出 $$r^*(k) \ge 3 \quad \text{for all } k \ge 5.$$

该证明的两个组成部分(第 4 节)具有独立的用途。引理 2 对每一个阈值 $r$ 都成立:$G(k,r)$ 从其标准列表中的可染色性蕴涵 $G(k+1,r)$ 的可染色性,因此对于固定的 $r$,使得 $G(k,r)$ 可染色的 $k$ 的集合是向上封闭的,且 $r^*(k+1) \ge r^*(k)$。引理 1 是基础情形 $G(5,2)$。作为对比:

  • 在 bipartite_subset_colorable_at_one 中,对所有 $k \ge 2$ 证明了阈值 $r = 1$ 处的标准列表可染色性,这蕴涵了对所有 $k \ge 2$ 均有 $r^*(k) \ge 2$。定理 1 将该下界提高至对所有 $k \ge 5$ 均有 $r^*(k) \ge 3$。
  • 在 bipartite_subset_uncolorable_of_ge 中表明,对于任意 $k \ge 1$ 以及任意 $r \ge k$,图 $G(k,r)$ 从其标准列表中都是不可染色的,从而给出了通用的上界 $r^*(k) \le k$。
  • 在 op861_no_right_equivariant_k6_r3 中证明了,在 $k = 6$ 且 $r = 3$ 处,在 $11$ 种循环颜色的 $6$ 元子集上不存在两个颜色选择器,使得它们既选择可用颜色,又在相交至多 $3$ 个元素的所有子集对上均取不同值,并且使得第二个选择器与 $\mathbb{Z}_{11}$ 的每个平移变换 $z \mapsto z + d$ 都可交换。这表明将可染色性结果推广至阈值 $r = 3$ 需要打破循环对称性的技术。
定理 bipartite_subset_colorable_two_from_five (Lean 4 已验证)
theorem bipartite_subset_colorable_two_from_five (k : ℕ) (hk : 5 ≤ k) : bipartite_subset_standard_list_colorable k 2

4. 证明

该定理通过对 $k \ge 5$ 进行归纳,由两个引理得出:基础情形 $k = 5$(引理 1)以及在固定阈值下从 $k$ 到 $k+1$ 的递推步(引理 2)。在这两处,用选择器来重新表述可染色性都很方便:$G(k,r)$ 从其标准列表中可染色当且仅当存在从一个 $(2k-1)$ 元颜色集的 $k$ 元子集映至颜色的映射 $f, g$,满足 $f(S) \in S$、$g(T) \in T$,且只要 $|S \cap T| \le r$ 就有 $f(S) \ne g(T)$(在 $A$ 上取 $f = c$,在 $B$ 上取 $g = c$)。选择器形式在任意有限颜色集上都是有意义的,并且在通过双射重新标记颜色下是不变量;Lean 同时利用了这两个事实。

引理 1 (bipartite_subset_colorable_five_at_two). $G(5,2)$ 从其标准列表中是可染色的。

证明. 将颜色集等同于 $\mathbb{Z}_9$,对于 $i \in \mathbb{Z}_9$,令 $$N(i) = \{i+2,\ i+3,\ i+4,\ i+5\},$$ 这是一个不包含 $i$ 的 $4$ 元集。在 Lean 中通过对 $\mathbb{Z}_9$ 的所有 $5$ 元子集调用 decide 进行有限验证表明,每个 $5$ 元集 $S$ 都包含某个满足 $|S \cap N(i)| \ge 3$ 的 $i$。设 $p(S)$ 为这样的一个 $i$,并在两侧使用相同的选择器:$f = g = p$。由于 $p(S) \in S$,因而遵循了列表要求。假设 $p(S) = p(T) = i$。集合 $S \cap N(i)$ 与 $T \cap N(i)$ 是 $4$ 元集 $N(i)$ 的大小至少为 $3$ 的子集,因此它们至少共享 $3 + 3 - 4 = 2$ 个元素。这些元素位于 $S \cap T$ 中,而不在 $N(i)$ 中的 $i$ 也位于 $S \cap T$ 中。因此 $|S \cap T| \ge 3$,$a_S b_T$ 不是 $G(5,2)$ 的边。因此相同的颜色绝不会在一条边两端相遇,该染色是正常的。$\square$

引理 2 (bipartite_subset_colorable_succ). 对所有 $k \ge 1$ 以及 $r \ge 0$:若 $G(k,r)$ 从其标准列表中是可染色的,则 $G(k+1,r)$ 亦然。

证明. 设 $f, g$ 为具有 $|P| = 2k-1$ 的颜色集 $P$ 的 $k$ 元子集选择器,添加两种新颜色 $x_0, x_1$,从而 $|P \cup \{x_0, x_1\}| = 2k+1 = 2(k+1)-1$。对于新颜色集的一个 $(k+1)$ 元子集 $S$:

  • 若 $S$ 同时包含 $x_0$ 和 $x_1$,令 $F(S) = x_0$ 以及 $G(S) = x_1$;
  • 否则 $S$ 至多包含一种新颜色,从而至少包含 $k$ 种旧颜色;选取一个 $k$ 元子集 $U(S) \subseteq S \cap P$ 并令 $F(S) = f(U(S))$,$G(S) = g(U(S))$。

两个选择器均从各自的集合中选取颜色。设 $|S \cap T| \le r$。若 $S$ 和 $T$ 均包含 $x_0, x_1$,则 $F(S) = x_0 \ne x_1 = G(T)$。若它们之中恰有一个包含,则一种颜色是新的而另一种是旧的。若两者均不包含,则 $U(S) \cap U(T) \subseteq S \cap T$,因此 $|U(S) \cap U(T)| \le r$,且 $F(S) = f(U(S)) \ne g(U(T)) = G(T)$。将这 $2k+1$ 种颜色重新标记为 $\mathrm{Fin}(2(k+1)-1)$ 即可给出 $G(k+1,r)$ 的标准列表染色。$\square$

定理 1 的证明. 对 $k \ge 5$ 进行归纳:基础情形是引理 1,而取 $r = 2$ 的引理 2(其假设 $1 \le k$ 由于 $k \ge 5$ 而成立)将可染色性从 $k$ 传递至 $k+1$。$\square$

5. 讨论

结果 bipartite_subset_colorable_two_from_five 确立了对所有 $k \ge 5$,二部子集图 $G(k, 2)$ 从其标准列表中都是可染色的,从而给出了一致下界: $$r^*(k) \ge 3 \quad \text{for all } k \ge 5.$$

虽然这严格改进了先前已知的一致下界 $r^*(k) \ge 2$(由 $k \ge 2$ 时的 bipartite_subset_colorable_at_one 导出),但它仍未解决 arXiv:2610.42094 中提出的核心渐近问题。该论文的定理 1.3 证明了条件 $r^2 > 2(2k-1)\ln(2k-1)$ 保证了从标准列表中不可染色,表明 $r^*(k) = O(\sqrt{k \ln k})$。该论文指出,该界对于真正的最小 $r$ 未给出任何信息,这使得当 $k \to \infty$ 时是 $r^*(k) = \Theta(\sqrt{k \ln k})$ 还是 $r^*(k) = o(\sqrt{k \ln k})$ 仍为一个未决问题。

常数下界 $3$ 无法区分这些渐近态势。特别是,当前结果并没有确定 $r^*(k)$ 是随 $k$ 无界增长,还是被某个绝对常数所界定。确定当 $k \to \infty$ 时是否有 $r^*(k) \to \infty$,是回答 arXiv:2610.42094 中问题的关键一步。

紧接着的下一个参数值是 $r = 3$。确定对于较大的 $k$——乃至对于诸如 $k = 5$ 或 $k = 6$ 的特定值——$G(k, 3)$ 是否容许正常的标准列表染色,仍然是未决的。然而,在阈值 $r = 3$ 处寻找染色面临着非平凡的对称性阻碍。在 op861_no_right_equivariant_k6_r3 中证明了,对于 $k = 6$(此时基础集有 $2k - 1 = 11$ 种颜色),在 $\binom{\mathrm{Fin}(11)}{6}$ 上不存在两个颜色选择函数,使得二者均选择可用颜色、只要 $|S \cap T| \le 3$ 就取不同值,并且第二个选择器满足循环等变性: $$c_B(T + d) = c_B(T) + d \quad \text{for all } d \in \mathbb{Z}_{11}.$$ 由于该问题在交换 $A$ 和 $B$ 下是对称的,因此 $G(6,3)$ 的标准列表染色(如果存在的话)的两个选择器都无法与所有循环平移对易。引理 1 的规则在 $\mathbb{Z}_9$ 上是平移不变的(在若干个容许的 $i$ 之间的选择除外),因此它在 $k = 6$,$r = 3$ 处的直接类似物必须打破这种对称性。

在 $r = 3$ 之外,建立随 $k$ 增长的 $r^*(k)$ 的非平凡下界,以及缩小常数下界($r^*(k) \ge 3$)与来自 arXiv:2610.42094 的上界(即满足 $r^2 > 2(2k-1)\ln(2k-1)$ 的最小整数 $r$)之间的差距,仍然是一个悬而未决的挑战。根据引理 2,对于某个 $k_0$ 的 $G(k_0, r)$ 的染色可以解决该阈值下所有更大的 $k$,因此增长的下界归结为一系列阈值 $r$ 的基础情形 $G(k_r, r)$;引理 1 的规则——顶点选择一种颜色 $i$,使其在固定窗口 $N(i)$ 内围绕 $i$ 是稠密的——正是此类基础情形的一个候选模式。

为什么是研究级成果

  • Gives the uniform lower bound of three on the least uncolorable intersection threshold for every k at least five

Lean 声明

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2610.42094 — A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。