کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4584417 | 1630493 | 2015 | 20 صفحه PDF | دانلود رایگان |
Let g, h be a random pair of generators of G=Sym(n)G=Sym(n) or G=Alt(n)G=Alt(n). We show that, with probability tending to 1 as n→∞n→∞, (a) the diameter of G with respect to S={g,h,g−1,h−1}S={g,h,g−1,h−1} is at most O(n2(logn)c)O(n2(logn)c), and (b) the mixing time of G with respect to S is at most O(n3(logn)c)O(n3(logn)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 ℓ-tuples, where ℓ is an arbitrary constant (Friedman et al., 1998).
Journal: Journal of Algebra - Volume 421, 1 January 2015, Pages 349–368