对于 $n \ge 4$,包含某顶点的支配集的局部平均阶严格小于 $(5n-1)/6$
low tier2026-10-09OP-135审阅: Claude CodeEnglish
摘要
arXiv:2610.11446 的定理 3.8 确立了:对于每个阶为 $n$ 且无孤立顶点的有限简单图 $G$ 以及每个顶点 $v$,包含 $v$ 的支配集的局部平均阶(记作 $avd_v(G)$)满足 $avd_v(G) \le \frac{5n-1}{6}$。尽管当 $n = 3$ 时,该上界由路图 $P_3$ 的一个端点达到,但对于任意 $n \ge 4$,该界是否紧仍是一个悬而未决的问题。本文通过证明对于每个阶为 $n \ge 4$ 且无孤立顶点的有限简单图 $G$ 以及每个顶点 $v \in V(G)$,严格不等式 $avd_v(G) < \frac{5n-1}{6}$ 均成立,从而对这一问题给出了否定的回答。该证明基于可移除顶点与关键顶点对包含每个顶点的支配集进行双重计数,在邻域交集为单元素的集合上建立单射以表明所有支配集中至多有三分之二与任意顶点的闭邻域仅相交于单个元素,并在该顶点的度至少为 2 时加强了这一界。当 $v$ 的度至少为 2 时,该界直接成立;当 $v$ 的度为 1 时,对 $v$ 的闭邻域之外的顶点进行结构分析,可得出存在一个度至少为 2 的顶点,或者存在一对共享同一个关键见证集的顶点。整个证明已在 Lean 4 中形式化并经过了机器验证。
1. 引言
设 $G = (V, E)$ 是一个阶为 $n = |V|$ 的有限简单无向图。若 $V$ 中的每个顶点要么属于 $S$,要么与 $S$ 中的至少一个顶点相邻,则子集 $S \subseteq V$ 是 $G$ 的支配集。支配集是图论与组合优化中的核心概念,有大量研究致力于其结构性质、基数界和计数不变量。对支配集的全局研究的一个自然细化是局部视角:对于指定顶点 $v \in V$,将注意力限制在包含 $v$ 的支配集族 $\mathcal{D}_v(G)$ 上。包含 $v$ 的支配集的局部平均阶记作 $avd_v(G)$,定义为属于 $\mathcal{D}_v(G)$ 的所有支配集基数的算术平均值: $$avd_v(G) = \frac{1}{|\mathcal{D}_v(G)|} \sum_{S \in \mathcal{D}_v(G)} |S|.$$
在 arXiv:2610.11446 中,研究了无孤立顶点图的支配集局部平均阶。具体而言,arXiv:2610.11446 的定理 3.8 证明了对于每个阶为 $n$ 且没有孤立顶点的有限简单图 $G$ 以及每个顶点 $v \in V(G)$,局部平均阶满足上界 $$avd_v(G) \le \frac{5n - 2 \deg(v) + 1}{6} \le \frac{5n - 1}{6}.$$ 对于较小的图,该界可以是紧的。特别地,当 $n = 3$ 时,考虑具有三个顶点、顶点集为 $\{v, u, w\}$ 且边集为 $\{\{v, u\}, \{u, w\}\}$ 的路图 $P_3$。顶点 $v$ 是一个度为 1 的叶顶点。包含 $v$ 的 $P_3$ 的支配集为 $\{v, u\}$、$\{v, w\}$ 和 $\{v, u, w\}$。恰好有 3 个这样的支配集,其基数分别为 2、2 和 3。它们大小的算术平均值为 $$avd_v(P_3) = \frac{2 + 2 + 3}{3} = \frac{7}{3}.$$ 对 $n = 3$ 计算定理 3.8 的上界给出 $\frac{5(3) - 1}{6} = \frac{14}{6} = \frac{7}{3}$。因此,对于 $n = 3$,该界在叶顶点 $v$ 处取到等号。
然而,arXiv:2610.11446 定理 3.8 中对界 $\frac{5n-1}{6}$ 的分析推导是通过将闭邻域 $N[v]$ 之外的每个顶点 $u$ 的贡献限制在形如下式的不等式中进行的: $$\frac{\deg(u) + 1}{2^{\deg(u) + 1} - 1} \le \frac{2}{3}.$$ 该分式界取等号要求闭邻域之外的每个顶点 $u \notin N[v]$ 都满足 $\deg(u) = 1$。此外,要达到总体的界,需要所有这些顶点具有两两不相交的闭邻域。正如在 arXiv:2610.11446 中所指出的,当 $n \ge 4$ 时,这些结构要求施加了严格的几何和度约束,任何无孤立顶点的简单图都无法同时满足这些约束。这引出了 arXiv:2610.11446 中的公开问题:是否存在阶为 $n \ge 4$ 且无孤立顶点的图 $G$ 以及顶点 $v \in V(G)$ 使得 $avd_v(G) = \frac{5n-1}{6}$,还是对于每个 $n \ge 4$ 该界都严格不紧?如果该界不紧,那么作为 $n$ 的函数的 $avd_v(G)$ 的精确最大值是多少?
在本文中,我们给出了对该紧性问题的否定形式化解答。在 Lean 4 证明助手中,我们验证了定理 simple_graph_local_avg_dominating_order_lt_of_four_le,该定理确立了对于每个阶为 $n \ge 4$ 且无孤立顶点的有限简单图 $G$ 以及每个顶点 $v \in V(G)$, $$avd_v(G) < \frac{5n - 1}{6}.$$ 该证明依赖于将支配集基数之和与关键顶点数量联系起来的双重计数论证、界定与闭邻域相交为单点的支配集比例的单射,以及针对 $v$ 的度与 $N[v]$ 外部顶点的邻域构型进行的结构情形划分。
2. 预备知识
设 $V$ 为具有可判定相等性的有限类型。我们考虑顶点集为 $V$ 且具有可判定邻接关系的简单图 $G$。在此设定下,简单图是 $V$ 上的反自反、对称关系。
对于任意顶点 $w \in V$,$w$ 在 $G$ 中的开邻域是与 $w$ 相邻的顶点的有限集合,记作 $N(w)$。$w$ 的度记作 $\deg(w)$,是 $N(w)$ 的基数。$w$ 的闭邻域记作 $N[w]$,定义为 $$N[w] = \{w\} \cup N(w).$$
若每个顶点的度均至少为 1,则图 $G$ 没有孤立顶点。在 Lean 中,该条件由每个顶点的度严格大于 0 的假设表示,使用自然数上的严格不等式。$G$ 的阶是顶点集 $V$ 的基数,记作 $n = |V|$。
现在给出在 Lean 中形式化的定义,用以界定局部平均支配阶:
定义 1 (simple_graph_dominating_sets_containing): 设 $G$ 是有限顶点集 $V$ 上的简单图,并设 $v \in V$。若 $v \in S$ 且每个顶点 $w \in V$ 都满足 $w \in S$ 或与某个顶点 $u \in S$ 相邻,则子集 $S \subseteq V$ 是 $G$ 的包含 $v$ 的支配集。所有此类支配集的族在 Lean 中由 simple_graph_dominating_sets_containing 定义为 $V$ 的幂集的有限子集,由下式给出: $$\mathcal{D}_v(G) = \left\{ S \subseteq V \;\middle|\; v \in S \land \forall w \in V, \, (w \in S \lor \exists u \in S, \, u \sim w) \right\}.$$
定义 2 (simple_graph_local_avg_dominating_order): 设 $G$ 是有限顶点集 $V$ 上的简单图,并设 $v \in V$。包含 $v$ 的支配集的局部平均阶记作 $avd_v(G)$,在 Lean 中由 simple_graph_local_avg_dominating_order 定义为 $\mathcal{D}_v(G)$ 中集合基数的算术平均值,在有理数 $\mathbb{Q}$ 中取值: $$avd_v(G) = \frac{\sum_{S \in \mathcal{D}_v(G)} |S|}{|\mathcal{D}_v(G)|}.$$
定义 3(未支配集 $U$): 对于固定的顶点 $v \in V$,$v$ 的闭邻域之外的顶点集记作 $U$。它定义为 $$U = (V \setminus \{v\}) \setminus N(v) = V \setminus N[v].$$ 集合 $U$ 由 $G$ 中所有未被单元素集 $\{v\}$ 支配的顶点组成。
形式化约定的注记: 定义 simple_graph_local_avg_dominating_order 在有理数域 $\mathbb{Q}$ 中进行除法。因为全顶点集 $V$ 始终是包含 $v$ 的支配集,所以集合族 $\mathcal{D}_v(G)$ 包含全集 $V$,从而确保 $\mathcal{D}_v(G)$ 非空且其基数为正。因此,除以零的情况绝不会发生。图 $G$ 没有孤立顶点的假设被表述为一个全称命题,即度数严格为正,而不是关于存在邻居的特称命题,这便于算术运算。最后,尽管在整个分析过程中 $v$ 是一个固定的特定顶点,但基数 $n = |V|$ 在满足 $n \ge 4$ 的条件下是任意的。
3. 主要结果
主定理否定了对于所有阶为 $n \ge 4$ 且无孤立顶点的图上界 $(5n-1)/6$ 的紧性。
定理 1 (simple_graph_local_avg_dominating_order_lt_of_four_le): 设 $V$ 为具有可判定相等性的有限类型,设 $G$ 是 $V$ 上具有可判定邻接关系的简单图。假设 $G$ 的阶满足 $n = |V| \ge 4$,且 $G$ 没有孤立顶点,即对所有 $w \in V$ 均有 $\deg(w) > 0$。则对于每个顶点 $v \in V$,包含 $v$ 的支配集的局部平均阶满足 $$avd_v(G) < \frac{5n - 1}{6}.$$
在 Lean 形式化中,该定理陈述为 simple_graph_local_avg_dominating_order_lt_of_four_le,对具有有限和可判定实例的顶点类型 $V$、具有可判定邻接关系的简单图 $G$、$V$ 的基数至少为 4 的假设、每个度数均严格为正的条件以及顶点 $v$ 进行全称量化,断言在有理数中 simple_graph_local_avg_dominating_order 在 $G$ 和 $v$ 处的值严格小于 $(5n - 1)/6$。
该定理对 arXiv:2610.11446 中提出的针对所有 $n \ge 4$ 的紧性问题给出了完全否定的回答。特别是,它表明在 $n = 3$ 处观察到的极值行为——其中路 $P_3$ 达到等号 $avd_v(P_3) = \frac{7}{3} = \frac{5(3)-1}{6}$——是一个孤立现象,不可能在任何更大的图上出现。此外,证明中的结构论证提供了依赖于 $v$ 的度的更精细界:当 $\deg(v) \ge 2$ 时,表明 $$avd_v(G) \le \frac{5n + 1 - 2 \deg(v)}{6} \le \frac{5n - 3}{6},$$ 而当 $\deg(v) = 1$ 时,证明了严格界 $$avd_v(G) \le \frac{5n - 1}{6} - \frac{1}{6|\mathcal{D}_v(G)|}.$$
theorem simple_graph_local_avg_dominating_order_lt_of_four_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hn : 4 ≤ Fintype.card V) (hiso : ∀ w, 0 < G.degree w) (v : V) : simple_graph_local_avg_dominating_order G v < (5 * (Fintype.card V : ℚ) - 1) / 6
4. 证明
设 $D = \mathcal{D}_v(G)$ 表示包含 $v$ 的支配集族。
证明思路: 为界定 $D$ 中支配集的平均大小,我们将总大小 $\sum_{S \in D} |S|$ 表示为 $\sum_{x \in V} a(x)$,其中 $a(x)$ 计算包含 $x$ 的支配集数量。每个这样的集合在移除 $x$ 后,要么仍然是支配集(此时 $x$ 是可移除的),要么在移除 $x$ 后不再是支配集(此时 $x$ 是关键的)。可移除集与不含 $x$ 的集合之间的双射给出 $a(x) = b(x) + c(x)$,从而得出 $2 \sum_{S \in D} |S| = n |D| + \sum_{x \in V} c(x)$,其中 $c(x)$ 计算使得 $x$ 是关键的集合数量。对于 $x \ne v$,任何关键集对于某个 $w \in U = V \setminus N[v]$ 都恰好与闭邻域 $N[w]$ 相交于 $\{x\}$。通过向与 $N[w]$ 相交至少两个顶点的集合建立单射,证明了所有支配集中至多有 $2/3$ 与 $N[w]$ 相交于单元素集;当 $\deg(w) \ge 2$ 时,该界可加强为 $3 |S_1(w)| + 2 \le 2|D|$。对 $U$ 求和可得 $avd_v(G) \le (5n + 1 - 2\deg(v))/6$。当 $\deg(v) \ge 2$ 时,该界严格小于 $(5n-1)/6$。当 $\deg(v) = 1$ 时,对 $U$ 中的叶顶点进行结构分析,得出要么存在一个度至少为 2 的顶点,要么存在一对共享同一个关键见证集的叶顶点,从而将该界严格精细化为 $avd_v(G) \le (5n - 1)/6 - 1/(6|D|) < (5n - 1)/6$。
我们现在通过六个引理来形式化这一论证。
引理 1(超集封闭性): 集合族 $D$ 非空且关于取超集封闭:若 $S \in D$ 且 $S \subseteq T \subseteq V$,则 $T \in D$。
引理 1 的证明: 全集 $V$ 包含 $v$ 并支配每个顶点,因此 $V \in D$。若 $S \in D$ 且 $S \subseteq T$,则 $v \in T$,且被 $S$ 支配的任何顶点仍被 $T$ 支配。
引理 2($U$ 的基数): 设 $U = V \setminus N[v]$。则 $|U| = n - 1 - \deg(v)$ 且 $\deg(v) \le n - 1$。
引理 2 的证明: 由于 $G$ 无自环,故 $N(v) \subseteq V \setminus \{v\}$。因为 $|V \setminus \{v\}| = n - 1$ 且 $|N(v)| = \deg(v)$,所以差集的大小为 $|U| = n - 1 - \deg(v)$,且 $\deg(v) \le n - 1$。
引理 3(关键性分解): 对每个顶点 $x \in V$,设 $a(x) = |\{S \in D \mid x \in S\}|$,$b(x) = |\{S \in D \mid x \notin S\}|$,以及 $c(x) = |\{S \in D \mid x \in S \land S \setminus \{x\} \notin D\}|$。则:
- $a(x) + b(x) = |D|$;
- $a(x) = b(x) + c(x)$;
- $\sum_{S \in D} |S| = \sum_{x \in V} a(x)$;
- $2 \sum_{x \in V} a(x) = n |D| + \sum_{x \in V} c(x)$。
引理 3 的证明: 第 1 部分是 $D$ 按 $x$ 的归属性进行的划分。对于第 2 部分,包含 $x$ 的集合划分为可移除集($S \setminus \{x\} \in D$)与关键集($S \setminus \{x\} \notin D$)。映射 $S \mapsto S \setminus \{x\}$ 是从可移除集到不含 $x$ 的集合的双射,其逆映射为 $T \mapsto T \cup \{x\}$,由引理 1 可知该逆映射的像在 $D$ 中。因此可移除集的数量为 $b(x)$,从而给出 $a(x) = b(x) + c(x)$。第 3 部分交换指示函数的求和次序。第 4 部分将 $a(x) + b(x) = |D|$ 与 $a(x) - b(x) = c(x)$ 相加得到 $2 a(x) = |D| + c(x)$,并对 $x \in V$ 求和。
引理 4(关键见证集): 对 $w \in V$ 和 $x \in V$,设 $E(w, x) = \{S \in D \mid S \cap N[w] = \{x\}\}$。对于任意 $x \ne v$,使得 $x$ 为关键顶点的每个集合 $S \in D$ 都对某个 $w \in U$ 满足 $S \in E(w, x)$。因此,$c(x) \le \sum_{w \in U} |E(w, x)|$。此外,若相异的 $w_1, w_2 \in U$ 满足 $E(w_1, x) \cap E(w_2, x) \ne \emptyset$,则 $c(x) + 1 \le \sum_{w \in U} |E(w, x)|$。
引理 4 的证明: 若 $x \ne v$ 且 $S \setminus \{x\} \notin D$,则 $v \in S \setminus \{x\}$,从而存在某个顶点 $w$ 未被 $S \setminus \{x\}$ 支配。由于 $v \in S \setminus \{x\}$,$w$ 未被 $v$ 支配,故 $w \in U$。$S$ 支配 $w$ 要求 $S \cap N[w]$ 非空,但 $(S \setminus \{x\}) \cap N[w] = \emptyset$,所以 $S \cap N[w] = \{x\}$,即 $S \in E(w, x)$。由并集界可得 $c(x) \le \sum_{w \in U} |E(w, x)|$。$E(w_1, x)$ 与 $E(w_2, x)$ 之间的重合元素使并集的基数严格减少至少 1。
引理 5(邻域单元素界): 对 $w \in V$,设 $S_1(w) = \{S \in D \mid |S \cap N[w]| = 1\}$ 且 $S_{\ge 2}(w) = \{S \in D \mid |S \cap N[w]| \ge 2\}$。则:
- $3 |S_1(w)| \le 2 |D|$;
- 若 $\deg(w) \ge 2$,则 $3 |S_1(w)| + 2 \le 2 |D|$。
引理 5 的证明: 由于 $G$ 没有孤立顶点,$w$ 有一个邻居 $w'$。定义 $\phi : S_1(w) \to S_{\ge 2}(w)$ 为:若 $w \in S$,则 $\phi(S) = S \cup \{w'\}$;若 $w \notin S$,则 $\phi(S) = S \cup \{w\}$。在两种情形下,由引理 1 均有 $\phi(S) \in D$,且 $|\phi(S) \cap N[w]| \ge 2$。$\phi$ 的每个纤维的大小至多为 2,因为任何原像必为 $M \setminus \{w'\}$ 或 $M \setminus \{w\}$。因此 $|S_1(w)| \le 2 |S_{\ge 2}(w)| \le 2(|D| - |S_1(w)|)$,移项整理得 $3 |S_1(w)| \le 2 |D|$,这就证明了第 1 部分。 对于第 2 部分,若 $\deg(w) \ge 2$,则 $|N[w]| \ge 3$,从而 $V \in S_{\ge 2}(w)$。但 $V \notin \mathrm{im}(\phi)$,因为从 $V$ 中移除至多一个顶点后,在 $N[w]$ 中仍留下至少 $3 - 1 = 2$ 个顶点,这与 $|S \cap N[w]| = 1$ 矛盾。因此 $\mathrm{im}(\phi) \subseteq S_{\ge 2}(w) \setminus \{V\}$,从而得出 $|S_1(w)| \le 2(|S_{\ge 2}(w)| - 1) \le 2(|D| - |S_1(w)| - 1)$,整理即得 $3 |S_1(w)| + 2 \le 2 |D|$。
引理 6(关键性和): 总关键性和满足 $3 \sum_{x \in V} c(x) \le 3 |D| + 2 |U| |D|$。此外,若某个 $w_0 \in U$ 满足 $\deg(w_0) \ge 2$,或者若相异的 $w_1, w_2 \in U$ 对某个 $x \ne v$ 共享见证集 $S \in E(w_1, x) \cap E(w_2, x)$,则 $3 \sum_{x \in V} c(x) + 1 \le 3 |D| + 2 |U| |D|$。
引理 6 的证明: 对每个 $w \in U$,不同 $x \ne v$ 对应的集合 $E(w, x)$ 是 $S_1(w)$ 的两两不相交子集,因此 $\sum_{x \ne v} |E(w, x)| \le |S_1(w)|$。对 $x \ne v$ 求和给出 $\sum_{x \ne v} c(x) \le \sum_{w \in U} |S_1(w)|$。乘以 3 并应用引理 5 第 1 部分可得 $3 \sum_{x \ne v} c(x) \le 2 |U| |D|$。加上平凡界 $3 c(v) \le 3 |D|$ 便给出了通用的不等式。当某个 $w_0 \in U$ 满足 $\deg(w_0) \ge 2$ 时,引理 5 第 2 部分使该和至少减少 2。当 $U$ 中的两个顶点共享一个见证集时,引理 4 使 $c(x)$ 之和减少 1,乘以 3 后使总数减少 3。在这两种情形下,均有 $3 \sum_{x \in V} c(x) + 1 \le 3 |D| + 2 |U| |D|$。
主定理的证明: 我们将论证根据 $\deg(v)$ 分为两种情形。
情形 1:$\deg(v) \ge 2$。 由引理 2,$|U| = n - 1 - \deg(v)$。将引理 6 的界代入引理 3 第 4 部分给出: $$2 \sum_{x \in V} a(x) \le \left( n + 1 + \frac{2}{3}(n - 1 - \deg(v)) \right) |D| = \frac{5n + 1 - 2 \deg(v)}{3} |D|.$$ 除以 $2 |D|$ 得到 $avd_v(G) \le (5n + 1 - 2 \deg(v))/6$。因为 $\deg(v) \ge 2$,这给出了 $avd_v(G) \le (5n - 3)/6 < (5n - 1)/6$。
情形 2:$\deg(v) = 1$。 由于 $G$ 没有孤立顶点,$v$ 有唯一邻居 $y$。由引理 2,因为 $n \ge 4$,所以 $|U| = n - 2 \ge 2$。若 $U$ 中的某个顶点度至少为 2,则引理 6 的严格界立即成立。 否则,$U$ 中的每个顶点的度均为 1,因此每个 $w \in U$ 都是具有唯一邻居 $z \ne v$ 的叶顶点:
- 若某个叶顶点 $w \in U$ 的邻居 $z$ 在 $U$ 中,则 $\{w, z\}$ 是同构于 $K_2$ 的连通分支。集合 $S = V \setminus \{z\}$ 包含 $v$ 并支配 $G$,因此 $S \in D$。我们有 $S \cap N[w] = \{w\}$ 且 $S \cap N[z] = \{w\}$,故 $S \in E(w, w) \cap E(z, w)$,在相异顶点 $w, z \in U$ 之间提供了关于 $w$ 的共享见证集。
- 若 $U$ 中的每个叶顶点的邻居都在 $U$ 之外,则 $U$ 中的所有叶顶点必与 $y$ 相邻(因为 $v$ 仅与 $y$ 相连)。由于 $|U| \ge 2$,选取相异的叶顶点 $w_1, w_2 \in U$。集合 $S = V \setminus \{w_1, w_2\}$ 包含 $v$ 和 $y$ 且支配 $G$,因此 $S \in D$。于是 $S \cap N[w_1] = \{y\}$ 且 $S \cap N[w_2] = \{y\}$,故 $S \in E(w_1, y) \cap E(w_2, y)$,为 $y \ne v$ 提供了共享见证集。
在情形 2 的所有子情形中,引理 6 均给出 $3 \sum_{x \in V} c(x) + 1 \le (2n - 1) |D|$。代入引理 3 第 4 部分可得 $2 \sum a(x) \le \frac{5n - 1}{3} |D| - \frac{1}{3}$,从而 $avd_v(G) \le \frac{5n - 1}{6} - \frac{1}{6 |D|} < \frac{5n - 1}{6}$。 定理 1 (simple_graph_local_avg_dominating_order_lt_of_four_le) 的证明至此完成。
5. 讨论
本文所证明的定理解决了 arXiv:2610.11446 定理 3.8 中建立的上界 $(5n-1)/6$ 是否能对阶为 $n \ge 4$ 的图达到的问题。它表明紧性普遍不成立:不存在阶为 $n \ge 4$ 且无孤立顶点的图具有能够达到 $avd_v(G) = \frac{5n-1}{6}$ 的顶点 $v$。因此,在端点处达到 $7/3 = (5(3)-1)/6$ 的路 $P_3$ 是所有无孤立顶点图中唯一的极值情形。
该结果未涉及的是确定在所有阶为 $n$ 且无孤立顶点的图以及 $v \in V(G)$ 的所有选取上 $avd_v(G)$ 的精确最大值。正如公开问题陈述中所指出的,arXiv:2610.11446 中提出的问题的第二部分问道:作为 $n$ 的函数,$avd_v(G)$ 的精确最大值是多少?
文献中提到了一个猜想界 $$avd_v(G) \le \frac{2n + 1}{3}.$$ 对所有 $n \ge 4$,这一候选界严格强于 $(5n-1)/6$: $$\frac{5n - 1}{6} - \frac{2n + 1}{3} = \frac{5n - 1 - 2(2n + 1)}{6} = \frac{n - 3}{6} > 0.$$ 在 $n = 3$ 时,两界重合:$\frac{2(3) + 1}{3} = \frac{7}{3} = \frac{5(3) - 1}{6}$。 对于 $n = 4$,该猜想界给出 $\frac{2(4)+1}{3} = 3$,而 $\frac{5(4)-1}{6} = \frac{19}{6} \approx 3.167$。 对于 $n = 5$,该猜想界给出 $\frac{11}{3} \approx 3.667$,而 $\frac{5(5)-1}{6} = 4$。 因此,界 $(2n+1)/3$ 将蕴含对所有 $n \ge 4$ 严格不等式 $avd_v(G) < (5n-1)/6$ 成立。在 simple_graph_local_avg_dominating_order_lt_of_four_le 中形式化的直接证明,独立于 $(2n+1)/3$ 是否能达到或在完全一般性下可证,通过揭示取等号的结构阻碍否定了 $(5n-1)/6$ 的紧性:对 $N[v]$ 外部叶顶点的邻域相交性的同时约束,迫使存在度为 2 的顶点或共享的关键见证集。
源自 arXiv:2610.11446 的下一个重要问题是猜想界 $(2n+1)/3$ 是否对所有 $n \ge 4$ 都成立;如果成立,哪些图和顶点能达到等号。另一个方向是刻画作为 $n$ 的函数的 $avd_v(G)$ 的精确最大值。
为什么是研究级成果
- refutes OP-135 (Sharpness of the (5n-1)/6 local average dominating set bound for n at least 4)
Lean 声明
- simple_graph_local_avg_dominating_order_lt_of_four_leFor n ≥ 4 the upper bound (5n−1)/6 is never attained: if G has order n ≥ 4 and no isolated vertices, then avd_v(G) < (5n−1)/6 for every…
- simple_graph_dominating_sets_containingD_v(G): the dominating sets of G that contain v, where S dominates G when every vertex is in S or adjacent to a vertex of S.
- simple_graph_local_avg_dominating_orderavd_v(G): the local average order of dominating sets containing v, i.e. the average size of the dominating sets of G that contain v.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2610.11446 — On the local average order of dominating sets
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。