AFTD Auto-Formalizing Theoretical Domains

Research Blogs

非邻域具有核的定向图中拟核的加权半覆盖

medium tier2026-11-05OP-337审阅: Claude CodeEnglish

摘要

小拟核猜想探讨是否每个有限无源有向图都存在一个顶点数至多为其一半的拟核。arXiv:2610.23487证明了,只要一个无源有向图的顶点的每个非负整数权重赋值都允许存在一个其闭出邻域包含至少一半总权重的拟核,则该有向图就满足这一界限,并将此结果应用于已知此类加权定理成立的break有向图。我们对每个顶点非邻域均诱导出具有核的有向图的有限无自环定向图,证明了这一加权半覆盖性质。该图类包含所有竞赛图以及所有定向完全多部图,并且包含不属于break有向图的定向图。证明选取了一个入权重最小的顶点(若平局则以入度打破):该顶点与其非邻域的一个核一起构成一个拟核,因为否则它的某个入邻点将具有更小的得分,且在定向图中最小入权重至多为总权重的一半。结合arXiv:2610.23487中未在此形式化的迁移定理,这给出了该类中每个无源有向图的半阶界。该定理及其引理已在Lean 4中得到检验。

1. 引言

在有向图理论中,有向图 $D = (V, E)$ 中的独立集是指其任意两个元素之间都没有有向弧的顶点子集。出核(或简称为核)是一个出支配 $V \setminus K$ 的独立集 $K \subseteq V$,这意味着对于每个 $v \in V \setminus K$,都存在 $u \in K$ 使得 $(u, v) \in E$。虽然由于奇有向圈的阻碍,核并不存在于所有有向图中,但一个经典定理保证了每个有限有向图都包含一个拟核:一个独立集 $Q \subseteq V$,使得 $V$ 中的每个顶点都可以从 $Q$ 通过长度至多为 2 的有向路径到达。

在 arXiv:2610.23487 中,猜想 1.1 提出了小拟核猜想:每个没有源(即每个顶点的入度至少为 1)的有限无自环有向图 $D = (V, E)$ 都包含一个满足 $|Q| \le |V|/2$ 的拟核 $Q$。无源条件是不可或缺的,因为 $D$ 的每个源点都必须属于每个拟核,因此具有超过 $|V|/2$ 个源点的图不可能拥有大小至多为 $|V|/2$ 的拟核。

arXiv:2610.23487 将该猜想与一种加权覆盖性质联系起来。给定一个非负整数权重函数 $w : V \to \mathbb{N}$,如果拟核 $Q$ 的闭出邻域 $N^+[Q] = \{v \in V \mid \exists q \in Q, q = v \vee (q, v) \in E\}$ 承载了至少一半的总权重: $$\sum_{v \in N^+[Q]} w(v) \ge \frac{1}{2} \sum_{v \in V} w(v).$$ 则称 $Q$ 对 $w$ 是半覆盖的。其定理 1.3 指出,如果一个无源有向图的每个权重函数都存在一个半覆盖拟核,则该图包含一个大小至多为 $\lfloor |V|/2 \rfloor$ 的拟核;其证明是一个保持邻域的选择论证结合匹配的交错路论证。该论文利用早期文献中针对该图类的加权邻域定理,将此应用于break有向图——即顶点集划分为一个诱导无圈有向图的部分和一个诱导竞赛图的部分的定向图,从而证明了该猜想对无源break有向图成立。

在这项工作中,我们对另一类图证明了加权半覆盖性质:对于每个顶点 $v$,既不是 $v$ 的入邻点也不是其出邻点的顶点诱导出一个具有核的有向图的有限无自环定向图(定理 digraph_nonneighborhood_kernels_weighted_half_cover)。该图类包含所有竞赛图(其中所有这些非邻域均为空),以及所有定向完全多部图(其中 $v$ 的非邻域为其所在部的其余顶点,这是一个独立集,因而也是它自己的核)。该图类不包含在break有向图类中:在由一个有向三角形将每个顶点替换为两个不相邻副本所得到的有向图中,竞赛图部分至多包含每个原顶点的一个副本,因此另一部分包含每个原顶点的一个副本,从而包含一个有向三角形。该图类也不包含break有向图:有向三角形加上一个与其所有顶点均不相邻的额外顶点是一个break有向图,但该额外顶点的非邻域就是这个没有核的有向三角形。

