Examples of Ramanujan and expander graphs for practical applications

摘要

Expander graphs are highly connected sparse finite graphs. The property of being an expander seems significant in many of these mathematical, computational and physical contexts. Even more, expanders are surprizingly applicably applicable in other computational aspects: in the theory of error corecting codes and the theory of pseudorandomness, which are used in probabilistic algorithms. In this article we present a method to obtain a new examples of families of expanders graphs and some examples of Ramanujan graphs which are the best expanders. We describe properties of obtained graphs in comparison to previously known results. Numerical computations of eigenvalues presented in this paper have been computed with MATLAB.