On the diameter of permutation groups
On the diameter of permutation groups
复制标题
DOI：
10.4007/annals.2014.179.2.4
复制
发表时间：
2011-09
影响因子：
4.9
通讯作者：
L. Babai;Á. Seress
中科院分区：
文献类型：
--
作者：
L. Babai;Á. Seress
给定有限群 G 和生成元集合 A，凯莱图 G(G,A) 的直径 diam(G(G,A)) 是最小的 l，使得 G 的每个元素都可以表示为 A→A -1 中长度最多为 l 的单词。我们关心的是边界直径（G）：=最大A直径（G（G，A））。长期以来，人们推测 n 次对称群的直径以 n 为多项式界限，但之前已知的最佳上限是以 nlogn - - - - - v 为指数形式。我们给出一个拟多项式上限，即 diam(G)=exp(O((logn) 4 loglogn))=exp((loglog|G|) O(1) ) 对于 G=Sym(n) 或 G=Alt(n) ，其中隐含常数是绝对的。这解决了巴拜关于简单群直径猜想的一个关键的开放案例。根据 Babai 和 Seress (1992) 的结果，我们的界限还意味着所有 n 次传递置换群的直径上的拟多项式上限。
Given a finite group G and a set A of generators, the diameter diam(G(G,A)) of the Cayley graph G(G,A) is the smallest l such that every element of G can be expressed as a word of length at most l in A?A -1 . We are concerned with bounding diam(G):=max A diam(G(G,A)) . It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n , but the best previously known upper bound was exponential in nlogn - - - - - v . We give a quasipolynomial upper bound, namely, diam(G)=exp(O((logn) 4 loglogn))=exp((loglog|G|) O(1) ) for G=Sym(n) or G=Alt(n) , where the implied constants are absolute. This addresses a key open case of Babai�s conjecture on diameters of simple groups. By a result of Babai and Seress (1992), our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree n .