← 返回 PaperDaily 大模型与智能体

大佬猜错？C7⊠C7竟然有10个一般位置点，不是9！

图论中看似完美的乘性猜想，被一篇预印本干净利落地推翻。本文不仅给出了路径强积与循环强积的精确公式，更构造出一个个具体反例，让「强积图一般位置数等于因子乘积」的神话破灭。思路清晰，论证优雅，适合图论爱好者品读。

龙哥读论文发布于 2026-09-05 00:31:11 阅读 3 查看原文

#人工智能

原论文信息如下：

论文标题:
General position sets in strong products with paths and cycles

发表日期: 2026年7月 发表单位: University of Maribor, Slovenia; Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia 原文链接: https://arxiv.org/pdf/2607.26844v1.pdf

龙哥今天要聊的这篇论文，来自2026年7月的预印本，作者是斯洛文尼亚马里博尔大学的Aleksander Vesel。看起来是个相对冷门的图论方向，但故事却一波三折——核心是关于一个被《Open Mathematics》期刊论文提出来的大胆猜想。这个猜想如果成立，将给出一个极其简洁优美的乘法公式，让强积图的一般位置数完全由因子决定。然而，Vesel用一篇干净利落的论文告诉我们：数学的直觉有时会骗人，看似完美的猜想，往往藏着你意想不到的反例。

问题背景与猜想

先来扫个盲。图论里有个概念叫一般位置集（general position set）：在一个图G中，一个顶点集合S称为一般位置集，如果S中任意三个不同顶点u、v、w，都不存在w位于u到v的某条最短路径上。这个集合的最大大小就是图的一般位置数，记作 gp(G)。这个概念最早由Chandran和Parthasarathy在2016年独立提出，近年来在图的乘积结构上吸引了不少研究。简单来说，一般位置集就是图中“没有顶点挡在另外两个顶点的最短路径中间”的最大集合，它刻画了图在测地线意义下的“无遮挡”程度。

什么是强乘积（strong product）？两个图G和H的强乘积 G ⊠ H，顶点集是V(G)×V(H)，两个顶点(u_x,u_y)和(v_x,v_y)相邻当且仅当它们在每个坐标上要么相等要么相邻（且至少有一个坐标是相邻的）。这个定义让强乘积在距离上具有一个很简洁的性质：
d_{G⊠H}(u,v) = max{ d_G(u_x,v_x), d_H(u_y,v_y) }。
这个性质（文中记为Fact 1.1）是整个证明的基石。它告诉我们，在强积图中，两点之间的距离完全由两个坐标方向上的距离中的较大者决定。这种“取最大值”的距离结构，使得强积图在组合性质上往往表现出某种“乘积性”，但也正是这种结构，为后来反例的构造埋下了伏笔。

2019年，Klavžar和Yero在《Open Mathematics》发表了一篇系统性的研究（[10]），其中证明了强乘积的一般位置数至少是因子一般位置数的乘积，即 gp(G⊠H) ≥ gp(G) gp(H)，并提出了一个开放问题（Problem 4.8）：这个下界是否总是紧的？换句话说，是否永远有 gp(G⊠H) = gp(G) gp(H)？如果成立，那将是个非常优雅的乘法公式。这个猜想之所以吸引人，是因为它非常自然：既然强积图的距离是取最大值，那么一般位置集似乎也应该能通过“乘积”的方式构造出来。Klavžar和Yero在论文中给出了大量支持性证据，包括对一些特殊图类验证了等号成立，使得这个猜想看起来相当可信。

然而本论文的作者Vesel直接给出了否定答案：这个猜想不成立！他不只举出了反例，还系统刻画了当其中一个因子是路径或小圈时的精确结果，让整个图景清晰了起来。Vesel的论文结构非常清晰：首先处理路径作为因子的情况，得到完美的精确公式；然后处理循环作为因子的情况，给出上界和小圈的精确值；最后，通过构造具体的反例，彻底否定了乘性猜想。这种从肯定到否定的递进式叙述，让读者能够逐步理解问题的本质。

