Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings

本文确定了由 $k$ 条不相交的 3 顶点路径和 $t$ 条不相交的边（其中 $n=3k+2t$）构成的所有 $k \ge 1$ 且 $t \ge 2$ 的生成线性森林的反拉姆齐数，从而在不依赖先前研究中限制条件的情况下解决了该问题。

要点

想象你举办了一场盛大的派对，宾客数量极多。我们将宾客总数记为 $n$。在这场派对中，每一位宾客都与其他每一位宾客恰好握手一次。用数学术语来说，这就是一个“完全图”（$K_n$）。

现在，想象你是派对策划人，手中有一大盒彩色马克笔。你的任务是为每一次握手（边）涂上特定的颜色。你希望让派对尽可能色彩斑斓，但你有一条严格的规定：你必须避免形成某种特定的“彩虹模式”。

被禁止的模式

你要避免的模式是由若干个小而分散的人群组成的集合：

1. $k$ 组三人，他们站成一排（即包含 3 个顶点的路径，或 $P_3$）。
2. $t$ 对两人，他们站在一起（即包含 2 个顶点的匹配，或 $P_2$）。

所谓的“彩虹”模式，意味着这些特定群体内部的每一次握手，其颜色都必须与该群体内其他任何一次握手的颜色不同。如果模式中哪怕有两次握手共享了同一种颜色，该模式就被“破坏”了，你就安全了。

核心问题

这篇论文提出的问题是：在不意外形成这种被禁止的彩虹模式的前提下，你最多可以使用多少种不同的颜色来给派对上的所有握手涂色？

在数学领域，这个最大数值被称为反拉姆齐数（Anti-Ramsey Number）。

此前的困境

长期以来，数学家们虽然知道这个问题的答案，但仅限于非常严格的条件下。这就好比说：“如果配对的数量（$t$）远大于三人组（$k$）的数量，我们就知道答案。”具体来说，先前的研究要求 $t$ 大约是 $k$ 的平方（即二次关系）。如果 $t$ 小于这个数值，数学推导就无法成立，答案也就未知。

新发现

这篇论文解决了最关键且最棘手的场景：“全覆盖”情形。

将“全覆盖情形”想象为派对刚好坐满的时刻。宾客总数（$n$）恰好等于构成被禁止模式所需的人数：

• $n = 3 \times (\text{三人组的数量}) + 2 \times (\text{配对的数量})$
• $n = 3k + 2t$

作者 Ali Ghalavand 和 Xueliang Li 证明了，你不再需要 $t$ 非常大。只要至少有一个三人组（$k \ge 1$）且至少有两个配对（$t \ge 2$），他们就找到了最大颜色数量的精确公式。

公式

论文声称，你可以使用的最大颜色数量为：
$$\frac{1}{2}(3k + 2t - 3)(3k + 2t - 4) + 1$$

用通俗的英语来说这是什么意思？
如果你尝试使用的颜色数量超过这个数值，从数学上讲，你必然会被迫意外地创造出那个被禁止的彩虹模式（即 $k$ 个三人组和 $t$ 个配对，且所有颜色均不相同）。但如果你坚持使用这个数量或更少的颜色，你就可以安排颜色，使得该模式永远不会出现。

他们是如何证明的

作者采用了一种巧妙的“分而治之”策略，将其分解为 16 种不同的情形（类似于检查颜色排列的每一种可能方式）：

1. 下界（“安全”方式）：他们展示了一种方法，可以用公式中给出的颜色数量给图涂色，而不会形成该模式。想象一下，取派对的一大部分，将其全部涂上独特的颜色，然后将所有剩余的握手只涂上一种新颜色。这会破坏任何潜在的彩虹模式，因为那些“额外”的握手共享了同一种颜色。
2. 上界（“危险”方式）：他们证明了，如果你尝试使用哪怕多一种颜色，你就被迫会创造出该模式。他们通过假设你没有创造出该模式，然后展示这在数学上会导致矛盾（就像试图把方形的塞子塞进圆形的孔里）来做到这一点。他们分析了颜色在“额外”宾客（即不在主群体中的 3 人）之间分配的所有可能方式，并表明无论如何，该模式最终都会出现。

结论

这篇论文消除了“二次下界”的限制。它告诉我们，在派对规模恰好与被禁止模式规模相匹配的特定情况下，无论你有三个组还是配对，答案都是简单且普适的。这是图论领域中一个特定且困难的谜题的完整解决方案。

技术摘要

技术摘要：3 顶点路径与匹配的生成线性森林的反拉姆齐数

