%0 Journal Article %1 alon86 %A Alon, Noga %D 1986 %J Combinatorica %K eigenvalues expander graph.theory ramsey %N 3 %P 207--219 %R 10.1007/BF02579382 %T Eigenvalues, Geometric Expanders, Sorting in Rounds, and Ramsey Theory %V 6 %X Expanding graphs are relevant to theoretical computer science in several ways. Here we show that the points versus hyperplanes incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number of edges. The expansion properties of the graphs are proved using the eigenvalues of their adjacency matrices.

@article{alon86, abstract = {Expanding graphs are relevant to theoretical computer science in several ways. Here we show that the points versus hyperplanes incidence graphs of finite geometries form highly (nonlinear) expanding graphs with essentially the smallest possible number of edges. The expansion properties of the graphs are proved using the eigenvalues of their adjacency matrices.}, added-at = {2016-11-01T04:26:48.000+0100}, author = {Alon, Noga}, biburl = {https://www.bibsonomy.org/bibtex/23b2f5a1bb607538d5bf479e3daef1eb4/ytyoun}, doi = {10.1007/BF02579382}, interhash = {3b5bbed13883c9a5d8f00ab179cd187c}, intrahash = {3b2f5a1bb607538d5bf479e3daef1eb4}, issn = {1439-6912}, journal = {Combinatorica}, keywords = {eigenvalues expander graph.theory ramsey}, number = 3, pages = {207--219}, timestamp = {2016-11-01T04:26:48.000+0100}, title = {Eigenvalues, Geometric Expanders, Sorting in Rounds, and {Ramsey} Theory}, volume = 6, year = 1986 }