Who first dubbed them “expander graphs”?

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.

• The first explicit expanders were constructed by Margulis in the seventies if I am not mistaken and random constructions go back further, so I wouldn't say it burst on the scene around the millenium. – Benjamin Steinberg May 30 '14 at 1:31

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.

• 1967! Wow! ${}$ – Joseph O'Rourke May 30 '14 at 1:49
• Interestingly, while Pinkser is generally credited with coining the term "expander graph", in that 1973 paper he calls them "expand ing graphs". – mhum May 30 '14 at 1:51
• Lubotzky's survey in the Bulletin of the AMS (ams.org/journals/bull/2012-49-01/S0273-0979-2011-01359-3/…) also credits Pinsker with defining and naming them (see page 115; he also credits Guth for drawing attention to Kolmogorov and Barzdin). – Lucia May 30 '14 at 1:52
• @mhum : I think that both terms are used frequently. Eg Lubotzky's book on the subject is called "Discrete groups, expanding graphs, and invariant measures". – Andy Putman May 30 '14 at 1:58