路径强乘积的精确结果

论文第一个主要定理（Theorem 2.2）非常漂亮：对任意s ≥ 2和任意连通图H，有
gp(Ps ⊠ H) = 2 gp(H)。
这里Ps是s个顶点的路径图，其一般位置数gp(Ps) = 2（s≥2）。因此下界由Klavžar-Yero定理直接给出：2 gp(H)。关键在于证明上界也是2 gp(H)。这个结果意味着，无论H是什么图，只要与一条路径做强积，结果图的一般位置数就是H的一般位置数的两倍，与路径的长度s完全无关！这是一个非常强的结论，它表明路径作为因子时，强积图的一般位置数完全由另一个因子决定。

为此，作者引入了一个辅助图X = X(S)（称为X图）。对给定的S ⊆ V(Ps⊠H)，定义X的顶点集就是S，两个顶点u和v在X中相邻当且仅当 dPs(ux, vx) > dH(uy, vy)。也就是说，在强积距离中，x坐标上的距离严格大于y坐标上的距离时，才连边。这个定义非常巧妙：它捕捉了S中顶点对在x方向和y方向上距离的相对大小关系。如果x方向距离更大，就在X中连一条边，表示这个顶点对在x方向上是“主导”的。

这个定义引出一个重要性质：一个集合A ⊆ S在X中独立（即无边相连）当且仅当它是y-等距集——即对任意u,v ∈ A，有dH(uy, vy) ≥ dPs(ux, vx)。而Fact 1.5告诉我们，每个y-等距集的大小不超过gp(H)。类似地，x-等距集大小不超过gp(Ps) = 2。这个事实将X图的独立集与原图的一般位置数联系了起来：X的每个颜色类（独立集）对应一个y-等距集，其大小受限于gp(H)。因此，如果我们能控制X的色数χ(X)，就能得到|S|的上界。

那么X图有什么结构？Lemma 2.1证明X是二部图（bipartite）。证明很巧妙：假设X有奇圈，考虑最小奇圈，利用路径上的距离约束和三角形不等式推出矛盾。因为路径的端点距离性质迫使在奇圈上走一圈后符号交替，但奇数个顶点做不到。因此χ(X) ≤ 2。这个证明的核心思想是：在路径Ps上，距离函数具有线性序性质，沿着圈走一圈，x方向的距离变化必须满足某种“符号守恒”，而奇圈会导致符号无法匹配，从而产生矛盾。

接下来是核心的计数引理（Fact 1.6）：对任意一般位置集S of G⊠H（G是路径或圈），|S| ≤ χ(X) · gp(H)。证明很简单：对X进行χ(X)-染色，每个颜色类是一个独立集，从而是y-等距集，大小不超过gp(H)。由于χ(X) ≤ 2，立即得到|S| ≤ 2 gp(H)。这个引理是整篇论文的方法论核心：它将一般位置集的大小估计问题，转化为辅助图X的色数估计问题。只要我们能证明X的色数有一个小的上界，就能得到|S|的紧的上界。

这个结果非常干净：路径作为因子时，强积图的一般位置数就是路径自身值的两倍，与H无关！这是强乘积乘性猜想在路径上的肯定例子——但注意，这里并不是证明猜想成立，而是恰好因为路径的特殊性。路径的线性结构使得X图必然是二部图，从而色数不超过2，这恰好与gp(Ps)=2匹配。换句话说，路径情形之所以满足乘积公式，是因为路径本身的一般位置数就是2，而X图的色数也恰好是2，两者巧合地相等。

循环强乘积的界与反例

循环图Cs（s≥3）比路径复杂得多，因为循环有回绕。已知gp(Cs) = 3（s≠4时）或2（s=4时）。那么对于强积Cs ⊠ H，上界如何？循环的引入带来了一个根本性的困难：在路径上，距离函数是线性的，我们可以通过“符号”来区分方向；但在循环上，距离是环形的，没有天然的线性序。这使得X图可能不再是二部图，色数可能大于2。