问题陈述
本文研究了完全图 $K_n$ 中一类特定线性森林的反拉姆齐数，记为 $AR(n, G)$。若一个子图的所有边具有不同的颜色，则称该子图为“彩虹”子图。反拉姆齐数$AR(n, G)$定义为$K_n$的边着色中不包含$G$ 的彩虹副本所能拥有的最大颜色数。

本研究的具体图 $G$ 为线性森林 $kP_3 \cup tP_2$，由 $k$ 条互不相交的长度为 2（即 3 个顶点）的路径和一个大小为 $t$（互不相交的边）的匹配组成。主要关注的是生成情形，即宿主图的顶点数等于森林的顶点数，亦即 $n = 3k + 2t$。虽然先前的文献已在 $t$ 的限制条件下（具体为 $t \ge \frac{k^2-3k+4}{2}$）解决了 $k \ge 2$ 的情况，但本文旨在解决所有 $k \ge 1$ 和 $t \ge 2$ 的生成情形，且不对 $k$ 与 $t$ 之间的关系施加额外约束。

方法论
主定理的证明依赖于归纳法与对边着色的详细情形分析相结合。方法论结构如下：

1. 归纳框架：证明通过对 $k$ 进行归纳进行。基础情形 $k=1$ 利用 He 和 Jin 关于 $AR(n, P_3 \cup tP_2)$ 的已知结果建立。
2. 关键引理（引理 2.2）：建立了一个关键引理以处理归约步骤。该引理断言，如果 $K_n$ 的边着色包含足够多的颜色（具体为 $\frac{1}{2}(3k+2t-3)(3k+2t-4)+2$），则存在一个子图 $K_{n-3}$（通过移除 3 个顶点获得），该子图保留了高密度的不同颜色，具体至少为 $\frac{1}{2}(3(k-1)+2t-3)(3(k-1)+2t-4)+2$。这使得可以应用归纳假设，在 $K_{n-3}$ 中找到一个彩虹 $(k-1)P_3 \cup tP_2$。
3. 详尽情形分析：为了完成归纳，作者分析了被移除顶点集 $S = \{s_1, s_2, s_3\}$ 与图其余部分连接的边，以及 $S$ 内部边所分配的颜色。证明假设 $K_{n-3}$ 中存在一个彩虹 $(k-1)P_3 \cup tP_2$，并根据集合 $S$ 中边的颜色分布及其与现有彩虹子图颜色的交集，考察了 16 种不同情形。
   • 这些情形涵盖了各种配置，例如 $S$ 中的边是否引入新颜色、是否重复现有子图中的颜色，或者是否形成特定的彩虹路径（$P_3$）或匹配（$P_2$），从而可以与现有结构结合。
   • 对于每种情形，作者证明如果总颜色数超过所提出的界限，则可以构造出一个彩虹 $kP_3 \cup tP_2$。
   • 如果无法立即进行此类构造，作者通过计算在假设不满足形成彩虹子图的具体条件下 $K_n$ 中可能的最大颜色数，推导出矛盾。在所有情况下，该上界均低于假设的颜色数，从而证明彩虹子图必然存在。

主要贡献与结果
本文确立了生成线性森林 $kP_3 \cup tP_2$ 的反拉姆齐数的精确值。

定理 1.1：对于正整数 $k \ge 1$，$t \ge 2$，且 $n = 3k + 2t$：
$$AR(n, kP_3 \cup tP_2) = \frac{1}{2}(3k + 2t - 3)(3k + 2t - 4) + 1$$

该结果证实，不含彩虹 $kP_3 \cup tP_2$ 的 $K_n$ 着色中，最大颜色数恰好比 $n-3$ 个顶点的完全图中的边数多 1。本文提供了一个匹配的构造下界（用不同颜色对 $K_{n-3}$ 子图进行着色，并将所有剩余边分配为单一新颜色），并通过上述详尽的情形分析证明了上界。

意义
这项工作的意义在于消除了先前研究中要求的关于 $t$ 的二次下界。具体而言，两位作者之前的结果（参考文献 [11]）仅确定了 $t \ge \frac{k^2-3k+4}{2}$ 时的该数值。本文证明了该公式适用于所有 $t \ge 2$，无论 $k$ 的大小如何。

作者将此描述为对“宿主图顶点数与森林顶点数完全相同”这一临界情形提供了“完整刻画”。通过在不限制路径分量与匹配分量比例的情况下解决生成情形，本文填补了线性森林反拉姆齐数理解中的一个重大空白。作者指出，剩余的开问题是在 $t$ 较小时改进非生成情形（$n \ge 3k + 2t + 1$）的结果。