The $\Delta$ property: a bridge between split graphs and Number Theory

技术摘要：$\Delta$-性质：分裂图与数论之间的桥梁

问题陈述
本文探讨了分裂图及其实现图理论中的一个特定结构问题。对于分裂图 $S$，保持度序列的 2-交换（局部边交换）的组合结构被编码在一个称为因子图 $\Phi(S)$ 的多重图中。$\Phi(S)$ 的顶点对应于 $S$ 的独立集，而边的重数记录了同时进行的 2-交换的数量。

核心问题（问题 1.1）是：对于哪些自然数 $n$，存在一个分裂图 $S$，使得 $\Phi(S)$ 包含一个类型为 0 的 $n$-简单三角形？$n$-简单三角形是指每条边的重数均为 $n$ 的三角形。“类型为 0"的三角形指的是在关联的流配置 $\vec{\Phi}(S)$ 中，三角形具有特定的方向，其中沿边的度数增加形成一致的层级结构（具体而言，$d_c > d_b > d_a$ 且 $d_c - d_a = (d_b - d_a) + (d_c - d_b)$）。

方法论
作者建立了此类图结构的存在性与整数 $n$ 的纯算术条件之间的双向对应关系。

1. 从图到数论：作者分析了 $\Phi(S)$ 中边重数的公式 $\sigma_{uv} = (d_u - \eta_{uv})(d_v - \eta_{uv})$，其中 $\eta_{uv}$ 是邻域交集的大小。他们证明，如果 $\Phi(S)$ 是一个类型为 0 的 $n$-简单三角形，则独立集中顶点的度数差必须满足涉及 $n$ 的互补因子的特定加法关系。
2. 从数论到图论：反之，给定满足算术条件的数 $n$，作者构造了一个具有大小为 3 的独立集的平衡分裂图。他们明确定义了度数和邻域交集，以确保生成的因子图是所需的 $n$-简单三角形。
3. 算术分析：本文系统地研究了满足该条件的整数集合 $N(\Delta)$。它利用因子性质、$\Delta$-三元组（满足特定方程的因子三元组 $(x, y, z)$）的界限以及生成多项式来刻画该集合。

关键定义与 $\Delta$-性质
本文定义了自然数 $n$ 的$\Delta$-性质：
设 $D_n$ 为 $n$ 的正因子集合。
设 $D^*_n = \{ |a - b| : a, b \in D_n, ab = n \}$（互补因子的差）。
设 $D^+_n = \{ x + y : x, y \in D^*_n \setminus \{0\} \}$（非零差的和）。
如果 $D^*_n \cap D^+_n \neq \emptyset$，则数 $n$ 具有 $\Delta$-性质。

该条件等价于存在 $n$ 的因子构成的$\Delta$-三元组 $(x, y, z)$，使得 $1 < x < y \le z < \sqrt{n}$ 且满足：
$$\frac{n}{x} - x = \left(\frac{n}{y} - y\right) + \left(\frac{n}{z} - z\right)$$

主要贡献与结果

1. 桥梁定理（定理 1.2）：
   本文证明了 $n \in N(\Delta)$ 当且仅当存在一个不可分解的分裂图 $S$，使得 $\Phi(S)$ 是一个类型为 0 的 $n$-简单三角形。这建立了一座双向桥梁：

   • 正向：数论数据（$\Delta$-三元组）产生特定的图实现。
   • 反向：特定的组合构型（三角形）迫使边重数 $n$ 满足 $\Delta$-条件。

2. $\Delta$-三元组的结构界限：
   作者推导了关于 $\Delta$-三元组最小分量 $x$ 的 $n$ 的最优上界。

   • 对于 $y=z$ 的情形，$n \le x(2x-1)(3x-2)$。
   • 对于 $y<z$ 的情形，$n \le x^2(x+1)^2(x^2+x-1)$。
     这些界限被证明是紧确的。

3. $N(\Delta)$ 的数论结构：

   • $\Delta$-原数：如果一个数在 $N(\Delta)$ 中，但不能写成 $\alpha^2 m$ 的形式（其中 $\alpha \ge 2$ 且 $m \in N(\Delta)$），则称该数为 $\Delta$-原数。本文表明，每个 $n \in N(\Delta)$ 都可以分解为一个平方数与一个 $\Delta$-原数的乘积。
   • 无穷性：集合 $N(\Delta)$ 是无限的。作者利用素数 $p$ 的三次多项式生成器 $F(p) = p(2p-1)(3p-2)$ 证明了存在无穷多个 $\Delta$-原数（定理 3.10）。
   • 唯一性：虽然分解为平方数和原数在一般情况下不唯一（例如 $5616$），但如果原数部分互质，则分解是唯一的。
   • 生成多项式：本文构造了无穷多个三次多项式族 $n(x)$，其值在 $x$ 足够大时属于 $N(\Delta)$。它证明了对于“重复”方法（$y=z$），不存在次数 $\ge 4$ 的此类生成多项式；对于通用情况（$y<z$）且 $k=3$ 个因子时，不存在线性族。

4. 障碍与刻画：
   本文识别了不满足 $\Delta$-性质的整数族：

   • 形式为 $2k$ 的数，其中 $k$ 为奇数。
   • 素数幂 $p^k$（对于任意素数 $p$）。
   • 两个素数的乘积 $pq$，$p^2q$，$pq^2$，$p^2q^2$。
   • 数 $p^k$，其中 $p \ge k$。
   • 数 $p^x q^y$，其中 $q > p^x$。
   • 对于三个不同素数 $pqr$的乘积，提供了完整的刻画：$pqr \in N(\Delta)$当且仅当$p, q, r$ 满足特定的丢番图条件（定理 5.15）。

5. 图论推论：
   本文将算术障碍翻译回图论。如果 $n$ 不是平方数且 $n \notin N(\Delta)$，则因子图 $\Phi(S)$ 中任何 $n$-简单诱导环的长度必须为 4（定理 5.19）。这意味着 $n$-简单三角形的存在性严格受 $\Delta$-性质支配。

意义与主张
本文声称在图论与数论之间建立了一座“双向桥梁”。

• 动机：通过将特定对称组合结构（分裂图因子图中的 $n$-简单三角形）的可实现性问题简化为纯算术条件，解决了该问题。
• 新颖性：引入了 $\Delta$-性质作为一个新的数论对象，分析了其原初元素、生成函数及障碍。
• 局限性/未解决问题：本文谦逊地指出，是否存在无穷多个 $\Delta$-原平方数的问题仍然悬而未决（猜想 3.11）。它建议这可能通过椭圆曲线 $y^2 = f(x)$ 上的整数点（其中 $f$ 是生成多项式）来探讨，但并未解决该猜想。此外，它指出 $n$-简单 4-环的刻画是未来工作的未探索领域。

该工作并未声称在分裂图中 2-交换动力学与因子算术的理论统一之外有广泛的应用，也未提出实验方法。其主要贡献是对存在特定图论构型的整数 $n$ 进行了严格分类。