Symmetric Groups and Expanders

Martin Kassabov

Abstract
We construct an explicit generating sets F n   and F ~ n   of the alternating and the symmetric groups, which make the Cayley graphs C ( A l t ( n ) , F n )   and C ( S y m ( n ) , F ~ n )   a family of bounded degree expanders for all sufficiently large n   .
These expanders have many applications in the theory of random walks on groups and other areas of mathematics.
A finite graph Γ   is called an ε   -expander for some ε ∈ ( 0 , 1 )   , if for any subset A ⊆ Γ   of size at most | Γ | / 2   we have | ∂ ( A ) | > ε | A |   (where ∂ ( A )   is the set of vertices of Γ \ A   of edge distance 1 to A   ). The largest such ε   is called the expanding constant of Γ   . Constructing families of ε   -expanders with bounded valency is an important practical problem in computer science, because such graphs have many nice properties — for example they have a logarithmic diameter. For an excellent introduction to the subject we refer the reader to the book [14] by A. Lubotzky. Using counting arguments it can be shown that almost any 5   regular graph is 1 / 5   -expander. However constructing an explicit examples of families expander graphs is a difficult problem.
The first explicit construction of a family of expanders was done by G. Margulis in [19] , using Kazhdan property T of S L 3 ( Z )   . Currently there are several different construction of expanders. With the exception of a few recent ones based on the zig-zag products of graphs (see [2, 23, 24] ), all constructions are based groups theory and use some variant of property T (property τ   , Selberg property etc.).
Kazhdan Property T is not very interesting for a given finite group G   (all finite groups have property T ), but the related Kazhdan constant with respect to some generating F   set is. Given an infinite collection of finite groups G i   , it is a challenge to prove the existence of uniform Kazhdan constants with respect to properly chosen generating sets. This problem is related to construction a family of expanders using the Cayley graphs of the groups G i   .
The original definition of property T uses the Fell topology of the unitary dual, see [11] . Here we will use an equivalent definition (only for discrete groups) which also addresses the notion of the Kazhdan constants.
Definition 1 Let G   be a discrete group generated by a finite set S   . Then G   has the Kazhdan property T if there exists ε > 0   such that for every unitary representation ρ : G → U ( ℋ )   on a Hilbert space ℋ   without G   invariant vectors and every vector v ≠ 0   there exists some s ∈ S   such that | | ρ ( s ) v − v | | > ε | | v | |   .
The largest ε   with this property is called the Kazhdan constant for G   with respect to S   and is denoted by K ( G ; S )   .
For a G   the property T is independent on the choice of the generating set S   , however the Kazhdan constant depends also on the generating set.
The following connection between property T and expander graphs is well known:
Theorem 2 ([14] , Theorem 4.3.2) Let G   be a discrete group having property T, and let S   be a finite generating set of G   . Then there exists an ε = ε ( S ) > 0   such that the Cayley graphs C ( G i , S i )   (and all their quotients) of the finite images of G i   of G   (with respect to the images S i   of S   ) form a family of ε   -expanders.
The largest ε 0 ( S )   with this property is related to the Kazhdan constant K ( G , S )   , in particular we have ε 0 ( S ) ≥ K ( G ; S ) 2 / 4   .
Using this approach and property T of S L n ( Z )   one can make the Cayley graphs of S L n ( F p )   for fixed n ≥ 3   a family of expanders. 1   Until recently the only way to prove Kazhdan property T was via representation theory of high rank Lie groups.
These methods are not quantitative and does not lead to estimates for the Kazhdan constants and the corresponding expanding constants of the resulting Cayley graphs.
A breakthrough in this direction was done in [25] by Y. Shalom, who used the bounded generation of the S L n ( Z )   and M. Burger's estimate (see [6] ) of the relative Kazhdan constant of S L 2 ( Z ) ⋉ Z 2   to obtain an estimates for the Kazhdan constant of S L n ( Z )   . His methods were refined in [7] to give the exact asymptotic of the Kazhdan constant of S L n ( Z )   with respect to the set of all elementary matrices. This yields an asymptotically exact estimate for the expansion constant of the form O ( 1 / n )   of the Cayley graphs of S L n ( F p )   with respect the set of all elementary matrices.
It is interesting to note that if the rank of the matrices increases then the resulting Cayley graphs do not form an expander family, even though that the degree of these graphs goes to infinity.
Using relative property T of the pair S L 2 ( R ) ⋉ R 2 , R 2   for finitely generated noncommutative rings R   , the Cayley graphs of S L n ( F q )   for any prime power q   and infinitely many n   -es can be made expanders by choosing a suitable generating set, see [8] . An important building block in this construction is that the group S L n ( F q )   can be written as a product of 20   abelian subgroups and this number is independent on n   and q   .
However, the symmetric/alternating groups can not be written as a product of fixed number of abelian subgroups, because the size of the S y m ( n )   or A l t ( n )   is approximately n n   and every abelian subgroup has at most 2 n   elements, see [1] .
This suggests that A l t ( n )   are further from the abelian groups than all others finite simple groups, and therefore they should have more expanding properties.
Unfortunately, this also significantly complicates the construction of expanders based on the alternating groups.
Using the classification of the finite simple groups A. Lubotzky suggested [18] that the results from [8] could be generalized to:
Conjecture 3 There exists constants L > 0   and ε > 0   such that for any non-abelian finite simple group G   , there exits a generating set F   such that | F | ≤ L   and the Cayley graphs C ( G ; F )   from a family of ε   -expanders. Equivalently, we have that K ( G ; F ) > ε   (with a different ε   ).
This conjecture is supported by several results — it is known (see [5] and [10] ) that for any non-abelian finite simple group there exist a 4   element generating set such that the diameter of the corresponding Cayley graph is logarithmic in the size of the group. Theorem  6 together with the results form [8] can be view as a major step toward proving Conjecture  3 , see [9] .
If one allows unbounded generating sets there are only a few partial results known. A classical result of N. Alon and Y. Roichman (and its improvements in [12] and [13] ) says that any group is an ε   -expander 2   with respect to a random large generating set:
Theorem 4 ([3] ) For any ε > 0   there exists c ( ε ) > 0   such that the Cayley graph any finite group G   is an ε   -expander with respect to a random generating set of size c ( ε ) log | G |   .
The bound c ( ε ) log | G |   is the optimal one in the class of all finite groups, because large the abelian groups are not expanders with respect to small generating sets. It is believed that if the group G   is far from being abelian the bound c log | G |   can be improved. Note that Theorem  4 implies a version of Conjecture  3 , where the size of the generating set is allowed to increase.
Theorem  4 also gives that the Cayley graphs of the alternating groups A l t ( n )   are expanders with respect to a random generating set of size n log n   . This was the best known result in this direction and even there were no known explicit sets of size less than n n   which make the Cayley graphs expanders. In view of the main results in this paper it is very interesting to understand the expanding properties of the Cayley graphs of A l t ( n )   and other finite simple groups with respect to a random generating set of a small (even bounded) size.
One of the main results in this paper gives answers affirmatively an old question, which have been asked several times in the literature, see [4, 14, 15] :
Theorem 5 There exist constants L > 0   , ε > 0   and an infinite sequence n s   with the property: There exists a constructible generating set F n s   of size at most L   of the alternating group A l t ( n s )   such that the Cayley graphs C ( A l t ( n s ) ; F n s )   form a family of ε   -expanders.
From the proof of Theorem  5 , it can be seen that the sequence n i   does not grow too fast, which leads to the following generalization:
Theorem 6 There exist constants L > 0   and ε > 0   , with the property: for any n   there exists a constructible generating sets F n   and F ~ n   of the alternating group A l t ( n )   and the symmetric group S y m ( n )   respectively such that the Cayley graphs C ( A l t ( n ) ; F n )   and C ( S y m ( n ) ; F ~ n )   form a family of ε   -expanders and all generating sets F n   and F ~ n   have at most L   elements.
Theorem  6 has applications interesting applications: It provides one of the few constructions of an expander family of Cayley graphs C ( G i , S i )   such that the groups G i   are not quotients of some infinite group having a variant of Kazhdan property T. It also provides a supporting evidence for the conjecture that the automorphism groups of the free groups have property τ   , see [16] .
Theorem  6 implies that the expanding constant of A l t ( n )   with respect to the set F n 10 10   is large enough. 3   The size of the set F n 10 10   is independent on n   , and if n   is sufficiently big then | F n 10 10 | < n 1 / 30 / 10 − 30   . The last inequality allows us to use the expander C ( A l t ( n ) ; F n 10 10 )   as a `seed' graph for E. Rozemann, A. Shalev and A. Widgerson recursive construction of expanders, see [24] . This construction produces a family of expander graphs based on Cayley graphs of the automorphism group of large n   -regular rooted tree of depth k   . A slight modification of this construction gives an other recursive expander family based on A l t ( n k )   for fixed large n   and different k   -es.
Theorem  6 gives that the Cayley graphs C ( A l t ( n ) ; F n )   and C ( S y m ( n ) ; F ~ n )   have many expanding properties which imply that the random walks on A l t ( n )   and S y m ( n )   , generated by F n   and F ~ n   respectively, have mixing time approximately log | A l t ( n ) | = n log n   steps. This leads to a natural and fast algorithm for generating pseudo-random permutations.
Proof of Theorem  5 : We will think that the alternating group A l t ( N )   acts on a set of N   points which are arranged into d   dimensional cube of size K   . Let ρ   be a representation of A l t ( N )   with almost invariant vector v   with respect to some generating set F   (to be chosen later). We will use two different arguments to show that there is an invariant vector.
First, we will break the representation ρ   into two components — one corresponding to partitions λ   with λ 1 < N − h   and second one containing all other partitions.
The decomposition of the regular representation of A l t ( N )   into two components depending on the first part of the partition λ   comes from [22] . In this paper, Y. Roichman uses similar argument to show that the Cayley graphs of the symmetric/alternating group with respect to a conjugacy class with a large number of non-fixed points have certain expanding properties.
We will show that the projection of the vector v   in the first representation is small provided that h ≫ K   . Also the projection of v   in the second one is close to an invariant vector if h ≪ N 1 / 4   . 4   In order to satisfy these restriction we need that N ≫ K 4   , i.e., d > 4   . In order to simplify the argument a little, we also require that d   is even, which justifies our choice of d = 6   and N = K 6   . Also we need that K ≪ h ≪ K 3 / 2   , therefore using h = K 5 / 4   we will define ℋ 1   to be the sub-representation of ℋ   corresponding to all partitions with λ 1 < N − K 5 / 4   . As an additional assumption, we require that K + 1   is a power of some prime number and we will use K = 2 3 s − 1   for a significantly large s   . 5   We will think that the alternating group A l t ( N )   acts on a set of N   points which are arranged into 6   dimensional cube of size K   and we will identify these points with ordered 6   -tuples of nonzero elements from the field F 2 3 s   .
Let ρ : A l t ( N ) → U ( ℋ )   be a fixed unitary representation of the alternating group and let v ∈ ℋ   be an ε   -almost invariant unit vector for some generating set F   . We will fix the set F   and the number ε   later. Without loss of generality, we may assume that ℋ   is generated by the orbit of the vector v   .
Let H s   denote the group S L 3 s ( F 2 )   . The group H s   has a natural action on the set V \ { 0 }   of K   nonzero elements of a vector space V   of dimension 3 s   over F 2   . The elements of H s   act by even permutations on V \ { 0 }   , because H s   is a simple group and does not have Z / 2 Z   as a factor. If we identify V   with F 2 3 s   then the existence of a generator for the multiplicative group of F 2 3 s   implies that some element of H s   acts as a K   -cycle on V \ { 0 }   . 6   Let Γ   be the direct product of K 5   copies of the group H s   . The group Γ   can be embedded into A l t ( N )   in 6   different ways which we denote by π i   , i = 1 , . . . , 6   .
The image of each copy of H s   under π i   acts as S L 3 s ( F 2 )   on a set of K = 2 3 s − 1   points where all coordinates but the i   -th one are fixed. It is clear that Γ   contains an abelian subgroup Γ ¯   isomorphic to ( Z / K Z ) × K 5   .
Using Theorem 5 from [8] , we can find a small generating set S   of the group H s   such that the Kazhdan constant K ( H s ; S ) > 1 / 400   . This allows us to construct a generating set S ~   with 40   elements of Γ   with similar properties, i.e., the Kazhdan constant K ( Γ ; S ~ ) > 1 / 500 .   Now we can define the generating set F N   of A l t ( N )   such that the Kazhdan constant K ( A l t ( N ) ; F N )   can be estimated — the set F N   will be the union of the images of S ~   under the embeddings π i   :
F N = ⋃ i π i ( S ~ ) .   The group generated by the set F N   contains the 6   images of Γ   and therefore is the whole alternating group A l t ( N )   . From now on, we will assume that the vector v ∈ ℋ   is ε   -almost invariant with respect to the set F N   . Using the Kazhdan constant of K ( Γ ; S ~ )   , it can be seen that if v   is ε   -almost invariant vector with respect to the set F N   in some representation ρ   of A l t ( N )   , then v   is close to Γ i   invariant vector, i.e., | | ρ ( π i ( g ) ) v − v | | ≤ 10 3 ε | | v | | ,   for all g ∈ Γ   and any i = 1 , . . . , 6   . If the diameters of Cayley graphs of C ( A l t ( N ) , ∪ Γ i )   were bounded independently on N   , this would gives us that the representation ρ   has an invariant vector, provided that ε   is small enough.
Unfortunately this is not the case, because A l t ( N )   can not be written as a product of less than log | N |   abelian subgroups and each Γ i   is a product of less than 20   abelian subgroups.
Let Γ i ¯   denote the image of Γ ¯   under the embedding π i   and let C   be the union of Γ i ¯   . Thus, we may assume that the vector v   is almost invariant with respect to the set C   .
As mentioned before we will break the representation ρ   into two components.
The space ℋ   decomposes as a sum of irreducible representations ℋ = ⊕ λ c λ M λ ,   where the sum is over all partitions λ   of N   , M λ   denotes the irreducible representations corresponding to the partition λ   and c λ   is the multiplicity of M λ   in ℋ   which is either 0   or 1   , since ℋ   is generated by 1 element. Let ℋ 1   is the sum of all irreducible sub-representations of ℋ   which correspond to the partitions λ = [ λ 1 , λ 2 , . . . ]   of N   with λ 1 < N − K 5 / 4 ,   and ℋ 2   is the orthogonal complement of ℋ 1   in ℋ   .
This allows us to decompose the almost invariant vector v   as v = v 1 + v 2   , where v i ∈ ℋ i   . We will use two different arguments to show that the vector v 1   is small and that v 2   is close to an invariant vector in ℋ 2   .
Using the definition of the set C   , it can be seen that C 440   acts almost transitively on the set of all ordered tuples of K 5 / 10   points. Here C 440   denotes the set of all product of less than 440   elements from the set C   , and by almost transitivity we if we are given 2   ordered tuples then with large probability κ   (approaching 1   as s → ∞   ), there exists an element in C 440   which send one to the other. Therefore the set C 440   contains almost all elements in some conjugacy class B   of permutations in A l t ( N )   with at least K 5 / 10   non-fixed points.
The vector v   is almost preserved by any element of C   , which implies that v   is moved a little by most of the elements inside the conjugacy class B   , i.e., | | ρ ( g ) v − v | | ≤ 440 × 1000 ε   for any g ∈ B ∩ C 440   . This gives
| | 1 | B | ∑ g ∈ B ρ 1 ( g ) v 1 − v 1 | | ≤ 1 | B | ∑ g ∈ B | | ρ ( g ) v − v | | ≤
≤ 2 ( 1 − κ ) | | v 1 | | + κ | B | ∑ g ∈ B ∩ C 440 | | ρ ( g ) v − v | | <
< | | v 1 | | 6 + 4.5 × 10 5 ε ,
provided that κ   is sufficiently close to 1   . The decomposition of ℋ 1   as ℋ 1 = ⊕ λ c λ M λ ,   gives a decomposition of the vector v 1 = ∑ v λ   . The set B   is a conjugacy class therefore 1 | B | ∑ g ∈ B ρ ( g ) v λ = χ ¯ λ ( B ) v λ   for any vector v λ   in an irreducible representation M λ   . Here χ ¯ λ ( B )   is the normalized character of the representation M λ   , defined as χ ¯ λ ( B ) : = χ λ ( B ) / dim M λ   . Thus we have | | 1 | B | ∑ g ∈ B ρ 1 ( g ) v 1 | | ≤ | | v 1 | | max λ | χ ¯ λ ( B ) | ,   where the maximums are taken over all partitions which appear in the representation ρ 1   , i.e., all partitions λ   with λ 1 < N − K 5 / 4   . There are various estimates of value of the normalized characters of the symmetric/alternating groups. Applying the bounds from [21] Theorem 1 yields
max λ | χ ¯ λ ( B ) | ≤ max λ { max { λ 1 / N , q } c supp | B | } ≤
≤ ( 1 − K 5 4 K 6 ) c K 5 10 ≤ exp ( − c K 1 4 10 ) < 1 3 ,
where c   and q   are universal constants. The last inequality is valid only if K   is large enough. The two inequalities above imply that
| | v 1 | | < 9 × 10 5 ε . (1)
The above argument does not work for the representation ℋ 2   , because the first part of the partition λ   can be close to N   . This means that the sum λ 2 + λ 3 + ⋅ ⋅ ⋅ < K 5 / 4   is small. Thus ℋ 2   can be embedded in the representation M   arising from the action of A l t ( N )   on set of all ordered tuples of size K 5 / 4   . Let E   denote the set of ordered tuples of size K 5 / 4   which is a basis of M   .
We have K K 5 ≫ N K 5 / 4   , i.e., number of elements in the set C   is much larger than size of the set E   . Using this inequality and the definition of the set S   , it can be shown that the random walk on set E   , where the moves are given by the permutations from some subset C ~ ⊂ C 6   , mixes in a few steps independent of N   . Therefore if we define the operator Δ   on M   defined by Δ : = 1 | C ~ | ∑ g ∈ C ~ ρ 2 ( g )   then Δ 8   has a single eigenvalue 1   with eigenvectors the invariant vectors in M   , and all other eigenvalues are less than 1 / 2   by absolute value. Thus we have:
| | Δ 8 v 2 − v 2 | | ≥ 1 2 | | v 2 − v | | | | ,   where v | |   be the projection of v 2   onto the space of all invariant vectors in M   .
On the other hand | | Δ 8 v 2 − v 2 | | ≤ 8 | | Δ v 2 − v 2 | | ≤ 8 | C ~ | ∑ g ∈ C ~ | | ρ 2 ( g ) v 2 − v 2 | | ≤ 48 × 1000 ε ,   which gives that
| | v 2 − v | | | | < 10 5 ε . (2)
The inequalities ( 1 ) and ( 2 ) imply that | | v − v | | | | ≤ | | v 1 | | + | | v 2 − v | | | | < 10 6 ε .   In particular, if ε   is small enough then the vector v | |   is not zero, which show that there exists invariant vectors in the representation ℋ   . Thus, we have shown that K ( A l t ( N ) ; F N ) ≥ 10 − 6 ,   which concludes the proof of Theorem  5 . □   Proof of Theorem  6 : By Theorem  5 the alternating groups A l t ( n s )   are expanders with respect to some generating set F n s   for n s = ( 2 3 s − 1 ) 6   . The sequence { n s } s = 50 ∞   grows exponentially, therefore for any sufficiently large n   there exists s   such that 1 < n / n s < 10 6   . The group A l t ( n )   can be written as a product of fixed number (less then 10 9   ) of copies of A l t ( n s )   embedded in A l t ( n )   . Using the images of the sets F n s   one can construct a generating set F n   such that K ( A l t ( n ) ; F n ) ≥ 10 − 15   and | F n | ≤ 10 10   , which completes the proof of Theorem  6 , the construction of the generating sets F ~ n   of the symmetric groups is similar. □   The generating set S   of S L 3 s ( F 2 )   can be defined so that the elements of S   are involutions. This allows us to construct an expanding generating set F n   consisting only of involutions.
The bounds for the size of the generating set F n   and the Kazhdan constant in the proof Theorem  6 can be significantly improved — it is possible to construct a 10   element generating set F ¯ n   consisting of involutions such that K ( A l t ( n ) ; F ¯ n ) ≥ 10 − 8   , provided that n   is large enough. N. Nikolov [20] suggested that it is possible to further improve the bound for Kazhdan constant by a factor of two by using the groups S L 3 ( F q )   instead of S L 3 s ( F 2 )   , but this will increase the size of the generating set.
Acknowledgements: I wish to thank A. Lubotzky and N. Nikolov for their encouragement and the useful discussions during the work on this project. I am grateful to Y. Shalom and E. Zelmanov for introducing me to the subject.
References

  1. M. Abért, Symmetric groups as products of abelian subgroups, Bull. London Math. Soc. 34 (2002), no. 4, 451–456.
  2. N. Alon, A. Lubotzky, A. Wigderson, Semi-direct product in groups and zig-zag product in graphs: connections and applications, Proc. of the 42nd FOCS, pp. 630–637, 2001.
  3. N. Alon, Y. Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271–284.
  4. L. Babai, G. Hetyei, W. M. Kantor, A. Lubotzky, A. Seress, On the diameter of finite groups. 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), 857–865, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990.
  5. L. Babai, W. M.Kantor, A. Lubotsky, Small-diameter Cayley graphs for finite simple groups. European J. Combin. 10 (1989), no. 6, 507–522.
  6. M. Burger, Kazhdan constants for S L 3 ( Z )   , J. Reine Angew. Math., 413 (1991), 36–67.
  7. M. Kassabov, Kazhdan constants for S L d ( Z )   , arXiv:math.GR/0311487, to appear in Internat. J. Algebra and Comput.
  8. M. Kassabov, Universal lattices and unbounded rank expanders, arXiv:math.GR/0502237.
  9. M. Kassabov, N. Nikolov, Finite simple groups and expanders, in preparation.
  10. M. Kassabov, T. R. Riley, Diameter of Cayley graphs of S L n ( Z / k Z )   , arXiv:math.GR/0502221.
  11. D. A. Kazhdan, On the connection of the dual space of a group with the structure of its closed subgroups, Funkcional. Anal. i Priloz. 1 (1967), 71–74.
  12. Z. Landau, A. Russell, Random Cayley graphs are expanders: a simple proof of the Alon-Roichman Theorem, Electronic Journal of Combinatorics, 11(1):R62, 2004
  13. P. Loh, L. Schulman, Imporved expansion of random Cayley graphs, Discrete Mathematics and Theoretical Computer Scinece, 6, 2004, 523–528.
  14. A. Lubotzky, Discrete groups, expanding graphs and invariant measures, Progr. Math. 125, Birkhäuser, Boston, 1994.
  15. A. Lubotzky, Cayley graphs: eigenvalues, expanders and random walks, Surveys in combinatorics, 1995 (Stirling), 155–189, London Math. Soc. Lecture Note Ser., 218, Cambridge Univ. Press, Cambridge, 1995.
  16. A. Lubotzky, I. Pak, The product replacement algorithm and Kazhdan's property (T), J. Amer. Math. Soc. 14 (2001), no. 2, 347–363 (electronic).
  17. A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277.
  18. A. Lubotzky, privite communication.
  19. G. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71–80.
  20. N. Nikolov, privite communication.
  21. Y. Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451–485.
  22. Y. Roichman, Expansion properties of Cayley graphs of the alternating groups, J. Combin. Theory Ser. A 79 (1997), no. 2, 281–297.
  23. O. Reingold, S. Vadhan, A. Wigderson, Entropy waves, The zig-zag graph product, and new constant-degree expanders and extractors, Proc. of the 41st FOCS, pages 3–13, 2000.
  24. E. Rozenman, A. Shalev, A. Wigderson, A new family of Cayley expanders (?), 36th Annual ACM Symposium, STOC 2004, pp 445–454, 2004.
  25. Y. Shalom, Bounded generation and Kazhdan's property (T), Publ. Math. IHES, 90 (1999), 145–168.

Martin Kassabov, Cornell University, Ithaca, NY 14853-4201, USA. e-mail: kassabov@math.cornell.edu

  2000 Mathematics Subject Classification: Primary 20B30; Secondary 05C25, 05E15, 20C30, 20F69, 60C05, 68R05, 68R10.

  Key words and phrases: expanders, symmetric groups, alternating groups, random permutations, property T, Kazhdan constants.

1   The Cayley graphs of S L 2 ( F p )   can also be made expanders although the group S L 2 ( Z )   does not have property T or even τ   , see [17] .

2   There are two different definitions of ε   -expanders, which are equivalent for graphs of bounded degree but not in general. A `weak' one corresponding to Definition  1 , and a `strong' one using the spectral gap of the Laplacian. The random Cayley graphs obtained from Theorem  4 are expanders in both definitions.

3   More precisely we have that the spectral gap of the Laplacian of the Cayley graph is very close to 1   .

4   We believe that the argument also works even in the case h ≪ N 1 / 2   , however we are unable to prove it. If such generalization is true, it will allow us to use d = 4   , which will improve the estimates for the Kazhdan constants by a factor of 10   .

5   It seems that s > 50   suffices, however the estimate depends on the constants involved in the character estimates from [21] , which are not in the literature.

6   We can use some other family of groups instead of { H s } s   — the only requirements for { H s } s   are that they acting transitively on a set of K ( s )   points (where K ( s ) → ∞   as s → ∞   ) and that { H s × K ( s ) 5 } s   can be made a bounded degree expanders. For example we can use the groups S L 3 ( F p )   acting on F p 3 \ { 0 }   or on the projective plane P 2 F p   for different primes p   -es.