Theorem 3.1给出了一个通用上界：gp(Cs ⊠ H) ≤ ⌊2s gp(H)/(⌊s/2⌋+1)⌋。推导思路是将循环Cs的顶点分成s个长度为h+1的连续弧（每个弧是等距路径），每个弧对应一个子图Ph+1 ⊠ H，其一般位置数不超过2 gp(H)。然后通过双计数每个顶点出现在h+1个弧中，得到上界。这个上界公式的推导非常巧妙：它利用了循环的对称性，将循环覆盖为若干个路径子图，然后利用路径情形的结果，再通过平均论证得到全局上界。当s为奇数时，h = ⌊s/2⌋，上界简化为⌊2s gp(H)/(h+1)⌋；当s为偶数时，h = s/2，上界为⌊2s gp(H)/(s/2+1)⌋。

对于小圈s=4,5,6，Theorem 3.5给出了精确值：
- gp(C4 ⊠ H) = 2 gp(H)
- gp(C5 ⊠ H) = gp(C6 ⊠ H) = 3 gp(H)
证明需要精细分析X图的色数。对于C4和C6，可以证明χ(X) ≤ 2（C4）或χ(X) ≤ 3（C5, C6），再配合Fact 1.6得到上界。其中用到了短边的概念：当dx(u,v)=1时，称为短边。Lemma 3.4证明短边形成匹配，且两个端点共享相同的y投影，并且是X中的真孪生顶点。这些性质帮助给X着色。具体来说，对于C4，由于循环长度为4，其距离结构具有某种“二分性”，使得X图仍然是二部图；而对于C5和C6，X图的色数上升到3，恰好等于gp(C5)=gp(C6)=3，因此乘积公式仍然成立。这些精确结果说明，对于小循环，乘性猜想仍然成立，但原因已经不再是路径情形那么简单了。

否定乘性猜想的关键构造

如果Klavžar-Yero猜想成立，那么对于两个圈Cs和Ct（s≠4且t≠4），应有gp(Cs ⊠ Ct) = 3×3 = 9。然而本论文在Section 4中构造了一系列反例，表明当周期足够大时，值可以超过9，达到10甚至11。这些反例的构造非常精巧：它们利用了循环的模运算结构，通过选取特定的“对角线”上的顶点，使得任意三个顶点都不在彼此的最短路径上。

Proposition 4.6列举了精确值：
- gp(C7⊠C7) = 10
- gp(C7⊠C9) = 10
- gp(C7⊠C11) = 10
- gp(C9⊠C9) = 10
- gp(C10⊠C10) = 10
- gp(C11⊠C11) = 11，且对于t=13,15,17,19,21,22，gp(C11⊠Ct) = 11。
这些下界通过构造具体的10个或11个顶点的一般位置集得到。例如，在C11⊠C11中，取集合S = {(i, 3i mod 11) : i=0,1,...,10}，直接验证即可。这个构造的灵感来源于数论中的模线性方程：选取的顶点在网格图上形成一条“斜线”，由于11是质数，3是模11的原根之一，这些点均匀分布在网格上，保证了任意两点之间的x距离和y距离具有特定的比例关系，从而避免了三点共线（在最短路径意义上）。

图1：一些循环强积中的大小为10的一般位置集 (a) C7⊠C7 (b) C7⊠C9 (c) C9⊠C9 (d) C7⊠C11

这些例子直接反驳了猜想。注意，上界由Theorem 3.1给出，在s=t=11时，上界为11，所以恰好tight。这意味着对于C11⊠C11，我们不仅知道猜想不成立（9不是正确答案），还知道精确值就是11，并且这个上界是可达的。对于C7⊠C7，Theorem 3.1给出的上界是⌊2×7×3/(3+1)⌋ = ⌊42/4⌋ = 10，而下界构造也是10，因此也是tight。这些结果说明，Theorem 3.1给出的上界对于某些循环对是紧的，但对于其他循环对可能还有改进空间。