2. 预备知识

我们在 Lean 的设置下形式化有限有向图及其加权性质。

定义 1(有限无自环有向图)。设 $\alpha$ 为具有可判定相等性的有限类型。顶点集 $\alpha$ 上的有向图 $D$ 由具有可判定关系的邻接关系 $D.Adj : \alpha \to \alpha \to \text{Prop}$ 指定。如果 $\forall v \in \alpha, \neg D.Adj\ v\ v$,则该图是无自环的。

定义 2(定向图)。如果无自环有向图 $D$ 不包含有向 2-圈,则称其为定向图: $$\forall u, v \in \alpha, \quad D.Adj\ u\ v \implies \neg D.Adj\ v\ u.$$

定义 3(邻域与入度)。对于顶点 $v \in \alpha$,其开入邻域为 $N^-(v) = \{u \in \alpha \mid D.Adj\ u\ v\}$。其开出邻域为 $N^+(v) = \{u \in \alpha \mid D.Adj\ v\ u\}$。对于任意子集 $Q \subseteq \alpha$,其闭出邻域为: $$N^+[Q] = \{v \in \alpha \mid \exists q \in Q, q = v \vee D.Adj\ q\ v\}.$$

定义 4(非邻域与非邻域出核)。对于任意顶点 $v \in \alpha$,其非邻域由所有既非 $v$ 的入邻点也非出邻点的顶点 $x \in \alpha \setminus \{v\}$ 组成: $$x \ne v \wedge \neg D.Adj\ x\ v \wedge \neg D.Adj\ v\ x.$$ 该非邻域的一个出核是满足以下三个条件的子集 $K \subseteq \alpha$:

  1. 每个元素 $x \in K$ 都属于 $v$ 的非邻域:$x \ne v \wedge \neg D.Adj\ x\ v \wedge \neg D.Adj\ v\ x$。
  2. $K$ 在 $D$ 中是独立集:$\forall x, y \in K, x \ne y \implies \neg D.Adj\ x\ y$。
  3. $K$ 出支配该非邻域:对于满足 $\neg D.Adj\ x\ v$ 且 $\neg D.Adj\ v\ x$ 的每个 $x \ne v$,存在 $k \in K$ 使得 $k = x$ 或 $D.Adj\ k\ x$。

局部假设断言,对于每个 $v \in \alpha$,都存在这样一个非邻域出核 $K$。

定义 5(拟核)。如果子集 $Q \subseteq \alpha$ 在 $D$ 中是独立的,并且 $\alpha$ 中的每个顶点都可以从 $Q$ 通过长度至多为 2 的有向路径到达,则称 $Q$ 为 $D$ 的拟核: $$\forall v \in \alpha, \quad \exists q \in Q, \quad q = v \vee D.Adj\ q\ v \vee (\exists z \in \alpha, D.Adj\ q\ z \wedge D.Adj\ z\ v).$$

定义 6(权重与入权重)。权重函数是映射 $w : \alpha \to \mathbb{N}$。$\alpha$ 的总权重为 $W = \sum_{v \in \alpha} w(v)$。对于任意顶点 $v \in \alpha$,其入权重为: $$w^-(v) = \sum_{u \in N^-(v)} w(u).$$ 对于任意子集 $S \subseteq \alpha$,其权重为 $w(S) = \sum_{v \in S} w(v)$。

