Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

技术摘要：强正则图上均匀平均混合的矩方法

问题陈述
本文研究了连通、非完全强正则图（SRGs）上连续时间量子行走是否存在均匀平均混合（Uniform Average Mixing, UAM）。UAM 定义为存在一个定义在 $[0, \infty)$ 上的 Borel 概率测度 $\mu$，使得时间平均混合矩阵等于均匀矩阵 $\frac{1}{n}J$，其中 $n$ 是顶点数。具体而言，本研究旨在确定哪些强正则图允许此类律的存在，并刻画这些律的性质（例如，它们是否可以由有界的密度、有限原子测度或单个观测时刻来实现）。这项工作解决了此前在文献中提出的关于量子行走平均值的谱矩视角下的开放问题。

方法论
作者采用了谱矩方法，将寻找时间律的无限维问题简化为有限维矩问题。

1. 谱约简： 利用强正则图的代数结构（特别是恒等式 $A^2 = (\lambda - \nu)A + (k - \nu)I + \nu J$），将混合矩阵 $M(t)$ 表示为与图的限制特征值相关的三个余弦矩。
2. 仿射约束： 证明 UAM 的条件等价于这三个矩满足的两个仿射约束，从而在 $\mathbb{R}^3$ 中定义了一条“矩线”。
3. 几何与代数工具：
   • Carathéodory 型定理： 作者利用 Carathéodory 定理的改进版本证明，对于任何平均混合矩阵，无论原始时间律如何，都可以由最多两个观测时刻（原子）来实现。
   • 矩问题： 对于具有非整数谱的图，作者利用 Fejér 多项式和 Gram 矩阵求逆，构造了显式的、在紧集上受限的有界时间密度。对于整数谱，他们利用有限 Toeplitz 和 Hankel 半正定矩阵推导出了充要条件。
   • 复 Hadamard 矩阵： 关键的一步是将存在位于矩线上且具有正定 Gram 矩阵的点，与 Bose–Mesner 代数中存在复 Hadamard 矩阵的联系起来。这使得无需依赖先前的分类定理或计算机计算即可对参数集进行分类。

主要贡献与结果

• 归约为两个时刻： 本文证明，对于任何连通的非完全强正则图，如果存在 UAM 律，则它可以由最多两个原子（观测时刻）的离散测度来实现。这简化了寻找 UAM 的过程，即只需检查特定的时刻对。
• 显式构造：
  • 对于具有非整数限制特征值的强正则图（非平方阶的会议图），作者构造了一个支撑在有限区间 $[0, T]$ 上的显式有界概率密度。
  • 对于整数谱，提供了一个有限半正定判据（Toeplitz/Hankel 形式）来确定其存在性。
• 完整分类： 本文确定了所有允许 UAM 的强正则图。除了具有瞬时均匀混合（IUM）特性的图和会议图外，UAM 仅由以下图（或其补图）允许：
  1. 参数为 $(4\theta^2 + 4\theta + 2, 2\theta^2 + \theta, \theta^2 - 1, \theta^2)$ 且 $\theta \ge 1$ 的图。
  2. 参数为 $(4\theta^2 - 1, 2\theta^2, \theta^2, \theta^2)$ 且 $\theta \ge 2$ 的图。
  • Petersen 图及其补图被确定为这些族中最小的成员。
• 密度与原子的二分性： 文中建立了一种二分关系：具有 UAM 的图允许有界时间密度，当且仅当它不具备瞬时均匀混合（IUM）。如果存在 IUM，则 UAM 律必须集中在离散集上。
• 对前人工作的修正： 本文修正了 Godsil, Mullin, 和 Roy 关于强正则图上瞬时均匀混合的分类。研究指出，他们的符号条件错误地排除了半 5 维立方体（该图在 $t=\pi/4$ 时实现均匀混合），并错误地包含了参数 $(36, 14, 4, 6)$，而后者并不存在 UAM 律。修正后的分类依赖于 $n$ 被 16 整除以及特定 Hadamard 矩阵的存在。

意义与主张
本文声称提供了允许均匀平均混合的强正则图的完整且自洽的分类。其重要性在于：

• 统一性： 它将 UAM 的研究与 Bose–Mesner 代数中的复 Hadamard 矩阵理论统一起来，为 Chan 在此背景下的分类提供了一个简短、基础的证明。
• 精确性： 它为整数谱情况提供了精确的、非渐近的判据（有限半正定条件），并为非整数谱情况提供了显式构造。
• 解决开放问题： 它回答了关于混合时间的有理性和 IUM 在强正则图类中的谱条件的特定开放问题。
• 方法论严谨性： 该分类的推导并未依赖计算机计算或先前的分类定理，而是仅使用了初等不等式和矩理论。

作者强调，其结果对于连通、非完全强正则图这一类具有决定性意义，明确划分了哪些图允许连续密度、哪些需要离散原子律，以及哪些完全不具备均匀平均混合。