更一般地，Lemma 4.10和4.12给出了伸缩构造：如果Cs⊠Ct中存在大小为n的一般位置集，那么对任意整数k，在Cks⊠Ckt（甚至轻微偏移长度）中也有大小为n的一般位置集。由此推出：当s≥121时，有gp(Cs⊠Cs) = 11。这表明上界11是可达的且无穷多。这个伸缩构造非常强大：它允许我们将一个小规模的反例“放大”到任意大的循环上，从而证明反例不是孤立的，而是存在于无穷多个循环对中。具体来说，如果我们在C11⊠C11中有一个大小为11的一般位置集，那么通过将每个顶点替换为一个k×k的块，就可以在C11k⊠C11k中得到同样大小为11的一般位置集。这个构造的关键在于，伸缩后的顶点集保持了原集合的“相对位置关系”，从而仍然满足一般位置集的条件。

因此，乘性猜想被彻底否定。并不是所有强积图都满足乘积公式。这个否定来得干净利落：Vesel不仅给出了反例，还系统地刻画了在什么情况下猜想成立（路径、小循环），在什么情况下不成立（大循环）。这种“既给出肯定结果又给出否定结果”的论文，在数学研究中是非常有价值的——它让我们对问题的理解更加全面和深刻。

总结与展望

本论文系统地刻画了强乘积中一个因子为路径或小圈时的一般位置数，给出了若干精确公式和上界，并通过构造反例否定了Klavžar-Yero的乘性猜想。主要贡献包括：

1. 证明gp(Ps⊠H)=2 gp(H)，路径情形完全解决。这个结果简洁优美，并且证明中引入的X图方法为后续研究提供了有力工具。

2. 对C4, C5, C6得到精确公式，对一般s给出上界。这些精确结果填补了小循环情形的空白，而上界公式则为一般循环提供了可计算的估计。

3. 构造了gp(Cs⊠Ct) > 9的反例，并证明当两个圈都很大时上界11可达。这些反例是论文的核心贡献，它们彻底否定了乘性猜想。

4. 提出了伸缩构造，生成无穷族验证上界tightness。这个构造具有通用性，可以应用于其他类似的乘积图问题。

未来方向包括：确定任意两个圈的一般位置数的精确公式（目前只有上界11和部分下界10）；研究其他图族（如完全图、树等）在强积下的乘性是否成立；以及将X图方法推广到其他乘积图。特别地，对于两个大循环的强积，目前的上界是11，但下界也是11（通过伸缩构造），因此gp(Cs⊠Ct)在s,t足够大时似乎稳定在11。但这是否对所有s,t≥11都成立？还是存在更大的值？这个问题仍然开放。此外，对于非循环图与循环的强积，例如树与循环的强积，其一般位置数会是什么？这些问题的解决可能需要更精细的分析工具。

龙迷三问

下面是龙哥对于大家可能的一些问题的解答：

Q1: 一般位置集和强积图在现实中有哪些应用？A: 图论中的一般位置概念源于组合几何，在一些网络拓扑、传感器布局、通信网络抗干扰等问题中可能有潜在应用。例如，在无线传感器网络中，我们希望部署的传感器节点之间没有“遮挡”关系，使得每个节点都能直接与其他节点通信而不经过中间节点转发，这类似于一般位置集的概念。不过本论文纯理论，更偏向图论结构本身。强积图作为一种重要的图乘积操作，在并行计算、网络设计等领域也有理论意义。

Q2: 文中的X图（X(S)）到底有什么用？A: X图是一个辅助图，它编码了强积图中顶点对在x投影和y投影上的大小关系。通过研究X的色数或独立数，可以关联到原图的一般位置数上界。这是证明上界的关键工具。具体来说，X图的每个独立集对应一个y-等距集，而y-等距集的大小不超过gp(H)。因此，如果我们能证明X图的色数不超过某个常数c，那么|S| ≤ c·gp(H)。在路径情形中，c=2；在小循环情形中，c=2或3。这个方法的优势在于，它将一个复杂的图论问题转化为一个相对简单的图着色问题，而着色问题往往有更成熟的分析工具。

