A new family of Cayley expanders (?)

ABSTRACT

We assume that for some fixed large enough integer d, the symmetric group Sd can be generated as an expander using d^1/30 generators. Under this assumption, we explicitly construct an infinite family of groups Gn, and explicit sets of generators Yn ⊂ Gn, such that all generating sets have bounded size (at most d^1/7), and the associated Cayley graphs are all expanders. The groups Gn above are very simple, and completely different from previous known examples of expanding groups. Indeed, Gn is (essentially) all symmetries of the d-regular tree of depth n. The proof is completely elementary, using only simple combinatorics and linear algebra. The recursive structure of the groups Gn (iterated wreath products of the alternating group Ad) allows for an inductive proof of expansion, using the group theoretic analogue [4] of the zig-zag graph product of [38]. The explicit construction of the generating sets Yn uses an efficient algorithm for solving certain equations over these groups, which relies on the work of [33] on the commutator width of perfect groups.We stress that our assumption above on weak expansion in the symmetric group is an open problem. We conjecture that it holds for all d. We discuss known results related to its likelihood in the paper.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 2: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 3: N. Alon , Z. Galil , V. D. Milman, Better expanders and superconcentrators, Journal of Algorithms, v.8 n.5, p.337-347, Sept. 1987 [doi>10.1016/0196-6774(87)90014-9]
• 4: A. Lubotzky, Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.630, October 14-17, 2001
• 5: N. Alon and V. D. Milman. λ1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory. Series B, 38(1):73--88, 1985.
• 6: N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures Algorithms, 5(2):271--284, 1994.
• 7: L. Babai, G. Hetyei, W. M. Kantor, A. Lubotzky, and A. Seress. On the diameter of finite groups. In 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), pages 857--865. IEEE Comput. Soc. Press, Los Alamitos, CA, 1990.
• 8: Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780631]
• 9: Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510003]
• 10: P. Diaconis and M. Shahshahani. On the eigenvalues of random matrices. J. Appl. Probab., 31A:49--62, 1994. Studies in applied probability.
• 11: J. D. Dixon. The probability of generating the symmetric group. Math. Z., 110:199--205, 1969.
• 12: M. Eichler. Quaternäre quadratische Formen und die Riemannsche Vermutung für die Kongruenzzetafunktion. Arch. Math., 5:355--366, 1954.
• 13: O. Gabber and Z. Galil. Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci., 22(3):407--420, June 1981.
• 14: O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman. Security preserving amplification of hardness. In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 318--326, St. Louis, Missouri, 22--24 Oct. 1990. IEEE.
• 15: M. Gromov. Spaces and questions. Geometric and Functional Analysis, pages 118--161, 2000. Part I of Special Volume on GAFA 2000 (Tel Aviv, 1999).
• 16: Russell Impagliazzo , Noam Nisan , Avi Wigderson, Pseudorandomness for network algorithms, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.356-364, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195190]
• 17: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 18: Shuji Jimbo , Akira Maruoka, Expanders obtained from affine transformations, Combinatorica, v.7 n.4, p.343-355, Dec, 1987 [doi>10.1007/BF02579322]
• 19: N. J. Kalton and J. W. Roberts. Uniformly exhaustive submeasures and nearly additive set functions. Transactions of the American Mathematical Society, 278(2):803--816, 1983.
• 20: D. Kazhdan. On the connection of the dual space of a group with the structure of its closed subgroups (russian). Funkcional. Anal. i Prilozh., 1:71--74, 1967.
• 21: M. Klawe. Limitations on explicit constructions of expanding graphs. SIAM J. Comput., 13(1):156--166, 1984.
• 22: M. W. Liebeck and A. Shalev. The probability of generating a finite simple group. Geom. Dedicata, 56(1):103--113, 1995.
• 23: L. Lovasz and P. Winkler. Mixing times. In Microsurveys in discrete probability (Princeton, NJ, 1997), volume 41 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 85--133. Amer. Math. Soc., Providence, RI, 1998.
• 24: A. Lubotzky. Discrete groups, expanding graphs and invariant measures. Birkhauser Verlag, Basel, 1994.
• 25: A. Lubotzky and I. Pak. The product replacement algorithm and Kazhdan's property (T). Journal of the American Mathematical Society, 14(2):347--363 (electronic), 2001.
• 26: A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
• 27: A. Lubotzky and B. Weiss. Groups and expanders. In Expanding graphs (Princeton, NJ, 1992), volume 10 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 95--109. Amer. Math. Soc., Providence, RI, 1993.
• 28: G. A. Margulis. Explicit constructions of expanders. Problemy Peredav ci Informacii, 9(4):71--80, 1973.
• 29: G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51--60, 1988.
• 30: Roy Meshulam , Avi Wigderson, Expanders from symmetric codes, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510004]
• 31: Moshe Morgenstern, Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q, Journal of Combinatorial Theory Series B, v.62 n.1, p.44-62, Sept. 1994 [doi>10.1006/jctb.1994.1054]
• 32: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 33: N. Nikolov. On the commutator width of perferct groups. to appear.
• 34: O. Ore. Some remarks on commutators. Proc. Amer. Math. Soc., 2:307--314, 1951.
• 35: M. S. Pinsker. On the complexity of a concentrator. In 7th Annual Teletraffic Conference, pages 318/1--318/4, Stockholm, 1973.
• 36: Nicholas Pippenger, Sorting and selecting in rounds, SIAM Journal on Computing, v.16 n.6, p.1032-1038, December 1, 1987 [doi>10.1137/0216066]
• 37: N. Pippenger and A. C. Yao. Rearrangeable networks with limited depth. SIAM Journal on Algebraic and Discrete Methods, 3:411--417, 1982.
• 38: O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. of Math. (2), 155(1):157--187, 2002.
• 39: A. Selberg. On the estimation of Fourier coefficients of modular forms. In Proc. Sympos. Pure Math., Vol. VIII, pages 1--15. Amer. Math. Soc., Providence, R. I., 1965.
• 40: Michael Siper, Expanders, randomness, or time versus space, Journal of Computer and System Sciences, v.36 n.3, p.379-383, June 1988 [doi>10.1016/0022-0000(88)90035-9]
• 41: M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6, part 1):1710--1722, 1996.
• 42: D. A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6, part 1):1723--1731, 1996.
• 43: M. R. Tanner. Explicit concentrators from generalized n-gons. SIAM Journal on Algebraic Discrete Methods, 5(3):287--293, 1984.
• 44: Alasdair Urquhart, Hard examples for resolution, Journal of the ACM (JACM), v.34 n.1, p.209-219, Jan. 1987 [doi>10.1145/7531.8928]
• 45: L. G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical foundations of computer science (Proc. Sixth Sympos., Tatranska Lomnica, 1977), pages 162--176. Lecture Notes in Comput. Sci., Vol. 53. Springer, Berlin, 1977.
• 46: A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: explicit construction and applications. Combinatorica, 19(1):125--138, 1999.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Cayley graphs, expanders, zig-zag product