GEOMETRY OF RANDOM CAYLEY GRAPHS OF ABELIAN GROUPS

• 成果类型: Article
• 署名作者: Hermon, Jonathan; Olesker-Taylor, Sam
• 署名单位: University of British Columbia; University of Warwick
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1899
• 发表日期: 2023
• 页码: 3520-3562
• 关键词: random random-walks; diameter; expansion

摘要

Consider the random Cayley graph of a finite Abelian group G with re-spect to k generators chosen uniformly at random, with 1 << log k << log |G|. Draw a vertex U <^> Unif(G).We show that the graph distance dist(id, U) from the identity to U con-centrates at a particular value M, which is the minimal radius of a ball in Zk 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 greater than or similar to log |G|, we show that the diameter of the graph is also asymptotically M. In the spirit of a conjecture of Aldous and Diaconis (Technical Report 231 (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) asymptotic to k and |G| lies in a density-1 subset of N or when k - 2d (G) asymptotic to k. This extends, for Abelian groups, a celebrated result of Alon and Roichman (Random Structures Algorithms 5 (1994) 271-284).The aforementioned results all hold with high probability over the random Cayley graph.