Uniform diameter bounds for some families of Cayley graphs

Authors:
  • AGAlex Gamburd
    Alex Gamburd
  • MSMehrdad Shahshahani
    Mehrdad Shahshahani

Abstract
We prove that Cayley graphs of PSL2(ℤ/p2ℤ) have uniform polylog diameter with respect to the natural projection of elements in PSL2(ℤ) generating a dense subgroup. The proof also provides a fast algorithm for finding a short path between two vertices.