21
$\begingroup$

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?


                PayleyGraph
Paley graphs (connecting pairs of elements that differ in a quadratic residue) are expanders.

$\endgroup$
  • 7
    $\begingroup$ 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. $\endgroup$ – Benjamin Steinberg May 30 '14 at 1:31
37
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 1967! Wow! ${}$ $\endgroup$ – Joseph O'Rourke May 30 '14 at 1:49
  • 4
    $\begingroup$ Interestingly, while Pinkser is generally credited with coining the term "expander graph", in that 1973 paper he calls them "expand ing graphs". $\endgroup$ – mhum May 30 '14 at 1:51
  • 1
    $\begingroup$ 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). $\endgroup$ – Lucia May 30 '14 at 1:52
  • 2
    $\begingroup$ @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". $\endgroup$ – Andy Putman May 30 '14 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.