Expansion properties of Cayley graphs of the alternating groups

[摘要] Let C be a conjugacy class in the alternating group A(n), and let supp(C) be the number of nonfixed digits under the action of a permutation in C. For every 1 > delta > 0 and n greater than or equal to 5 there exists a constant c = c(delta) > 0 such that if supp(C) greater than or equal to delta n then the undirected Cayley graph X(A(n), C) is a c expander. A family of such Cayley graphs with supp(C) = o(root n) is not a family of c-expenders. For every delta > 0, if supp(C) greater than or equal to root 3n then sets of vertices of order at most (1/2 - delta)(n - (n/supp(C)))! in X(A(n), C) expand. The proof of the last result combines spectral and representation theory techniques with direct combinatorial arguments. (C) 1997 Academic Press.

[发布日期] 1997-08-01