定义 7(全预序)。类型 $A$ 上的全预序(TotalPreorder)是指其关系 $\le$ 满足完全性的预序:$\forall a, b \in A, a \le b \vee b \le a$。实例 LinearOrder.toTotalPreorder 注册了每个线性序都是全预序。

关于形式化选择的注记: 权重函数 $w$ 定义为取值于自然数集 $\mathbb{N}$。为了避免有理数分数和舍入,半权重条件表示为整数不等式: $$\sum_{v \in \alpha} w(v) \le 2 \sum_{v \in N^+[Q]} w(v).$$ 若 $\alpha$ 为空,则两个求和的值均为 0,且不等式在 $Q = \emptyset$ 时显然成立。局部假设仅要求每个非邻域至少存在一个出核,而不要求唯一性。

3. 主要结果

本工作形式化的主要定理是 digraph_nonneighborhood_kernels_weighted_half_cover。

定理(digraph_nonneighborhood_kernels_weighted_half_cover)。 设 $D$ 是顶点集 $\alpha$ 上的有限无自环定向图。假设对于每个顶点 $v \in \alpha$,$v$ 的诱导非邻域都包含一个出核。那么对于每个非负整数权重赋值 $w : \alpha \to \mathbb{N}$,都存在一个拟核 $Q \subseteq \alpha$,使得 $Q$ 的闭出邻域包含至少一半的总权重: $$\sum_{v \in \alpha} w(v) \le 2 \sum_{v \in N^+[Q]} w(v).$$

在 Lean 中,定理 digraph_nonneighborhood_kernels_weighted_half_cover 接受有限类型 $\alpha$、具有可判定邻接关系的有向图 $D$、表明 $D$ 无自环且为定向图以及每个顶点的非邻域中都存在出核的假设,以及权重函数 $w$ 作为参数,并断言存在 $\alpha$ 的一个有限子集,该子集是独立的,构成一个拟核,并且满足对所有顶点的二倍求和不等式。

该定理得到了若干辅助结果的支持:

  • 引理 digraph_nonneighbor_kernel_or_dominating_vertex 确立了一个关键的结构二歧性:对于任意顶点 $s$ 及其非邻域的任意出核 $K$,要么 $\{s\} \cup K$ 是 $D$ 的拟核,要么存在一个指向 $s$ 的不同顶点 $t$,其入邻域完全包含在 $s$ 的入邻域内。
  • 一对得分编码引理确立了复合得分函数 $w^-(v) \cdot M + |N^-(v)|$ 保真地实现了字典序比较,因此在顶点上最小化得分会先最小化入权重,再最小化入度。
  • 一个覆盖权重引理表明,只要独立集 $\{s\} \cup K$ 覆盖了所有不指向 $s$ 的顶点,$\{s\} \cup K$ 的闭出邻域漏掉的权重就至多为入权重 $w^-(s)$。
  • 定向图的二重和不等式确立了弧权重的二重和至多为总权重平方的一半,这意味着任何具有最小入权重的顶点的入权重至多为 $W / 2$。

主定理除 digraph_nonneighbor_kernel_or_dominating_vertex 和这些辅助引理之外,没有使用其他形式化结果。

