A note on Ramsey numbers for minors

该论文确定了拉姆齐数 $R_h(k; \ell)$ 的渐近阶，证明了在两种颜色情形下其上下界均为 $k\sqrt{\log k}$ 量级，而在 $\ell$ 种颜色情形下其渐近值为 $2\beta \ell k\sqrt{\log k}$（其中$\beta \approx 0.265656$）。

要点

这篇论文探讨了一个非常有趣的数学问题，我们可以把它想象成一场**“色彩与形状的捉迷藏游戏”**。

为了让你轻松理解，我们先把里面的专业术语翻译成生活中的概念：

1. 核心概念：什么是“拉姆齐数”和“ minors（子式）”？

• 拉姆齐数（Ramsey Number）：
  想象你有一大群朋友（顶点），你们之间两两都要握手（边）。现在，你手里有几种颜色的马克笔（比如红色和蓝色）。你要给每一对朋友的握手连线涂上颜色。
  拉姆齐问题问的是： 至少需要多少个人，才能保证不管你怎么涂色，人群中总会有一群人，他们之间的连线全是同一种颜色（比如全是红色），并且这群人里包含某种特定的“结构”？

• 什么是“ minors（子式）”？
  在传统的拉姆齐问题中，我们要找的是“完全图”（比如 3 个人互相认识，形成一个三角形 $K_3$）。
  但这篇论文玩得更高级。它不要求大家必须“完全互相认识”，而是允许我们玩一个**“变形游戏”**：

  1. 合并： 把两个朋友“粘”在一起，变成一个人。
  2. 删除： 把某些朋友踢出圈子。
     如果通过这种“粘人”和“踢人”的操作，你能从这群人里变出一个 $k$ 个人的小团体（完全图 $K_k$），那么这群人就被称为拥有**"k 阶子式”**。
  • 简单比喻： 就像是用乐高积木搭房子。传统的拉姆齐数要求你直接找到一块完美的 $k$ 块积木拼成的房子。而这篇论文说的是：只要你能把现有的积木拼凑、粘合一下，最后能变出一个 $k$ 块积木的房子，就算你赢了。

2. 这篇论文在做什么？

作者 Maria Axenovich 想要解决一个具体的问题：
如果我们有 $k$ 个目标（想要变出一个 $k$ 阶子式），并且我们只有 2 种颜色（红和蓝），那么我们需要至少多少人（$n$），才能保证无论怎么涂色，总有一种颜色的连线能变出这个目标？

这个最小的 $n$ 就是论文研究的 $Rh(k; 2)$。

3. 主要发现：人数大概是多少？

作者通过复杂的数学推导，给出了一个非常精确的“人数估算公式”。

• 以前的认知： 我们知道人数肯定和 $k$ 有关，但具体是多少一直不清楚。
• 作者的发现： 人数大约等于 $k \times \sqrt{\log k}$。
  • 这里的 $\log k$ 就像是一个“增长加速器”。如果 $k$ 是 100，$\sqrt{\log 100}$ 大概是 3 左右。所以你需要的人数大概是 $100 \times 3 = 300$人，而不是$100$人，也不是$10000$ 人。
  • 作者不仅给出了这个公式，还非常精确地算出了前面的系数（大约是 1.031）。这意味着，只要人数达到这个数值的 1.031 倍，你就100% 能找到那个“变形后的目标”。

通俗比喻：
想象你在玩一个巨大的拼图游戏。

• $k$ 是你想要拼出的最终图案的大小。
• 颜色是拼图块的两种属性（比如红边和蓝边）。
• 论文告诉你：只要你的拼图板（总人数）大到 $k$ 乘以根号下对数 $k$ 那么大，不管你怎么乱涂乱画，你总能在一堆同色的碎片里，通过“粘合”和“丢弃”一些碎片，拼出你想要的图案。

4. 论文里的“侦探故事”

作者是如何证明这个结论的？她用了两种策略：

1. 证明“人多了肯定行”（上界）：
   她利用了一个关于“图密度”的著名定理（Thomason 定理）。

   • 逻辑： 如果人群足够大，那么无论你怎么分颜色，总有一种颜色的连线会非常“密集”（就像在一个拥挤的房间里，大家互相认识的概率很高）。
   • 推论： 一旦某种颜色的连线足够密集，根据数学定理，它里面就必然藏着可以通过“变形”得到的 $k$ 阶子式。作者通过精细计算，把“足够大”这个门槛压得很低，算出了那个 1.031 的系数。

