2025-11-10T03:09:09.120069

Geometry of Random Cayley Graphs of Abelian Groups

Hermon, Olesker-Taylor

Consider the random Cayley graph of a finite Abelian group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll \log k \ll \log |G|$. Draw a vertex $U \sim \operatorname{Unif}(G)$. We show that the graph distance $\operatorname{dist}(\mathsf{id},U)$ from the identity to $U$ concentrates at a particular value $M$, which is the minimal radius of a ball in $\mathbb Z^k$ of cardinality at least $|G|$, under mild conditions. In other words, the distance from the identity for all but $o(|G|)$ of the elements of $G$ lies in the interval $[M - o(M), M + o(M)]$. In the regime $k \gtrsim \log |G|$, we show that the diameter of the graph is also asymptotically $M$. In the spirit of a conjecture of Aldous and Diaconis (1985), this $M$ depends only on $k$ and $|G|$, not on the algebraic structure of $G$. Write $d(G)$ for the minimal size of a generating subset of $G$. We prove that the order of the spectral gap is $|G|^{-2/k}$ when $k - d(G) \asymp k$ and $|G|$ lies in a density-$1$ subset of $\mathbb N$ or when $k - 2 d(G) \asymp k$. This extends, for Abelian groups, a celebrated result of Alon and Roichman (1994). The aforementioned results all hold with high probability over the random Cayley graph.

academic

Geometry of Random Cayley Graphs of Abelian Groups

基本信息

论文ID: 2102.02801
标题: Geometry of Random Cayley Graphs of Abelian Groups
作者: Jonathan Hermon (University of British Columbia), Sam Olesker-Taylor (University of Bath)
分类: math.PR (Probability), math.CO (Combinatorics)
发表时间: 2021年2月 (arXiv v2: 2025年10月)
论文链接: https://arxiv.org/abs/2102.02801

摘要

本文研究有限阿贝尔群 $G$ 的随机Cayley图的几何性质，其中 $k$ 个生成元均匀随机选择，且 $1 \ll \log k \ll \log |G|$ 。作者证明了从单位元到随机顶点 $U \sim \operatorname{Unif}(G)$ 的图距离 $\operatorname{dist}(\mathsf{id},U)$ 集中在特定值 $M$ 附近，该值是 $\mathbb{Z}^k$ 中基数至少为 $|G|$ 的球的最小半径。在 $k \gtrsim \log |G|$ 的情形下，图的直径也渐近于 $M$ 。符合Aldous-Diaconis猜想的精神， $M$ 仅依赖于 $k$ 和 $|G|$ ，而不依赖于 $G$ 的代数结构。此外，作者证明了当 $k - d(G) \asymp k$ 时谱间隙的阶为 $|G|^{-2/k}$ ，扩展了Alon-Roichman的经典结果。

研究背景与动机

问题背景

随机Cayley图模型: Aldous和Diaconis在1985年引入了随机Cayley图模型，通过从群 $G$ 中独立均匀选择 $k$ 个生成元来构造Cayley图。这一模型旨在研究"典型"随机游走在群上的行为。
几何性质研究: 传统研究主要关注固定 $k$ 的情况，而本文考虑 $k$ 随 $|G|$ 增长的情形，这允许研究更广泛的群类，特别是 $d(G)$ 随 $|G|$ 增长的群。
普遍性问题: Aldous-Diaconis猜想预测某些统计量应该"独立于群的代数结构"，即仅依赖于 $k$ 和 $|G|$ 。

研究动机

典型距离集中性: 理解随机Cayley图中从单位元到随机顶点的距离分布
直径估计: 确定图直径的渐近行为
谱性质: 分析随机游走的谱间隙，这与混合时间密切相关
普遍性验证: 验证这些几何量是否真的只依赖于 $k$ 和 $|G|$

核心贡献

典型距离集中定理: 证明了在三个不同的 $k$ 范围内（ $1 \ll k \ll \log |G|$ 、 $k \asymp \log |G|$ 、 $k \gg \log |G|$ ），典型距离都集中在明确的值附近。
直径集中性: 对于 $k \gtrsim \log |G|$ ，证明了直径与典型距离渐近相等。
谱间隙精确估计: 将Alon-Roichman定理扩展到阿贝尔群情况，给出了谱间隙的精确阶 $|G|^{-2/k}$ 。
幂零群扩展: 将部分结果扩展到幂零群，证明了阿贝尔化的主导作用。
普遍性结果: 证明了对于 $k - \log^2 |G| \asymp k$ 的情况， $\mathbb{Z}_2^d$ 给出最大直径。

方法详解

任务定义

研究随机Cayley图 $G_k$ 的几何性质，其中：

$G$ 是有限阿贝尔群
$Z_1, \ldots, Z_k \sim \text{Unif}(G)$ 独立同分布
典型距离定义为 $D_{G_k}(\beta) := \min\{R \geq 0 : |B_{G_k}(R)| \geq \beta|G|\}$

核心技术方法

1. 反向方法论 (§2.2)

与传统方法相反，本文使用混合技术证明几何结果：

通过分析辅助随机变量的混合性质
利用 $L^2$ 距离估计证明典型距离的上界

2. 格球估计 (§2.3, §3.3, §4.3)

对于不同的 $k$ 范围，精确估计 $\mathbb{Z}^k$ 中 $L^1$ 球的大小：

$1 \ll k \ll \log |G|$ : 使用几何分布作为球面分布的代理
$k \asymp \log |G|$ : 直接使用球面上的均匀分布
$k \gg \log |G|$ : 利用二项式系数的渐近性质

3. 最大公约数分析

关键技术是分析向量差 $V = W - W'$ 的最大公约数： $g = \gcd(V_1, \ldots, V_k, n)$ 通过控制 $\mathbb{E}(g^{d(G)} \mathbf{1}(V \neq 0))$ 来证明混合性。

4. 典型性条件

引入典型性集合 $\mathcal{W}$ 来处理"好"的样本： $\mathcal{W} = \{w \in \mathbb{Z}^k : L_0 + 1 \leq \|w\|_1/k \leq L, \max_i w_i \leq 3L \log k\}$

技术创新点

统一框架: 为三个不同的 $k$ 范围提供了统一的分析框架
混合方法: 创新性地使用随机游走混合理论证明几何性质
精确常数: 给出了明确的集中值，而非仅是渐近阶
条件放松: 通过密度-1子集的技巧放松了对群结构的限制

主要定理

定理A (典型距离)

设 $G$ 是阿贝尔群，则有以下收敛（依概率）：

情况1: $1 \ll k \ll \log |G|$ ， $k - d(G) \asymp k$ $D_{G_k^\pm}(\beta) / D^\pm \to_P 1$ 其中 $D^+ = |G|^{1/k}/(2e)$ ， $D^- = |G|^{1/k}/e$
情况2: $k \asymp \lambda \log |G|$ $D_{G_k^\pm}(\beta) / (\alpha_\lambda^\pm k) \to_P 1$
情况3: $k \gg \log |G|$ $D_{G_k^\pm}(\beta) / \left(\frac{\rho}{\rho-1} \log_k |G|\right) \to_P 1$