跳闭与跃闭边子集不构成拟阵的平坦集
low tier2026-10-26OP-302审阅: CodexEnglish
摘要
arXiv:2610.18463 中的问题 5.9 询问有限简单图的跳闭(跳极大)边子集族,或跃闭(跃极大)边子集族,是否构成其边集上某个拟阵的平坦集集合。对于生成子图 $H = G[F]$,跳极大性要求加入来自 $E(G) \setminus F$ 的任意边都会使该子图的跳数严格增加,而跃极大性要求加入来自 $E(G) \setminus F$ 的任意边都会使其跃群 $\Lambda_1(H)$ 严格扩大。我们表明对这两个概念的回答都是否定的:无论是跳闭边子集族还是跃闭边子集族,都不是对每个有限简单图都构成拟阵的平坦集集合。该反驳通过证明在三顶点完全图 $K_3$ 上,这两个族在交集运算下都不封闭来展开。具体而言,存在成对的跳闭(分别为跃闭)边子集,它们的交集不是跳闭(分别为跃闭)的。由于任何拟阵的平坦集族在交集运算下必然封闭,这种交集封闭性的失效证明了 $K_3$ 的边集上不存在任何以这两个族中任一族为平坦集的拟阵。所有定义、引理以及主反驳定理均已在 Lean 4 证明助手中形式化并验证。
1. 引言
在题为《The group generated by a graph's derangements》的 arXiv:2610.18463 中,问题 5.9 探讨了由与有限图相关的置换群作用所定义的子图族的组合与拟阵性质。设 $G = (V, E)$ 为有限简单图。对于任意边子集 $F \subseteq E$,生成子图 $G[F] = (V, F)$ 具有顶点集 $V$ 和边集 $F$。在该论文中,如果对于每条边 $e \in E \setminus F$,生成子图 $G[F \cup \{e\}]$ 的跳数都严格多于 $G[F]$ 的跳数,则边子集 $F \subseteq E$ 被定义为在 $G$ 中是跳极大的(或跳闭的)。类似地,如果对于每条边 $e \in E \setminus F$,跃群 $\Lambda_1(G[F \cup \{e\}])$ 都严格包含 $\Lambda_1(G[F])$,则 $F$ 被定义为在 $G$ 中是跃极大的(或跃闭的)。提出问题 5.9 时,该论文问道:
“这两个概念中的任一个是否能给出拟阵的平坦集?”
在拟阵论中,给定有限基集 $E$,子集族 $\mathcal{F} \subseteq \mathcal{P}(E)$ 当且仅当满足经典平坦集公理时,才构成拟阵 $M = (E, \mathcal{I})$ 的平坦集(或闭集)集合:基集 $E$ 属于 $\mathcal{F}$,$\mathcal{F}$ 中任意两个成员的交集属于 $\mathcal{F}$,且该族满足覆盖性质。特别地,平坦集 $F \in \mathcal{F}$ 具有如下性质:对每个元素 $e \in E \setminus F$,秩都严格增加,$r_M(F \cup \{e\}) > r_M(F)$。arXiv:2610.18463 中的问题询问对于每个有限简单图 $G = (V, E)$,跳闭边子集(或跃闭边子集)是否可以作为某个基集为 $E$ 的拟阵 $M$ 的平坦集出现。
问题 5.9 询问这些由图定义的族是否满足刻画拟阵平坦集的公理。我们采用生成子图解释:在移除边时保留环境图的所有顶点。在拟阵论中,交集封闭性是无条件的必要条件:在任何拟阵 $M$ 中,若 $F_1$ 和 $F_2$ 是平坦集,则它们的交集 $F_1 \cap F_2$ 也是平坦集。如果一个提议的子集族即使在单个图 $G$ 上不满足交集封闭性,它就无法构成 $G$ 的边集上任何拟阵的平坦集集合。
本博文通过定理 simple_graph_hop_or_leap_maximal_not_matroid_flats 呈现了对问题 5.9 的形式化反驳,该定理已在 Lean 4 中形式化并验证。该定理证明了无论是跳闭边子集还是跃闭边子集,都不是对每个有限简单图都构成拟阵的平坦集。
证明确立了三个顶点上的完全图 $K_3$ 可作为这两种性质的反例。具体而言:
- 引理
simple_graph_completeGraph_three_hop_closed_not_intersection_closed证明了 $K_3$ 的跳闭边子集族在交集运算下不封闭。 - 引理
simple_graph_completeGraph_three_leap_closed_not_intersection_closed证明了 $K_3$ 的跃闭边子集族在交集运算下不封闭。
结合拟阵论的一般引理 matroid_isFlat_inter(其指出两个平坦集的交集始终是平坦集),这些反例排除了存在以 $K_3$ 的跳闭或跃闭边集为平坦集的拟阵的可能性,从而对问题 5.9 的两个部分都给出了否定的解答。
2. 预备知识
我们在有限简单图和拟阵的背景下展开工作。设 $V$ 为类型,并设 $G$ 为 $V$ 上的简单图,在 Lean 中由类型为 $\text{SimpleGraph } V$ 的项表示。$G$ 的边集记作 $G.\text{edgeSet}$,它是对称二阶幂 $\text{Sym2 } V$ 的子集,后者表示 $V$ 中元素的无序对集合。给定边子集 $F \subseteq E(G)$,$G$ 的边集为 $F$ 的生成子图记作 $G[F] = (V, F)$,在 Lean 中对应于 $\text{SimpleGraph.fromEdgeSet } F$。
图 $H$ 的一个跳是其整个顶点集的一个置换 $h$,使得对每个顶点 $v$,$v$ 和 $h(v)$ 都是相邻的。因为我们考虑的图没有自环,所以每个跳都没有不动点。特别地,孤立顶点的存在排除了所有跳。跃群 $\Lambda_1(H)$ 是由这些跳生成的置换群的子群。若不存在跳,则这个生成的子群是平凡群,它仍然包含单位元。跳的空集与平凡跃群之间的区别贯穿了整个反例。
定义 1(simple_graph_is_hop_closed)。设 $V$ 为有限类型,并设 $G$ 为 $V$ 上的简单图,其边集为 $E(G) = G.\text{edgeSet} \subseteq \text{Sym2 } V$。若边子集 $F \subseteq \text{Sym2 } V$ 满足 $F \subseteq E(G)$,且对每条边 $e \in E(G) \setminus F$,生成子图 $G[F \cup \{e\}]$ 的跳数严格大于 $G[F]$ 的跳数,则称 $F$ 在 $G$ 中是跳闭的(或跳极大的),记作 simple_graph_is_hop_closed: $$F \subseteq G.\text{edgeSet} \wedge \forall e \in G.\text{edgeSet} \setminus F, \; \text{Nat.card} \{ h : \text{Equiv.Perm } V \mid \text{simple\_graph\_is\_hop } (G[F]) \; h \} < \text{Nat.card} \{ h : \text{Equiv.Perm } V \mid \text{simple\_graph\_is\_hop } (G[F \cup \{e\}]) \; h \},$$ 其中 $G[F] = \text{SimpleGraph.fromEdgeSet } F$ 且 $G[F \cup \{e\}] = \text{SimpleGraph.fromEdgeSet } (\text{insert } e \; F)$。
*注 1。* 在定义 1 中,比较跳数的不等式是严格的($<$):添加 $F$ 之外的任意边必须使作为跳的置换子类型的基数严格增加。顶点类型 $V$ 配备了 $\text{Fintype } V$ 实例,确保置换群 $\text{Equiv.Perm } V$ 是有限的,并且计数是良定义的自然数。顶点集 $V$ 在整个过程中保持固定,而边集则通过添加单条边 $e \in G.\text{edgeSet} \setminus F$ 而变化。
定义 2(simple_graph_is_leap_closed)。设 $V$ 为一个类型,并设 $G$ 为 $V$ 上的简单图,其边集为 $E(G) = G.\text{edgeSet} \subseteq \text{Sym2 } V$。若边子集 $F \subseteq \text{Sym2 } V$ 满足 $F \subseteq E(G)$,且对每条边 $e \in E(G) \setminus F$,生成子图 $G[F]$ 的跃群被严格包含在生成子图 $G[F \cup \{e\}]$ 的跃群中,则称 $F$ 在 $G$ 中是跃闭的(或跃极大的),记作 simple_graph_is_leap_closed: $$F \subseteq G.\text{edgeSet} \wedge \forall e \in G.\text{edgeSet} \setminus F, \; \text{simple\_graph\_leap\_group } (G[F]) < \text{simple\_graph\_leap\_group } (G[F \cup \{e\}]),$$ 其中 $<$ 表示 $\text{Equiv.Perm } V$ 的子群完备格中的严格包含关系,且 $G[F] = \text{SimpleGraph.fromEdgeSet } F$ 以及 $G[F \cup \{e\}] = \text{SimpleGraph.fromEdgeSet } (\text{insert } e \; F)$。
*注 2。* 在定义 2 中,序关系是置换子群格中的严格不等式($<$),意味着 $\text{simple\_graph\_leap\_group } (G[F])$ 是 $\text{simple\_graph\_leap\_group } (G[F \cup \{e\}])$ 的真子群。在 Lean 中,该定义在其签名中不需要 $\text{Fintype } V$,因为子群包含关系对任意类型均有定义。对于问题 5.9 中对有限图的应用,$V$ 是有限类型。
定义 3(拟阵平坦集与交集封闭性)。设 $\alpha$ 为有限类型,并设 $M$ 为基集 $M.E \subseteq \alpha$ 上的拟阵。若子集 $F \subseteq \alpha$ 满足 $F \subseteq M.E$ 且 $F$ 的拟阵闭包满足 $\text{cl}_M(F) = F$,则称 $F$ 为 $M$ 的平坦集,在 Lean 中记作 $M.\text{IsFlat } F$。等价地,$F$ 为平坦集,当且仅当对于每个元素 $x \in M.E \setminus F$,$F \cup \{x\}$ 的秩都严格大于 $F$ 的秩。引理 matroid_isFlat_inter 确立了任何拟阵的平坦集集合在二元交集运算下封闭: $$\forall (F_1 \, F_2 : \text{Set } \alpha), \; M.\text{IsFlat } F_1 \to M.\text{IsFlat } F_2 \to M.\text{IsFlat } (F_1 \cap F_2).$$
*注 3。* 在图的语境下,环境类型为 $\alpha = \text{Sym2 } V$,且拟阵的基集固定为 $G$ 的边集,即 $M.E = G.\text{edgeSet}$。在 Lean 的 Mathlib 拟阵库中,$M.\text{IsFlat } F$ 蕴含 $F \subseteq M.E$,这与定义 1 和定义 2 中 $F \subseteq G.\text{edgeSet}$ 的要求一致。在交集运算下的封闭性是拟阵论中对所有拟阵均成立的无条件定理。
3. 主要结果
在 Lean 4 中确立的主要结果是对 arXiv:2610.18463 的问题 5.9 针对跳闭和跃闭边子集两方面的反驳。
定理(simple_graph_hop_or_leap_maximal_not_matroid_flats)。 对于任意有限简单图 $G$,跳闭边子集族和跃闭边子集族都不构成拟阵的平坦集集合。具体而言,以下两个全称陈述都是错误的:
1. 并非对每个具有可判定相等性的有限类型 $V$ 以及 $V$ 上的每个简单图 $G$,都存在 $\text{Sym2 } V$ 上以 $M.E = G.\text{edgeSet}$ 为基集的拟阵 $M$,其平坦集恰好是 $G$ 的跳闭边子集: $$\neg \left( \forall \{V : \text{Type}\} \; [\text{Fintype } V] \; [\text{DecidableEq } V] \; (G : \text{SimpleGraph } V), \; \exists (M : \text{Matroid } (\text{Sym2 } V)), \; M.E = G.\text{edgeSet} \wedge \forall F, M.\text{IsFlat } F \leftrightarrow \text{simple\_graph\_is\_hop\_closed } G \; F \right).$$ 2. 并非对每个具有可判定相等性的有限类型 $V$ 以及 $V$ 上的每个简单图 $G$,都存在 $\text{Sym2 } V$ 上以 $M.E = G.\text{edgeSet}$ 为基集的拟阵 $M$,其平坦集恰好是 $G$ 的跃闭边子集: $$\neg \left( \forall \{V : \text{Type}\} \; [\text{Fintype } V] \; [\text{DecidableEq } V] \; (G : \text{SimpleGraph } V), \; \exists (M : \text{Matroid } (\text{Sym2 } V)), \; M.E = G.\text{edgeSet} \wedge \forall F, M.\text{IsFlat } F \leftrightarrow \text{simple\_graph\_is\_leap\_closed } G \; F \right).$$
在 Lean 的陈述中,该定理被构造成两个命题的合取,每个命题分别指出:在所有具有可判定相等性的有限顶点类型 $V$ 和 $V$ 上的所有简单图 $G$ 上,不存在环境类型 $\text{Sym2 } V$ 上以 $M.E = G.\text{edgeSet}$ 为基集的拟阵 $M$,其平坦集与应用于 $G$ 的 simple_graph_is_hop_closed 一致(在第一个合取项中)或与应用于 $G$ 的 simple_graph_is_leap_closed 一致(在第二个合取项中)。
形式化中的每个辅助结果都为该反驳贡献了必要的组成部分:
simple_graph_completeGraph_three_hop_closed_not_intersection_closed证明了三顶点完全图 $K_3 = (\top : \text{SimpleGraph } (\text{Fin } 3))$ 的跳闭边子集族在交集运算下不封闭,给出了边子集 $F_1, F_2 \subseteq E(K_3)$,它们是跳闭的,而它们的交集 $F_1 \cap F_2$ 则不是。simple_graph_completeGraph_three_leap_closed_not_intersection_closed证明了三顶点完全图 $K_3 = (\top : \text{SimpleGraph } (\text{Fin } 3))$ 的跃闭边子集族在交集运算下不封闭,给出了边子集 $F_1, F_2 \subseteq E(K_3)$,它们是跃闭的,而它们的交集 $F_1 \cap F_2$ 则不是。matroid_isFlat_inter提供了拟阵论性质:拟阵中任意两个平坦集的交集仍是平坦集,从而将 $K_3$ 上交集封闭性的失效转化为对任何此类拟阵存在性的反驳。
theorem simple_graph_hop_or_leap_maximal_not_matroid_flats : (¬ ∀ {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V), ∃ (M : Matroid (Sym2 V)), M.E = G.edgeSet ∧ ∀ F, M.IsFlat F ↔ simple_graph_is_hop_closed G F) ∧ (¬ ∀ {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V), ∃ (M : Matroid (Sym2 V)), M.E = G.edgeSet ∧ ∀ F, M.IsFlat F ↔ simple_graph_is_leap_closed G F)
4. 证明
反例是固定顶点集 $V=\{0,1,2\}$ 上的三角形。记连接 $i$ 与 $j$ 的无序边为 $e_{ij}$。它的三条边是 $e_{01},e_{02},e_{12}$。我们首先计算其相关生成子图的跳,然后使用拟阵平坦集必需的交集公理。该论证仅需要含两条边的路径和含一条边的图;不需要在更大的图上进行搜索,也不需要验证拟阵交换公理。
三顶点路径上的跳。 考虑边集为 $\{e_{01},e_{12}\}$ 的路径。顶点 $0$ 和 $2$ 都以 $1$ 作为它们唯一的邻点。因此,一个跳必须满足 $h(0)=h(2)=1$,这与单射性矛盾。因此该路径没有跳。相同的论证适用于三角形的每个双边生成子图:它的两个叶节点都必须映射到其中间顶点。单边生成子图也没有跳,因为它的第三个顶点是孤立的。这些结论均涉及所有三个顶点的置换,包括在孤立顶点存在时的情形。
三角形上的跳。 完全图 $K_3$ 上的跳恰好是没有不动点的三顶点置换。恰好存在两个这样的置换,即轮换 $(0\;1\;2)$ 和 $(0\;2\;1)$。每一个都将每个顶点映到另一个不同的顶点,因而是邻点。所有其他置换都有不动点,不能成为跳。因此,当插入任意双边路径的缺失边时,跳数从零增加到二。相对于 $K_3$,每条路径都只有一条缺失边,因此这验证了该路径成为跳闭子集所需的每一次插入。
跳闭见证。 形式化跳引理使用了 $$F_1=\{e_{01},e_{12}\},\qquad F_2=\{e_{12},e_{02}\}.$$ 每一个都是路径,因此根据前面的计数,每一个在 $K_3$ 中都是跳闭的。它们的交集是 $S=\{e_{12}\}$。将缺失的边 $e_{01}$ 插入 $S$ 中。$G[S]$ 和 $G[S\cup\{e_{01}\}]$ 的跳数都为零:前者有一个孤立顶点,而后者是一条路径。因此跳闭性所要求的严格不等式将是 $0<0$。这是错误的,故 $S$ 不是跳闭的。只要有一次插入失败,就足以反驳要求对每条缺失边都严格增加的条件。
这就是 simple_graph_completeGraph_three_hop_closed_not_intersection_closed 的内容。其 Lean 证明命名了三条边和两个有限边集,验证了每个见证都包含在三角形的边集中,并确定了每条路径唯一的缺失边。随后通过对 Fin 3 的置换进行有限计算来检查跳数零和二。对于交集,相同的计算在插入所选边之前和之后都给出零。该证明对这些小计数使用了经内核检查的有限判定。
跃闭见证。 跃引理使用了一对重新标号的路径: $$L_1=\{e_{01},e_{02}\},\qquad L_2=\{e_{01},e_{12}\},\qquad L_1\cap L_2=\{e_{01}\}.$$ 这两条路径都没有跳,因此它们的跃群都是平凡群。$K_3$ 的跃群是非平凡的:置换 $0\mapsto1\mapsto2\mapsto0$ 是一个跳,因此属于由跳生成的子群,并且它不同于恒等映射。因此,插入任一路径唯一的缺失边都会使其跃群从平凡群严格扩大为非平凡群。这证明了 $L_1$ 和 $L_2$ 是跃闭的。
它们的交集不是跃闭的。含边 $e_{01}$ 的单边生成图具有孤立顶点,因而具有平凡跃群。插入 $e_{02}$ 得到路径 $L_1$,其跃群同样是平凡的。在这两个相等的群之间不存在严格的子群包含关系。这在对应的缺失边处违反了定义条件。
simple_graph_completeGraph_three_leap_closed_not_intersection_closed 的 Lean 证明直接遵循了这一论证。它通过在叶节点处使用置换的单射性证明了两条路径都没有跳,并通过观察其孤立顶点证明了单边图没有跳。随后证明了由跳的空集生成的子群是底子群。对于完全图,它给出了旋转置换作为跃群的非单位元成员。这里只需要非平凡性;形式化证明无需枚举对称群的子群,也不需要三角形跃群的精确描述。
拟阵阻碍。 若 $A$ 和 $B$ 是拟阵 $M$ 的平坦集,则它们的交集也是平坦集。理解这一点的一种方法是将平坦集写成拟阵闭包算子的不动点。单调性给出 $$\operatorname{cl}_M(A\cap B)\subseteq\operatorname{cl}_M(A)\cap\operatorname{cl}_M(B)=A\cap B.$$ 由于 $A\cap B$ 落在基集中,扩张性给出了反向包含。因此 $\operatorname{cl}_M(A\cap B)=A\cap B$。形式化引理 matroid_isFlat_inter 从平坦集群交集的库定理中获得了该性质,应用于由两个元素索引的族。
现在假设三角形边集上的某个拟阵恰好以跳闭子集为其平坦集。那么 $F_1$ 和 $F_2$ 都将是平坦集,从而 $F_1\cap F_2$ 也将是平坦集。由所假设的族相等性,它们的交集应是跳闭的,这与上述见证相矛盾。使用 $L_1,L_2$ 的论证对跃闭子集给出了同样的矛盾。
最后,声称对每个有限简单图都存在此类拟阵的全称断言同样适用于 $K_3$。因此,这两个矛盾分别反驳了这两个全称断言。定理 simple_graph_hop_or_leap_maximal_not_matroid_flats 将这些反驳打包为一个合取式。其 Lean 证明将每个提议的全称断言特化为 Fin 3 上的完全图,将两个见证的封闭性转移为平坦性,应用 matroid_isFlat_inter,再将交集的平坦性转回以得出矛盾。基集是三角形的边集;环境类型 Sym2 (Fin 3) 仅是无序顶点对的表示。
5. 讨论
在本文所使用的生成子图解释下,该结果对 arXiv:2610.18463 的问题 5.9 的两个备选方案都给出了否定回答。阻碍在三个顶点上就已经显现:两条路径各自可以要求加入每条缺失边以产生跳或扩大跃群,而它们的公共单条边却不具备这一性质。
这种行为也解释了为什么图定义中的“闭(closed)”一词本身并不提供闭包算子。检验每次单边扩充的条件在交集运算下未必保持。在这里,两条边合在一起距离支持一个跳仅差一步,而单条边距离支持跳则差得更远。两条路径都通过了扩充检验,而它们的交集却未能通过。跃群版本具有相同的阻碍,因为证明中使用的所有真生成子图都具有平凡跃群。
该定理反驳了针对所有有限简单图的断言。它没有对哪些特定图允许存在以任一规定族为平坦集的拟阵进行分类。它也没有断言交集封闭性的失效发生在每一个图中。对环境图提出的任何限制都需要单独的论证。类似地,在移除边时改变顶点集,或允许生成元固定顶点的变体,使用的是不同的定义,不在本形式化的涵盖范围内。
不需要针对三角形检验其余的拟阵平坦集公理:一个必要公理的失效就已经排除了这两个提议的族。事实上,同样的失效也排除了它们作为边集上任何普通闭包算子的不动点集的可能性,因为此类不动点集在交集运算下也必须封闭。
为什么是研究级成果
- refutes OP-302 (Matroid flats from hop-maximal and leap-maximal subgraphs)
Lean 声明
- simple_graph_hop_or_leap_maximal_not_matroid_flatsNeither the collection of hop-closed edge subsets nor the collection of leap-closed edge subsets forms the set of flats of a matroid for…
- simple_graph_completeGraph_three_hop_closed_not_intersection_closedThe collection of hop-closed edge subsets of the complete graph K₃ on 3 vertices is not closed under intersection.
- simple_graph_completeGraph_three_leap_closed_not_intersection_closedThe collection of leap-closed edge subsets of the complete graph K₃ on 3 vertices is not closed under intersection.
- matroid_isFlat_interIn any matroid M, if F₁ and F₂ are flats of M, then their intersection F₁ ∩ F₂ is also a flat of M.
- simple_graph_is_hop_closedAn edge subset F of a finite simple graph G is hop-closed (hop-maximal) if F is a subset of the edge set of G and for every edge e in E(G)…
- simple_graph_is_leap_closedAn edge subset F of a simple graph G is leap-closed (leap-maximal) if F is a subset of the edge set of G and for every edge e in E(G) \ F,…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2610.18463 — The group generated by a graph's derangements
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Codex 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。