On new expanders of unbounded degree for practical applications in informatics

Abstract

A method of construction of new examples of families of expander graphs of unbounded degree is presented. The property of being an expander seems significant in many of these mathematical, computational, and physical contexts. Even more, expanders are surprisingly applicable in other computational aspects: in the theory of error correcting codes, computer networking theory, the theory of pseudorandomness, etc. We present the new families of (q + 1)-regular graphs with the second largest eigenvalue of at most 2√q for every prime power q (geometrical Ramanujan graphs). In particular, we construct a family of new (q + 1)-regular Ramanujan graphs of girth 6 of order 2(1+q+q²+q³). They are not isospectric to the geometry of the simple Lie group B₂(q).