Q3: 论文如何证明X是二部图（路径情形）？A: 反证法。假设X有一个奇圈，取最小奇圈，然后利用路径上距离的绝对值差以及三角不等式，推导出矛盾——因为沿奇圈走一圈后符号交替，但奇数个顶点无法做到。具体细节可看论文Lemma 2.1。更直观地说，在路径Ps上，我们可以给每个顶点赋予一个“方向”符号：如果从u到v的x距离大于y距离，就认为u和v之间有一条“正向边”。沿着圈走一圈，这些符号必须交替变化，但奇数个顶点会导致第一个和最后一个顶点的符号相同，从而产生矛盾。这个证明非常优雅，是整篇论文的技术亮点之一。

如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

龙哥点评

论文创新性分数：★★★★✰

思路清晰，用X图方法统一处理路径和循环，构造反例巧妙，但创新主要体现在否定猜想的构造上，整体属于扎实推进类工作。论文的方法论（X图）虽然不是全新的概念，但将其系统应用于强积图的一般位置问题，并取得了完整的结果，这种系统性的工作本身就有很高的价值。

实验合理度：★★★★★

纯图论定理证明，没有实验部分。论证严密，所有定理证明完整，反例列举详尽，无逻辑漏洞。论文中的每个定理都给出了完整的证明，每个反例都给出了显式的构造和验证，符合纯数学论文的最高标准。

学术研究价值：★★★★★

解决了强积图一般位置数的核心开放问题，对图论乘积结构研究有重要推动作用，后续很多工作可能以此为起点。这篇论文的发表意味着强积图一般位置数的研究进入了一个新阶段：不再追求普适的乘积公式，而是转向更精细的刻画和分类。

稳定性：N/A

纯理论结果，不涉及算法稳定性。

适应性以及泛化能力：★★★✰✰

仅针对强积图且至少一个因子是路径或圈，对更一般的图尚未解决。伸缩构造有一定通用性，但总体范围有限。论文的方法（X图）依赖于强积图的特殊距离结构，对于其他类型的图乘积（如笛卡尔积、字典积）可能不直接适用。

硬件需求及成本：N/A

纯数学推理，不涉及计算。

复现难度：★★★★★

（论文已开源？但未提及代码。不过图论证明完全文字化，读者可以逐行验证。构造的通用位置集用显式公式给出，容易验证。）对于有图论基础的读者，完全可以在纸上验证所有定理和反例，不需要任何计算设备。

产品化成熟度：★✰✰✰✰

纯理论研究，远离产品化。

可能的问题：论文对s≥7的一般圈的精确值未给出，仅给出上界11和部分下界。另外，对于非循环图（如树、完全图）与循环的强积，也没有完全刻画。但作为否定猜想的论文已经足够了。此外，论文中对于s=7,8,9,10等中等大小的循环，其精确值是否就是上界给出的值？还是存在更紧的上界？这些问题留待后续研究。不过，一篇论文不可能解决所有问题，Vesel的工作已经为这个方向奠定了坚实的基础。

主要参考文献

[1] S. Klavžar, I.G. Yero, The general position problem and strong resolving graphs, Open Math. 17 (2019) 1126–1135. (提出猜想)

[2] U. Chandran S.V., G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143. (一般位置集的起源)

[3] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second ed., CRC Press, 2011. (强积图的定义和基本性质)

[4] A. Vesel, General position sets in strong products with paths and cycles, arXiv:2607.26844v1, 2026. (本文)

*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！

图论猜想的推翻，往往需要一把巧妙的钥匙。想知道这把钥匙怎么打磨出来的？加入龙哥读论文粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称（如图论+上海+某某大学+龙哥），根据格式备注，可更快被通过且邀请进群。
wechat_helper