%0 Conference Paper %1 kahale91 %A Kahale, N. %B Proceedings 32nd Annual Symposium of Foundations of Computer Science %D 1991 %I IEEE %K expander graph.theory ramanujan %R 10.1109/sfcs.1991.185397 %T Better Expansion for Ramanujan Graphs %X The expansion properties of regular graphs are investigated. The best previously known expansion of subsets of linear size of explicit k-regular graphs is k/4. This bound is achieved by nonbipartite Ramanujan graphs of degree k=p+1, which have the property that all but the largest eigenvalue have absolute value at most 2 square root p. The expansion coefficient for linear subsets for nonbipartite Ramanujan graphs is improved to 3(k-2)/8. Other results are established, including improved results about random walks on expanders.

@inproceedings{kahale91, abstract = {The expansion properties of regular graphs are investigated. The best previously known expansion of subsets of linear size of explicit k-regular graphs is k/4. This bound is achieved by nonbipartite Ramanujan graphs of degree k=p+1, which have the property that all but the largest eigenvalue have absolute value at most 2 square root p. The expansion coefficient for linear subsets for nonbipartite Ramanujan graphs is improved to 3(k-2)/8. Other results are established, including improved results about random walks on expanders.}, added-at = {2016-10-29T06:16:59.000+0200}, author = {Kahale, N.}, biburl = {https://www.bibsonomy.org/bibtex/255c79a216606bc96f45cde7f6971e2a1/ytyoun}, booktitle = {Proceedings 32nd Annual Symposium of Foundations of Computer Science}, doi = {10.1109/sfcs.1991.185397}, interhash = {e1a8bf65c8d987dda5b89a303c3a1c4a}, intrahash = {55c79a216606bc96f45cde7f6971e2a1}, keywords = {expander graph.theory ramanujan}, publisher = {IEEE}, timestamp = {2016-10-29T12:03:52.000+0200}, title = {Better Expansion for {Ramanujan} Graphs}, year = 1991 }