Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

2012/01/16 by V. Arvind, Partha Mukhopadhyay, Arvind, V. +5
Computer Science · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.1201.3181

15 pages

arxiv created 2012/01/16 · arxiv updated 2012/01/17

Abstract

Let G =<S> be a solvable permutation group of the symmetric group S_n given as input by the generating set S. We give a deterministic polynomial-time algorithm that computes an expanding generating set of size O(n²) for G. More precisely, the algorithm computes a subset T⊂ G of size O(n²)(1/λ)^O(1) such that the undirected Cayley graph Cay(G,T) is a λ-spectral expander (the O notation suppresses log ^O(1)n factors). As a byproduct of our proof, we get a new explicit construction of ε-bias spaces of size O(n\poly(log d))((1)/(ε))^O(1) for the groups \Z_dⁿ. The earlier known size bound was O((d+n/ε²))^11/2 given by \citeAMN98.

Related

• Symmetric Groups and Expander Graphs
• Symmetric Groups and Expanders
• Near-Optimal Cayley Expanders for Abelian Groups
• Uniform expansion bounds for Cayley graphs of SL 2 (𝔽 p )
• Random Cayley graphs and expanders