圈加孤立点在圈长至少为 $k((k-1)^2+1)$ 时是 $k$-紧的
low tier2026-11-12OP-193审阅: Claude CodeEnglish
摘要
对于 $k \ge 3$ 以及 $m \ge 4k-3$,arXiv:2610.17884 询问了一个 $m$-圈与一个孤立点的不相交并 $C_m \sqcup K_1$ 是否是 $k$-紧的($k$-tight),即其稳定 Kneser 图(stable Kneser graph)$\operatorname{KG}(C_m \sqcup K_1, k)$(其顶点为独立 $k$-元集,边连接不相交的集合)的色数是否为 $m-2k+3$。该论文称这是其猜想 1.3 中最简单的未决情形,并且仅在 $m$ 超过一个隐式阈值 $n_0(k)$ 时证明了该结论,该阈值由锚定颜色类与稳定 $k$-元集数量之间的计数比较所定义。我们证明了对于每个 $k \ge 3$ 以及每个 $m \ge k((k-1)^2+1)$,$C_m \sqcup K_1$ 都是 $k$-紧的,例如在 $k = 3$ 时从 $m = 15$ 起成立,在 $k = 4$ 时从 $m = 40$ 起成立。证明保留了该论文对非锚定颜色类的归约,但以不同方式找到了该类:根据图兰定理(Turán's theorem),对于至多包含 $k$ 个圈顶点的任意 $m-2k+2$ 个集合,圈的某个独立 $k$-元集与其中每个集合至多相交于一个顶点,因此圈的稳定 Kneser 图的任何最优染色都不可能使其所有颜色类都是锚定的。该结果在 Lean 4 中验证为 op_193_cubic_tight_if_cycle_lower,并将仅针对圈的经典下界 $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$ 作为假设。
1. 引言
给定一个具有 $n$ 个顶点的图 $G$ 和一个整数 $k \ge 1$,$G$-稳定 Kneser 图 $\operatorname{KG}(G,k)$ 以 $G$ 的独立 $k$-元集为顶点,当两个独立集不相交时相邻。标准染色给出 $\chi(\operatorname{KG}(G,k)) \le n-2k+2$,当等号成立时,$G$ 被称为 $k$-紧的。对于 $m$-圈而言,$\operatorname{KG}(C_m,k)$ 是施赖弗图(Schrijver graph, SG),关于它的经典定理表明当 $m \ge 2k$ 时 $C_m$ 是 $k$-紧的。
论文 arXiv:2610.17884 研究了哪些图是 $k$-紧的。该文指出,一个 $k$-紧图是路与圈的不相交并,其中所真包含的每个圈的长度至少为 $4k-3$,并且猜想了其逆命题(其猜想 1.3)。随后该文指出,即使圈定理未涵盖的最简单情形也是未决的:一个长度至少为 $4k-3$ 的圈加上一个孤立点。用该论文的话来说,“我们只能渐近地证明它”。因此问题在于:对于 $k \ge 3$ 以及 $m \ge 4k-3$,是否满足 $$\chi(\operatorname{KG}(C_m \sqcup K_1, k)) = (m+1) - 2k + 2 = m-2k+3 ?$$
该论文的渐近结果(其定理 1.4)在 $m \ge n_0(k)$ 时成立,其中 $n_0(k)$ 是使一个计数不等式成立的最小整数:$m-2k+2$ 乘以施赖弗图的锚定独立集的最大大小小于其顶点数。该论文没有给出 $n_0(k)$ 的闭形式。根据其对锚定集合的界,在 $k = 3$ 时的比较仅从圈长 $21$ 起成立,而对于较大的 $k$,它需要 $k^4$ 阶的圈长。
我们证明了该断言对于每个 $k \ge 3$ 以及每个 $m \ge k((k-1)^2+1)$ 成立,这是一个 $k^3$ 阶的阈值,在 $k = 3$ 时等于 $15$,在 $k = 4$ 时等于 $40$。该论证沿用了该论文通过非锚定颜色类的路径,但将对锚定类的计数替换为对圈顶点上的一个辅助图简短应用图兰定理。该定理为 op_193_cubic_tight_if_cycle_lower。其唯一假设 $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$ 是关于施赖弗图的经典定理,该定理尚未在 Lean 中形式化,在陈述中作为假设给出。
区间 $4k-3 \le m < k((k-1)^2+1)$ 中的两个小情形也得到了验证:$\chi(\operatorname{KG}(C_9 \sqcup K_1, 3)) = 6$(op_193_cycle_isolated_vertex_k3_m9),以及通过单独的情形分析得出的 $\chi(\operatorname{KG}(C_{10} \sqcup K_1, 3)) = 7$。对于 $k = 3$,圈长 $m = 11, \dots, 14$ 仍然未决。
2. 预备知识
定义 1(GStableKneser)。对于有限顶点类型 $V$ 上的简单图 $G$ 和 $k \in \mathbb{N}$,图 GStableKneser G k 以在 $G$ 中独立且满足 $|s| = k$ 的有限集 $s \subseteq V$ 为顶点,并在 $s \ne t$ 且 $s \cap t = \emptyset$ 时连接 $s$ 和 $t$。我们将其记为 $\operatorname{KG}(G,k)$。对于圈,$\operatorname{KG}(C_m,k)$ 是 $C_m$ 的稳定 $k$-元集上的施赖弗图 $\operatorname{SG}(m,k)$。
定义 2(圈加孤立点)。$C_m$ 是 Mathlib 中 $\operatorname{Fin} m$ 上的 SimpleGraph.cycleGraph m,孤立点是单点类型 Unit 上的空图 $\bot$。它们的不相交和 $C_m \sqcup K_1$ 具有顶点类型 $\operatorname{Fin} m \oplus \operatorname{Unit}$,且两部分之间没有边。我们将孤立点记为 $\infty$。$C_m \sqcup K_1$ 的独立 $k$-元集要么是圈的稳定 $k$-元集,要么是 $F \cup \{\infty\}$,其中 $F$ 是圈的稳定 $(k-1)$-元集。
定义 3($k$-紧性)。对于 $n = m+1$ 个顶点,当 $\chi(\operatorname{KG}(C_m \sqcup K_1,k)) = m-2k+3$ 时 $C_m \sqcup K_1$ 是 $k$-紧的;is_k_tight_cycle_sum_unit_iff 记录了在 $k \ge 3$ 和 $m \ge 4k-3$ 下对该定义的这一表述。Lean 中的色数取值于 $\mathbb{N}_\infty$,命题陈述中将其与强制转换到 $\mathbb{N}_\infty$ 的自然数进行比较。
定义 4(锚定类)。设 $c$ 是 $\operatorname{SG}(m,k)$ 的一个正常染色。若某个 $U \in \mathcal{A}$(称为锚)对每个 $W \in \mathcal{A}$ 均满足 $|U \cap W| \ge 2$,则颜色类 $\mathcal{A}$ 是锚定的。这是 arXiv:2610.17884 第 3 节中的概念。
所使用的已知事实。对于 $k \ge 3$、$m \ge 4k-3$ 的上界 $\chi(\operatorname{KG}(C_m \sqcup K_1,k)) \le m-2k+3$ 是 op_193_cycle_isolated_vertex_chromatic_le,而 op_193_cycle_isolated_vertex_k_tight_iff_ge 将紧性转化为仅需证明下界。Mathlib 中可用形式的图兰定理:一个没有大小为 $r+1$ 的团且具有 $m$ 个顶点的图至多有 $\frac{r-1}{2r} m^2$ 条边。
3. 主要结果
定理(op_193_cubic_tight_if_cycle_lower)。设 $k \ge 3$ 且 $m \ge k((k-1)^2+1)$。若 $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$,则 $$\chi(\operatorname{KG}(C_m \sqcup K_1, k)) = m-2k+3 .$$
在 Lean 中,该陈述接受 k m : ℕ,假设 3 ≤ k、k * ((k-1)^2+1) ≤ m 以及 ((m-2*k+2 : ℕ) : ℕ∞) ≤ (GStableKneser (SimpleGraph.cycleGraph m) k).chromaticNumber,并得出结论:GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k 的色数等于 m-2*k+3。该假设是施赖弗图上的经典定理,因此在数学上该结果是无条件的:对所有 $k \ge 3$ 以及 $m \ge k((k-1)^2+1)$,$C_m \sqcup K_1$ 都是 $k$-紧的。
证明的核心是可染色性断言 op_193_cubic_noncolorable_if_cycle_lower:在关于 $k$ 和 $m$ 的相同界下,若 $\operatorname{KG}(C_m,k)$ 不是 $(m-2k+1)$-可染色的,则 $\operatorname{KG}(C_m \sqcup K_1,k)$ 不是 $(m-2k+2)$-可染色的。它依赖于一个同样已证的避让引理:对于 $C_m$ 中至多包含 $k$ 个顶点的任意集合 $A_1, \dots, A_{m-2k+2}$,圈的某个稳定 $k$-元集 $S$ 对每个 $j$ 均满足 $|S \cap A_j| \le 1$。阈值仅通过多项式不等式 op_193_cubic_threshold_edge_gap 引入:对于实数 $k \ge 3$ 和 $m \ge k((k-1)^2+1)$, $$m^2 - 3(k-1)m - (m-2k+2)\,k(k-1)^2 > 0 .$$
与 arXiv:2610.17884 相比,该定理以显式阈值 $k((k-1)^2+1)$ 代替了 $n_0(k)$,给出了该论文的定理 1.4。它尚未达到猜想的范围 $m \ge 4k-3$。
theorem op_193_cubic_tight_if_cycle_lower (k m : ℕ) (hk : 3 ≤ k)
(hm : k * ((k-1)^2+1) ≤ m)
(hcycle : ((m-2*k+2 : ℕ) : ℕ∞) ≤ (GStableKneser (SimpleGraph.cycleGraph m) k).chromaticNumber) :
(GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber =
m-2*k+34. 证明
令 $q = m-2k+2$。证明分为四步:来自图兰定理的避让引理、一个非锚定颜色类、论文中从该类导向不可染色顶点的步骤,以及相匹配的上界。
步骤 1(避让)。设 $A_1, \dots, A_q$ 是 $C_m$ 中至多包含 $k$ 个顶点的集合。设 $H$ 为 $C_m$ 顶点上的图,其中 $x \ne y$ 在它们在圈上不相邻且没有 $A_j$ 同时包含二者时相邻。$H$ 的一个 $k$-团是 $C_m$ 的一个与每个 $A_j$ 至多相交于一个顶点的稳定 $k$-元集,因此只需证明 $H$ 具有一个 $k$-团即可。圈具有 $m(m-3)/2$ 对不相邻的顶点对,且每个 $A_j$ 至多包含 $k(k-1)/2$ 个对,因此 $$2|E(H)| \ge m(m-3) - q\,k(k-1).$$ 若 $H$ 没有 $k$-团,则取 $r = k-1$ 的图兰定理将给出 $2(k-1)|E(H)| \le (k-2)m^2$。将第一个不等式乘以 $k-1$ 并结合,可得 $$m^2 - 3(k-1)m - q\,k(k-1)^2 \le 0 ,$$ 由于 $q = m-2k+2$,这与 op_193_cubic_threshold_edge_gap 矛盾。该引理通过恒等式证明,其中 $d = m - k((k-1)^2+1) \ge 0$: $$m^2 - 3(k-1)m - (m-2k+2)k(k-1)^2 = k(k-2)^2 + d\,(k^2(k-2)+3) + d^2 ,$$ 其右边在 $k \ge 3$ 时为正。在 Lean 中,团界采用 Mathlib 的图兰定理,边计数在 $\mathbb{N}$ 上完成,最终的矛盾是在 $\mathbb{R}$ 上的非线性算术步骤。
步骤 2(非锚定类)。假设 $c$ 是 $\operatorname{KG}(C_m \sqcup K_1,k)$ 用 $q$ 种颜色的一个正常染色,并设 $c'$ 为其在圈的稳定 $k$-元集上的限制,这是 $\operatorname{SG}(m,k)$ 的一个正常 $q$-染色。若 $c'$ 的每个颜色类 $j$ 都有一个锚 $U_j$,则将步骤 1 应用于 $U_1, \dots, U_q$ 将给出一个对所有 $j$ 均满足 $|S \cap U_j| \le 1$ 的稳定 $k$-元集 $S$。但 $S$ 具有某种颜色 $j = c'(S)$,且其所在类的锚满足 $|S \cap U_j| \ge 2$。因此 $c'$ 的某个类 $j$ 不是锚定的。
步骤 3(孤立点无法被染色)。这是 arXiv:2610.17884 第 3 节的论证。根据假设,$\operatorname{SG}(m,k)$ 没有正常 $(q-1)$-染色。因此颜色为 $j$ 的某个 $U$ 与其它每种颜色的集合都不相交:否则颜色为 $j$ 的每个集合都可以用其邻居中缺失的某种颜色重新染色。颜色为 $j$ 的集合两两相交,所以这将给出一个正常 $(q-1)$-染色。由于类 $j$ 不是锚定的,颜色为 $j$ 的某个 $W$ 满足 $|U \cap W| \le 1$,并且由于 $U$ 与 $W$ 颜色相同,必有 $|U \cap W| = 1$。令 $F = U \setminus W$,这是圈的一个稳定 $(k-1)$-元集。与 $U$ 不相交的每个集合都与 $F$ 不相交,并且 $W$ 与 $F$ 不相交。因此圈中与 $F$ 不相交的稳定 $k$-元集涵盖了全部 $q$ 种颜色。此时 $F \cup \{\infty\}$ 是 $\operatorname{KG}(C_m \sqcup K_1,k)$ 的一个顶点,与所有这些集合都不相交,因此它没有剩余颜色可用,产生矛盾。步骤 2 和步骤 3 共同构成了引理 op_193_cubic_noncolorable_if_cycle_lower:$\operatorname{KG}(C_m \sqcup K_1,k)$ 不是 $q$-可染色的。
步骤 4(组合)。在 op_193_cubic_tight_if_cycle_lower 中,假设 $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$ 首先给出 $\operatorname{KG}(C_m,k)$ 不是 $(m-2k+1)$-可染色的。随后步骤 3 表明 $\operatorname{KG}(C_m \sqcup K_1,k)$ 不是 $(m-2k+2)$-可染色的,因此其在 $\mathbb{N}_\infty$ 中的色数严格大于 $m-2k+2$,从而至少为 $m-2k+3$。由 $k \ge 3$ 可得 $(k-1)^2+1 \ge 5$,因此 $m \ge 5k > 4k-3$,而使用了上界 op_193_cycle_isolated_vertex_chromatic_le 的 op_193_cycle_isolated_vertex_k_tight_iff_ge 将该下界转化为等式。
例如,在 $k = 3$ 时,该定理涵盖了所有 $m \ge 15$,其中 $\chi(\operatorname{KG}(C_m \sqcup K_1, 3)) = m-3$。在 $k = 4$ 时,它涵盖了所有 $m \ge 40$,其值为 $m-5$。
5. 讨论
该定理用显式的三次式 $k((k-1)^2+1)$ 代替了该论文渐近结果中的隐式阈值。这是对该论文定理 1.4 的加强,而不是对该问题的完全解决,该问题询问的是所有 $m \ge 4k-3$。除了 $k = 3$ 时两个已验证的情形(即 $m = 9$ 和 $m = 10$)之外,区间 $4k-3 \le m < k((k-1)^2+1)$ 仍未解决。
这一改进来自于找到非锚定类的方法。该论文界定了锚定类的大小,并需要 $q$ 个锚定类过小而无法覆盖所有稳定 $k$-元集。而避让引理则仅使用锚本身:大小为 $k$ 的 $q$ 个集合至多禁止 $q\binom{k}{2}$ 个对,然后图兰定理仍能给出一个与每个锚至多相交于一个顶点的稳定 $k$-元集。步骤 1 中的恒等式表明边不等式在 $d = 0$ 时已成立,并具有余量 $k(k-2)^2$,因此该方法的真实阈值略低于 $k((k-1)^2+1)$,但通过该论证其阶数仍为 $k^3$。
对于小圈,步骤 2 失效:它不可能对施赖弗图的每个最优染色都成立。op_193_nine_cycle_stable_triples_anchored_five_coloring 给出了 $C_9$ 的稳定三元集的一个正常 $5$-染色,其中每个类都是锚定的;对于具有 $7$ 种颜色的 $C_{11}$ 和具有 $8$ 种颜色的 $C_{12}$,也验证了每个类都锚定的类似染色。在这些圈长下,施赖弗图的某些最优染色没有非锚定类。在这些情况下证明紧性必须使用超出步骤 2 的方法,例如圈部分的哪些染色可以延拓到包含 $\infty$ 的集合上。$k = 3$ 时的 $m = 9$ 和 $m = 10$ 情形是通过直接验证解决的。
仍有两个问题。首先,一个更敏锐的避让论证——即利用锚的稳定性与圈结构而非仅仅其大小的论证——能否将阈值降低到 $k$ 的线性阶?其次,从 $\operatorname{KG}(C_{r+2} \sqcup K_1,k)$ 到 $\operatorname{KG}(C_r \sqcup K_1,k-1)$ 的步进同态 op_193_hom_cycle_step 是否有助于填补该区间?它将紧性从 $(m,k)$ 向下传递到 $(m-2,k-1)$。因为阈值随 $k$ 增长,这远离了该区间,因此需要一个反向的归约。最后,Lean 陈述假设了施赖弗图的下界,其拓扑证明尚未形式化。
为什么是研究级成果
- Conditional on the published cycle-only chromatic lower bound, gives the explicit sufficient cycle length m ≥ k((k−1)²+1) for the cycle-plus-isolated-vertex conjecture; the source paper proves the result only for an unspecified sufficiently large threshold
Lean 声明
- op_193_cubic_tight_if_cycle_lowerFor k at least 3 and m at least k((k-1)²+1), the stable k-set graph of the m-cycle plus an isolated vertex has chromatic number m-2k+3,…
- op_193_cycle_isolated_vertex_k3_m9The G-stable Kneser graph KG(C_9 ⊔ K_1, 3), where the base graph is the disjoint sum of the 9-cycle and an isolated vertex, has chromatic…
- is_k_tight_cycle_sum_unit_iffFor k ≥ 3 and m ≥ 4*k - 3, the disjoint sum of the m-cycle and an isolated vertex is k-tight if and only if the chromatic number of its…
- op_193_cycle_isolated_vertex_chromatic_leFor any natural numbers k ≥ 3 and m ≥ 4 * k - 3, the chromatic number of the G-stable Kneser graph of the disjoint sum of the m-cycle and…
- op_193_cycle_isolated_vertex_k_tight_iff_geFor k ≥ 3 and m ≥ 4*k - 3, the chromatic number of the G-stable Kneser graph of the disjoint sum of the m-cycle and an isolated vertex…
- op_193_cubic_noncolorable_if_cycle_lowerFor k at least 3 and m at least k((k-1)²+1), if the cycle-stable k-set graph is not (m-2k+1)-colorable, then adding an isolated vertex…
- op_193_cubic_threshold_edge_gapThe edge-count gap in the clique-free anchor argument is strictly positive at and beyond the cubic threshold.
- op_193_nine_cycle_stable_triples_anchored_five_coloringThe stable triples of the nine-cycle have a proper five-coloring in which every color class has an anchor intersecting each triple of the…
- op_193_hom_cycle_stepFor all integers k ≥ 2 and r ≥ 2 * k - 2, there exists a graph homomorphism from the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) to the…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2610.17884 — The chromatic number of $G$-stable Kneser graphs
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。