定理 digraph_nonneighborhood_kernels_weighted_half_cover (Lean 4 已验证)
theorem digraph_nonneighborhood_kernels_weighted_half_cover
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj]
    (hloop : ∀ v, ¬ D.Adj v v)
    (horient : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (hlocal : ∀ v, ∃ K : Finset α,
      (∀ x ∈ K, x ≠ v ∧ ¬ D.Adj x v ∧ ¬ D.Adj v x) ∧
      (∀ x ∈ K, ∀ y ∈ K, x ≠ y → ¬ D.Adj x y) ∧
      (∀ x, x ≠ v → ¬ D.Adj x v → ¬ D.Adj v x →
        ∃ k ∈ K, k = x ∨ D.Adj k x)) (w : α → ℕ) :
    ∃ Q : Finset α,
      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧
      (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ z, D.Adj u z ∧ D.Adj z v) ∧
      (∑ v ∈ Finset.univ, w v) ≤
        2 * (∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v)

4. 证明

现在我们给出 digraph_nonneighborhood_kernels_weighted_half_cover 的证明。

总体思路是极值选取。在定向图中,平均入权重至多为总权重的一半。如果我们选取一个最小化入权重 $w^-(s)$、并在次要层次上最小化入度 $|N^-(s)|$ 的顶点 $s$,那么它的入权重不能超过总权重的一半。然后我们取由局部核假设所提供的 $s$ 的非邻域的出核 $K$。由 digraph_nonneighbor_kernel_or_dominating_vertex 的结构二歧性,如果 $\{s\} \cup K$ 不是拟核,就会存在一个入邻点 $t \to s$,其入邻域严格包含在 $s$ 的入邻域内。但这样的顶点 $t$ 将满足 $w^-(t) \le w^-(s)$ 以及 $|N^-(t)| < |N^-(s)|$,从而严格减小最小得分并导致直接矛盾。因此,$\{s\} \cup K$ 必为拟核,且其闭出邻域覆盖了除可能的某些 $s$ 的入邻点之外的每个顶点,保证了它包含至少一半的总权重。

我们陈述每个引理并解释 Lean 如何解决它。

引理 1(字典序得分编码)。设 $\alpha$ 为有限类型,并设 $M$ 为严格大于每个入邻域基数的常数,使得对所有 $x \in \alpha$ 均有 $|N^-(x)| < M$。如果 $w_1 \cdot M + c_1 \le w_2 \cdot M + c_2$ 且 $c_1 < M$,则 $w_1 \le w_2$。此外,如果 $w_1 \le w_2$ 且 $c_1 < c_2$ 以及 $c_1 < M$,则 $w_1 \cdot M + c_1 < w_2 \cdot M + c_2$。这两个陈述均由整数除法和 $\mathbb{N}$ 上的余数算术性质得出。

引理 2(digraph_nonneighbor_kernel_or_dominating_vertex)。设 $D$ 为有限无自环有向图,$s \in \alpha$,且设 $K \subseteq \alpha$ 为 $s$ 的非邻域的出核。则要么 $\{s\} \cup K$ 是 $D$ 的独立拟核,要么存在顶点 $t \in \alpha \setminus \{s\}$ 使得 $D.Adj\ t\ s$ 且 $N^-(t) \subseteq N^-(s)$。

Lean 中的证明:根据非邻域出核的定义,每个 $k \in K$ 均满足 $\neg D.Adj\ s\ k$ 和 $\neg D.Adj\ k\ s$,且 $K$ 是独立的。因此 $\{s\} \cup K$ 是独立的。假设 $\{s\} \cup K$ 不是拟核。那么存在顶点 $x \in \alpha$ 无法从 $\{s\} \cup K$ 在至多 2 步内到达。特别地,$x \notin \{s\} \cup K$,故 $x \ne s$。此外,$\neg D.Adj\ s\ x$,因为否则 $s \in \{s\} \cup K$ 将在 1 步内到达 $x$。若 $x$ 也不是 $s$ 的入邻点(即 $\neg D.Adj\ x\ s$),则 $x$ 属于 $s$ 的非邻域。但 $K$ 是该非邻域的出核,故存在 $k \in K$ 使得 $k = x$ 或 $D.Adj\ k\ x$。无论哪种情况,$x$ 都可以从 $K \subseteq \{s\} \cup K$ 在至多 1 步内到达,这与我们的假设矛盾。因此,必有 $D.Adj\ x\ s$,即 $x \in N^-(s)$。现在,考虑满足 $D.Adj\ z\ x$ 的 $x$ 的任意入邻点 $z$。若 $z$ 不是 $s$ 的入邻点($\neg D.Adj\ z\ s$),则要么 $z = s$,要么 $D.Adj\ s\ z$,要么 $z$ 处于 $s$ 的非邻域中。若 $z = s$,则 $D.Adj\ s\ x$,这已被排除。若 $D.Adj\ s\ z$,则 $s \to z \to x$ 是从 $\{s\} \cup K$ 到 $x$ 的长度为 2 的路径,矛盾。若 $z$ 在 $s$ 的非邻域中,则某个 $k \in K$ 满足 $k = z$ 或 $D.Adj\ k\ z$,从而给出了从 $k \in K$ 到 $x$ 的长度至多为 2 的路径($k = z \to x$ 或 $k \to z \to x$),这同样产生矛盾。因此,$x$ 的每个入邻点 $z$ 都必须满足 $D.Adj\ z\ s$。这证明了 $N^-(x) \subseteq N^-(s)$。令 $t = x$ 便给出了满足 $t \ne s$ 和 $D.Adj\ t\ s$ 的第二种择一情况。

引理 3(入权重与入度单调性)。设 $D$ 为无自环有向图,$w : \alpha \to \mathbb{N}$,并设 $s, t \in \alpha$ 满足 $t \ne s$、$D.Adj\ t\ s$ 以及 $N^-(t) \subseteq N^-(s)$。则 $w^-(t) \le w^-(s)$ 且 $|N^-(t)| < |N^-(s)|$。

Lean 中的证明:因为 $D$ 无自环,所以 $\neg D.Adj\ t\ t$,这意味着 $t \notin N^-(t)$。然而 $D.Adj\ t\ s$,故 $t \in N^-(s)$。由于 $N^-(t) \subseteq N^-(s)$ 且 $t \notin N^-(t)$,我们有 $N^-(t) \subseteq N^-(s) \setminus \{t\}$。因为 $t \in N^-(s)$,集合 $N^-(s) \setminus \{t\}$ 的基数严格小于 $|N^-(s)|$。因此 $|N^-(t)| \le |N^-(s) \setminus \{t\}| = |N^-(s)| - 1 < |N^-(s)|$。对于权重,由于 $w$ 取值于 $\mathbb{N}$,我们有 $w^-(t) = \sum_{u \in N^-(t)} w(u) \le \sum_{u \in N^-(s) \setminus \{t\}} w(u) \le \sum_{u \in N^-(s)} w(u) = w^-(s)$。

引理 4(出邻域覆盖权重)。设 $s \in \alpha$,$K \subseteq \alpha$,并设 $Q = \{s\} \cup K$。如果满足 $\neg D.Adj\ x\ s$ 的每个顶点 $x \in \alpha$ 都属于 $N^+[Q]$,则: $$\sum_{v \in N^+[Q]} w(v) \ge \sum_{v \in \alpha} w(v) - w^-(s).$$

Lean 中的证明:如果顶点 $x \in \alpha$ 不在 $N^+[Q]$ 中,则由假设它必满足 $D.Adj\ x\ s$,即 $x \in N^-(s)$。因此,未被覆盖的顶点集包含在 $N^-(s)$ 中:$\alpha \setminus N^+[Q] \subseteq N^-(s)$。对非负权重求和可得 $\sum_{v \notin N^+[Q]} w(v) \le \sum_{v \in N^-(s)} w(v) = w^-(s)$。由于 $\sum_{v \in \alpha} w(v) = \sum_{v \in N^+[Q]} w(v) + \sum_{v \notin N^+[Q]} w(v)$,移项整理即得所断言的界。

引理 5(定向图的二重和界)。设 $D$ 为定向图且 $w : \alpha \to \mathbb{N}$。则: $$\sum_{v \in \alpha} w(v) w^-(v) \le \frac{1}{2} \left( \sum_{v \in \alpha} w(v) \right)^2.$$

Lean 中的证明:展开 $w^-(v)$ 可得 $\sum_{v \in \alpha} w(v) w^-(v) = \sum_{v \in \alpha} \sum_{u \in N^-(v)} w(u) w(v) = \sum_{(u, v) \in E} w(u) w(v)$。由于 $D$ 是定向图,对于任意一对不同顶点 $\{u, v\}$,$(u, v)$ 或 $(v, u)$ 中至多有一个是有向弧。由于 $D$ 没有自环,任何对 $(u, u)$ 都不是弧。因此 $2 \sum_{(u, v) \in E} w(u) w(v) = \sum_{(u, v) \in E} w(u) w(v) + \sum_{(v, u) \in E} w(v) w(u) \le \sum_{u \ne v} w(u) w(v)$。由于 $\sum_{u \ne v} w(u) w(v) = (\sum_{v} w(v))^2 - \sum_{v} w(v)^2 \le (\sum_{v} w(v))^2$,两边除以 2 即确立了该不等式。

引理 6(最小入权重界)。设 $s \in \alpha$ 使得对所有 $v \in \alpha$ 均有 $w^-(s) \le w^-(v)$。若 $W = \sum_{v \in \alpha} w(v) > 0$ 且 $\sum_{v \in \alpha} w(v) w^-(v) \le \frac{1}{2} W^2$, 则 $2 w^-(s) \le W$。

Lean 中的证明:将不等式 $w^-(s) \le w^-(v)$ 乘以 $w(v) \ge 0$ 并对所有 $v \in \alpha$ 求和,可得 $w^-(s) W = \sum_{v \in \alpha} w(v) w^-(s) \le \sum_{v \in \alpha} w(v) w^-(v) \le \frac{1}{2} W^2$。两边乘以 2 得到 $2 w^-(s) W \le W^2$。由于 $W > 0$,两边除以 $W$ 即可得出 $2 w^-(s) \le W$。

现在我们将这些引理结合起来以确立主定理:

1. 基础情况:若 $\alpha$ 为空,我们选取 $Q = \emptyset$。独立性与拟核可达性条件均平凡成立,且求和不等式两端均等于 0,从而 $0 \le 2 \cdot 0$。 2. 极小元选取:若 $\alpha$ 非空,我们定义编码模数 $M = \text{card}(\alpha) + 1$ 以及得分函数: $$\text{score}(v) = w^-(v) \cdot M + |N^-(v)|.$$ 由有限非空集合上最小值的存在性,存在顶点 $s \in \alpha$ 在所有 $v \in \alpha$ 上最小化 $\text{score}(v)$。由引理 1,$s$ 也最小化 $w^-(v)$:$\forall v \in \alpha, w^-(s) \le w^-(v)$。 3. 应用结构二歧性:由关于 $s$ 的局部假设,存在 $s$ 的非邻域的出核 $K$。我们对 $s$ 和 $K$ 应用引理 2(digraph_nonneighbor_kernel_or_dominating_vertex)。若存在 $t \ne s$ 使得 $D.Adj\ t\ s$ 且 $N^-(t) \subseteq N^-(s)$,则由引理 3,我们有 $w^-(t) \le w^-(s)$ 以及 $|N^-(t)| < |N^-(s)|$。应用引理 1 表明 $\text{score}(t) < \text{score}(s)$,这直接与 $\text{score}(s)$ 的极小性相矛盾。因此这种择一情况被排除,第一种择一情况必成立:$Q = \{s\} \cup K$ 是 $D$ 的独立拟核。 4. 邻域覆盖:设 $x \in \alpha$ 为满足 $\neg D.Adj\ x\ s$ 的任意顶点。若 $x = s$,则 $x \in Q \subseteq N^+[Q]$。若 $x \ne s$ 且 $D.Adj\ s\ x$,则 $s \in Q$ 出支配 $x$,从而 $x \in N^+[Q]$。若 $x \ne s$ 且 $\neg D.Adj\ s\ x$,则 $x$ 在 $s$ 的非邻域中;由于 $K$ 出支配该非邻域,存在 $k \in K \subseteq Q$ 使得 $k = x$ 或 $D.Adj\ k\ x$,因此 $x \in N^+[Q]$。 5. 权重计算:由于不在 $N^-(s)$ 中的每个顶点都被 $N^+[Q]$ 覆盖,引理 4 给出 $\sum_{v \in N^+[Q]} w(v) \ge W - w^-(s)$。若 $W = 0$,不等式 $W \le 2 w(N^+[Q])$ 平凡成立($0 \le 0$)。若 $W > 0$,引理 5 和引理 6 给出 $2 w^-(s) \le W$,这等价于 $2 (W - w^-(s)) \ge W$。将此与覆盖界相结合可得 $2 \sum_{v \in N^+[Q]} w(v) \ge 2 (W - w^-(s)) \ge W = \sum_{v \in \alpha} w(v)$,完成了证明。

5. 讨论

定理 digraph_nonneighborhood_kernels_weighted_half_cover 为由局部条件定义的一类定向图确立了拟核的加权半覆盖性质。我们指出每个假设在何处发挥作用、对猜想带来的结论以及仍未解决的问题。

  1. 定向性:$D$ 没有有向 2-圈。这仅在引理 5 中用于将最小入权重限制在总权重的一半以内。没有它,选取规则本身就会失效:一个形式化的例子给出了一个具有 2-圈的 4-顶点半完全有向图和一个权重赋值,其中一个顶点同时最小化入权重和入度且本身构成拟核,然而其闭出邻域所承载的权重却少于总权重的一半。
  2. 非邻域核:每个顶点的非邻域必须诱导出一个具有核的有向图。这在竞赛图、定向完全多部图中成立,并且只要每个非邻域都诱导出一个无圈图或更一般地核完美有向图时也成立。一旦某个非邻域诱导出(例如)有向奇圈,该条件就会失效。

根据 arXiv:2610.23487 的定理 1.3,每个具有加权半覆盖性质的无源有向图都拥有一个大小至多为 $\lfloor |V|/2 \rfloor$ 的拟核。因此,该图类中的每个无源定向图都满足小拟核猜想;这一推论依赖于该论文的定理,不属于 Lean 形式化开发的一部分。对于定向完全多部图,半阶数界本身此前已为人所知(arXiv:2610.23487 指出半完全多部有向图具有两个不相交的拟核);在该处,本定理补充了加权结论。该图类与break有向图类是不可比较的,因此该结果将加权方法的应用范围扩展到了该论文所处理的图类之外,且二者互不包含。

两个小型的形式化例子标明了更简单策略的局限性:在 digraph_seven_tournament_two_neighborhood_cover_counterexample 中,一个具有 7 个顶点的无源竞赛图以每个单元素集作为拟核且仅有单元素拟核,然而其中任意两个单元素集的闭出邻域都无法覆盖所有顶点;在 digraph_small_quasikernel_max_independent_cover_counterexample 中,一个具有 7 个顶点的无源定向图拥有一个大小为 4 的最大独立集,该独立集不在任何大小至多为 $7/2$ 的拟核的闭出邻域内。

仍未解决的问题:

  1. 是否每个定向图都具有加权半覆盖性质?由迁移定理,这将为所有无源定向图证明小拟核猜想。
  2. 非邻域核假设能否放宽为非邻域拟核?若 $K$ 仅为 $s$ 的非邻域的拟核,digraph_nonneighbor_kernel_or_dominating_vertex 中的二歧性的类似结论是否仍然成立?
  3. 在最小化入权重失效的具有 2-圈的有向图中,是否存在不同的选取规则能使未覆盖权重保持在至多为总权重的一半?

为什么是研究级成果

  • Weighted half-coverage by quasi-kernels for every oriented graph whose non-neighborhoods have kernels; with the transfer theorem of arXiv:2610.23487 this gives the half-order bound for a class incomparable with the break digraphs treated there

Lean 声明

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

参考文献

  1. arXiv:2610.23487 — Small and large quasi-kernels: a weighted transfer theorem

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