Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

摘要

Given a finite group G by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on G with O(logG) generators, which has a rapid mixing property and a constant spectral expansion.We prove a similar result in the undirected case, and give a new deterministic polynomial-time construction of an expanding Cayley graph with O(logG) generators, for any group G given by its multiplication table. This gives a completely different and elementary proof of a result of Wigderson and Xiao.For any finite group G given by a multiplication table, we give a deterministic polynomial-time construction of a cube generating sequence that gives a distribution on G which is arbitrarily close to the uniform distribution. This derandomizes the construction of Erdos-Renyi sequences