# 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.
##### MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: