25
$\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$
1
  • 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$ May 30 '14 at 1:31
40
$\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$
5
  • $\begingroup$ 1967! Wow! ${}$ $\endgroup$ 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
  • 3
    $\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$ May 30 '14 at 1:58
  • $\begingroup$ Pinkser's 1973 paper refers to Margulis's paper before it was published with the title "Explicit Constructions of Expanders" $\endgroup$
    – quantropy
    May 8 at 18:57
1
$\begingroup$

The term expanding graph was coined by Pinsker in the proof of the main result (Lemma 1) of his paper, "On the complexity of a concentrator," which appeared in the proceeding of 7th International Teletraffic Congress, published in 1973. Margulis worked at the institute, Problemy Peredachi Informatsii Institute during the same time period, M. Pinsker and L. A. Bassalyo worked (Bassalygo still works there) and published his paper, "Explicit construction of concentrators in Problemy Peredachi Informatsii Journal the same year. However, Margulis never mentions the term expander anywhere in this paper. The term expander seems to appear the first time in Gabber and Galil's 1979 and 1981 papers, "Explicit constructions of linear-sized superconcentrators," in an odd way by making a reference to Margulis' paper. Here is the phrase Gabber and Galil used on the second page of their paper: "Margulis [2J made a major step forward. He found a way to construct explicit linear expanders defined below." This appears in both the conference and journal edition of their paper even though Margulish never mentions the term expander in his paper. It remains to be determined if the term expander appeared explicitly in any article published between 1973 (Margulis) and 1979 (Gabber and Galil). Margulis was recently interviewed as a co-winner of 2020 Abel prize, where he credits Pinsker for coining the term expanding graph (Around 43 minutes into the video towards the end), but then also mentions that the notion of an expanding graph was transformed over time into other forms. (Video Link: https://www.youtube.com/watch?v=FInTu9-MHHU&t=32s&ab_channel=TheAbelPrize).

$\endgroup$

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.