%0 Journal Article %1 lubotzky88 %A Lubotzky, A. %A Phillips, R. %A Sarnak, P. %D 1988 %I Springer-Verlag %J Combinatorica %K expander graph.theory ramanujan %N 3 %P 261--277 %R 10.1007/BF02126799 %T Ramanujan Graphs %V 8 %X 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.

@article{lubotzky88, 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 \sqrt{k}−1$. This property is optimal and leads to the best known explicit expander graphs. (ii) The girth of $X$ is asymptotically $≧ 4/3 \log_{k−1} |X|$ which gives larger girth than was previously known by explicit or non-explicit constructions.}, added-at = {2014-04-20T17:33:49.000+0200}, author = {Lubotzky, A. and Phillips, R. and Sarnak, P.}, biburl = {https://www.bibsonomy.org/bibtex/2ad570947f4e1aa6b28f92edcd3ca519d/ytyoun}, doi = {10.1007/BF02126799}, interhash = {a24586cfce5d28dcb68ac32cbb5c00fd}, intrahash = {ad570947f4e1aa6b28f92edcd3ca519d}, issn = {0209-9683}, journal = {Combinatorica}, keywords = {expander graph.theory ramanujan}, language = {English}, number = 3, pages = {261--277}, publisher = {Springer-Verlag}, timestamp = {2017-11-20T03:00:53.000+0100}, title = {Ramanujan Graphs}, volume = 8, year = 1988 }