Abstract
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 łog_k−1 |X|$ which gives larger girth than was previously known by explicit or non-explicit constructions.
Users
Please
log in to take part in the discussion (add own reviews or comments).