zbMATH — the first resource for mathematics

Essentially every unimodular matrix defines an expander. (English) Zbl 1018.05065
Summary: We generalize the construction of O. Gabber and Z. Galil [J. Comput. Syst. Sci. 22, 407-420 (1981; Zbl 0487.05045)] to essentially every unimodular matrix in \(\text{SL}_2(\mathbf Z)\). It is shown that every parabolic or hyperbolic fractional linear transformation explicitly defines an expander of bounded degree and constant expansion. Thus all but a vanishingly small fraction of unimodular matrices define expanders.
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX Cite
Full Text: DOI