The Alon-Roichman Theorem
V. Arvind · 2013
Expander graphs are of much importance in theoretical computer science, and the construction of expander graphs involves different areas of mathematics. It has at-tracted mathematicians and theoretical computer scientists alike and continues to be a flourishing area of research [14]. In this essay we discuss the Alon-Roichman theorem which states that for any finite group G, if S is a randomly picked multiset of O(log |G|) elements then the symmetric Cayley graph Cay(G,S) is a spectral expander with high probability. We explain a proof of this theorem based on Erdős-Rényi sequences, which are interesting in their own right, and also outline a |G|O(1) time derandomized construction of the set S. We also discuss faster, (log |G|)O(1) time, derandomizations of the Alon-Roichman theorem for finite groups given by small generating sets as input and raise some open questions. 1