期刊
JOURNAL OF ALGEBRA
卷 421, 期 -, 页码 349-368出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jalgebra.2014.08.033
关键词
Symmetric group; Permutation groups; Diameter; Spectral gap
类别
资金
- ANR [ANR-12-BS01-0011]
- Adams Prize
- Leverhulme Prize
Let g, h be a random pair of generators of G = Sym(n) or G = Alt(n). We show that, with probability tending to 1 as n -> infinity, (a) the diameter of G with respect to S = {g, h, g(-1), h(-1)} is at most O(n(2)(log n)(c)), and (b) the mixing time of G with respect to S is at most O(n(3)(log n)(c)). (Both c and the implied constants are absolute.) These bounds are far lower than the strongest worst-case bounds known (in Helfgott-Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap. Our results rest on a combination of the algorithm in (Babai-Beals-Seress, 2004) and the fact that the action of a pair of random permutations is almost certain to act as an expander on l-tuples, where l is an arbitrary constant (Friedman et al., 1998). (C) 2014 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据