A large family of explicit k-regular Cayley graphs X is presented. These graphs satisfy a number of extremal combinatorial properties. (i) For eigenvalues λ of X either λ=±k or |λ|≦2 √k-1. This property is optimal and leads to the best known explicit expander graphs. (ii) The girth of X is asymptotically ≧4/3 logk-1 |X| which gives larger girth than was previously known by explicit or non-explicit constructions.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics