Expander graphs
("sparse graphs that have strong connectivity properties")
burst onto the mathematical scene around the millennium, but I have not
been successful in tracing the origin of
(a) the concept, and
(b) the name expander.
Does anyone know? And can provide a citation?
Paley graphs
(connecting pairs of elements that differ in a quadratic residue) are expanders.
Best Answer
The concept (but not the name) was introduced by Barzdin and Kolmogorov in
A. N. Kolmogorov and Y. M. Barzdin, “On the realization of networks in three-dimensional space” in Selected Works of Kolmogorov, vol. 3, Kluwer, Dordrecht, 1993, 194–202.
which was published in 1967. They proved that they exist via a probabilistic argument. They were then rediscovered and named expanders by Pinsker in his paper
M. S. Pinsker, "On the complexity of a concentrator'', Proceedings of the Seventh International Teletraffic Congress (Stockholm, 1973), pp. 318/1–318/4, Paper No. 318.
available here (see the appendix). He also proves they exist via a probabilistic argument. The first explicit examples were found by Margulis in his paper
G. Margulis, Explicit constructions of concentrators, Problemy Peredachi Informatsii, 9(4) (1973), pp. 71-80; Problems Inform. Transmission, 10 (1975), pp. 325-332.
and by Gabber-Galil in their paper
O. Gabber and Z. Galil, Explicit constructions of linear size superconcentrators, Proc. 20th Annual Symposium on the Foundations of Computer Science, 1979, pp. 364-370.
By the way, I learned the above history from the following lovely paper:
M. Gromov and L. Guth, Generalizations of the Kolmogorov-Barzdin embedding estimates. Duke Math. J. 161 (2012), no. 13, 2549–2603.