2. 证明“人少了可能不行”（下界）：
   她构造了一个“反例”。

   • 逻辑： 如果人数稍微少一点点（比如 $k \sqrt{\log k}$ 再少一点），她可以设计一种涂色方案（利用随机图），让红色和蓝色都变得“稀疏”且“分散”。
   • 结果： 在这种方案下，无论你怎么“粘合”或“删除”，都变不出 $k$ 阶子式。这证明了人数不能太少。

5. 为什么这很重要？

• 填补空白： 虽然数学家们研究“拉姆齐数”研究了几十年，也研究“图子式”研究了几十年，但把这两个概念结合起来（即“带子式的拉姆齐数”）之前几乎没人专门算过。这篇论文是第一次系统地给出了答案。
• 连接经典猜想： 这个问题和著名的**“哈德维格猜想”（Hadwiger Conjecture）**有关。哈德维格猜想说：如果一个图很难用很少的颜色染色（色数高），那它一定包含很大的子式。这篇论文从“随机性”和“极值”的角度，为理解这种结构提供了新的视角。
• 多色扩展： 论文还顺便讨论了如果有 3 种、4 种甚至更多颜色（$\ell$ 种颜色）的情况，发现人数会随着颜色数量线性增加。

总结

这篇论文就像是一个**“数学预言家”。它告诉我们：
在一个由无数人组成的社交网络中，如果你只给关系线涂上两种颜色，只要人数达到 $k$ 乘以根号下对数 $k$ 这个量级，你就绝对无法逃脱**在某种颜色里找到一个可以通过“变形”得到的 $k$ 人核心圈子。

这不仅是数学上的精确计算，也揭示了复杂网络中**“无序中的必然有序”**这一深刻规律：无论你怎么随机打乱，只要基数够大，特定的结构（哪怕是可以变形的结构）总会顽强地冒出来。

技术摘要

1. 研究问题 (Problem)

本文主要研究子式 Ramsey 数（Ramsey numbers for minors），记为 $R_h(k; \ell)$。

• 定义：$R_h(k; \ell)$ 是最小的整数 $n$，使得对完全图 $K_n$ 的边进行 $\ell$ 种颜色的任意着色，必然存在一个单色子图，其**Hadwiger 数（Hadwiger number）**至少为 $k$。
• Hadwiger 数 $h(G)$：图 $G$ 的 Hadwiger 数是指 $G$ 中包含的完全图 $K_k$ 子式（minor）的最大阶数 $k$。即，$K_k$ 可以通过对 $G$ 进行边收缩（edge contractions）和顶点删除（vertex deletions）得到。
• 背景：
  • 经典的 Ramsey 数 $R(k)$ 对应于 $R_\omega(k)$，其中参数 $\omega(G)$ 是团数（clique number）。
  • Hadwiger 猜想（Hadwiger conjecture）指出 $h(G) \ge \chi(G)$（色数），这是图论中的核心未解问题之一。
  • 尽管 Hadwiger 猜想及相关密度问题（如 Thomason 关于 $c(k)$ 的研究）已有大量文献，但显式地研究子式 Ramsey 数 $R_h(k; \ell)$ 在文献中似乎从未被直接探讨过。

2. 方法论 (Methodology)

作者结合了极值图论、随机图理论以及图分解（graph decomposition）技术来推导上下界。

• 上界推导 (Upper Bounds)：

  • 密度论证：利用 Thomason 关于图密度的结果（Theorem 1.1），即对于平均度足够高的图，其 Hadwiger 数有下界。
  • 多数色类分析：在 $\ell$ 色着色中，必然存在一个颜色类（子图）拥有至少 $1/\ell$比例的边。如果该子图的边密度足够高，根据 Thomason 的定理，其 Hadwiger 数将超过$k$。
  • 连通性细分：针对连通性较低的情况，作者通过寻找诱导子图、分析最小度以及利用补图中的结构（如 $K_{k,k}$）来证明单色 $K_k$-子式的存在。
  • 小参数特例：对于小的 $k$（如 $k=3, 4$），通过具体的构造和穷举分析（如利用 $K_4$-minor-free 图的最大边数界限 $2n-3$）来确定精确值。

• 下界推导 (Lower Bounds)：

  • 随机图构造：利用 Erdős-Rényi 随机图 $G(n, p)$ 的性质。根据 Bollobás, Catlin, 和 Erdős 的定理，随机图的 Hadwiger 数约为 $n \sqrt{\frac{\log(1/q)}{\log n}}$。通过设置 $n$ 略小于目标值，使得随机图中几乎必然不存在 $K_k$-子式。
  • 图分解与打包 (Packing and Decomposition)：
    • 利用 Wilson 定理（关于图的分解）和 Alon-Yuster 定理（关于边着色）。
    • 构造一个不含 $K_k$-子式的图 $H$（基于 Thomason 的极值图），并将其作为“因子”打包进 $K_n$。
    • 通过给每个 $H$ 副本分配不同颜色，并处理剩余边（分解为森林），构造出一个不含单色 $K_k$-子式的着色方案。

3. 关键贡献与主要结果 (Key Contributions & Results)

主要定理 1.4：双色情况 ($R_h(k; 2)$)

作者确定了 $R_h(k; 2)$ 的渐近行为：
$$k\sqrt{\log k}(1 + o(1)) \le R_h(k; 2) \le 1.031 \cdot k\sqrt{\log k}(1 + o(1))$$

• 下界：由随机图 $G(n, 1/2)$ 的性质直接得出。
• 上界：通过精细的连通性分析和密度论证，将常数从初步的 $2\sqrt{\beta} \approx 1.062$优化至$1.031$。
• 精确小值：
  • $R_h(3) = 5$
  • $R_h(4) = 7$
  • 对于 $k \ge 5$，给出了 $2(k-2) \le R_h(k) \le 32(k-2)^{\lfloor \log(k-2) \rfloor} + 1$ 的界限。

主要定理 1.5：多色情况 ($R_h(k; \ell)$)

对于任意颜色数 $\ell \ge 1$：

• 精确小值：$R_h(3; \ell) = 2\ell + 1$。
• 渐近公式：存在常数 $\beta = 0.265656\dots$（由 Thomason 定义，与方程 $1-\lambda + 2\lambda \ln \lambda = 0$的解有关），使得对于足够大的$k$和$\ell$：
  $$R_h(k; \ell) = 2\beta \ell k \sqrt{\log k} (1 + o(1))$$
  这意味着 $R_h(k; \ell)$ 与 $\ell$ 呈线性关系，且主导项为 $k\sqrt{\log k}$。

常数 $\beta$ 的定义

$\beta$ 源自 Thomason 关于图密度与 Hadwiger 数关系的研究：
$$\beta = \frac{1-\lambda}{2\sqrt{\ln(1/\lambda)}} \cdot \frac{1}{\sqrt{\log_2 e}} \approx 0.265656$$
其中 $\lambda$ 是方程 $1 - \lambda + 2\lambda \ln \lambda = 0$ 的解。

4. 意义与影响 (Significance)

1. 填补文献空白：这是首次显式地定义并系统研究子式 Ramsey 数 $R_h(k; \ell)$，将经典的 Ramsey 理论推广到了图子式（minor）这一重要参数上。
2. 连接 Hadwiger 猜想与 Ramsey 理论：该研究将 Hadwiger 猜想（关于色数与子式的关系）与 Ramsey 理论（关于单色结构的必然性）联系起来，揭示了在边着色下，为了强制出现高 Hadwiger 数所需的图规模。
3. 渐近紧确性：论文不仅给出了上下界，而且证明了上下界在渐近意义上是匹配的（除了常数因子），特别是确定了 $R_h(k; \ell)$ 的增长阶数为 $\Theta(\ell k \sqrt{\log k})$。
4. 方法创新：展示了如何将极值图论中的密度定理（Thomason 定理）与组合设计中的图分解技术（Wilson 定理、Nash-Williams 定理）结合，以解决 Ramsey 型问题。
5. 未来方向：作者推测 $R_h(k; 2)$ 的常数 $c$ 实际上等于 1（即 $R_h(k; 2) \sim k\sqrt{\log k}$），并指出寻找一个不依赖密度定理的直接证明是一个有趣的方向。

总结

这篇论文通过严谨的极值图论分析和构造性证明，确立了子式 Ramsey 数的渐近行为。它表明，为了在 $\ell$ 色着色的完全图中强制出现一个 Hadwiger 数为 $k$ 的单色子图，所需的顶点数 $n$ 大致为 $2\beta \ell k \sqrt{\log k}$。这一结果不仅深化了对 Hadwiger 数性质的理解，也为图论中的 Ramsey 理论开辟了一个新的研究分支。