As I already mentioned, A. Lubotzky pointed out, in his recent Colloquium Lectures, that expander graphs (which were usually said to go back to a paper of Pinsker in 1973) already appeared in a paper of Barzdin and Kolmogorov from 1967. This was naturally in Russian, but the paper is reproduced in English translation in the selected works of Kolmogorov.
The paper is very interesting. It contains, indeed, a definition of what are recognizably expanders; it contains, before Pinsker, and with a similar probabilistic argument, a proof that “most” graphs, in a certain sense, are expanders; and it contains, most interestingly for me, an application of expanders which is of great interest, and which I didn’t know before. (I’d be interested to know if other readers had already heard of it).
In a second post, I will try to explain what Barzdin and Kolmogorov did in some detail, as far as my understanding goes. For the moment, before a few general remarks, here is the problem that they solve. The question is roughly: “how much volume does one need to embed a graph in?” More precisely, they consider a finite oriented graph $latex \Gamma$; this may not be planar, but it is clear that $latex \Gamma$ can be represented (without edge-crossings) in $latex \mathbf{R}^3$. Of course, once this is done, scaling leads to a copy of the graph in an arbitrary small volume, but what happens if the vertices are fattened-up a bit, and the edges are constrained to not come too close? Then the question becomes interesting. The motivation mentioned in the paper, attributed to Kolmogorov, has to do with neuron networks in the brain, but I think it has obvious mathematical interest. And the main results of Barzdin and Kolmogorov give the following answer: (1) any “fat” network with $latex n$ vertices can be embedded in a sphere of radius $latex \sqrt{n}$ in space; (2) this can not be improved in general, and most strikingly, a sequence $latex \Gamma_n$ of expander graphs requires at least volume $latex n^{3/2}$ asymptotically as $latex n$ grows (up to a fixed multiplicative constant). To show that (2) is not an empty statement, Barzdin and Kolmogorov show, as already mentioned, that expanders exist, and even better, with a suitable model, that “most” graphs are expanders. This is the result that was (it turns out) re-discovered by Pinsker.
Amusingly, 1967 is also the year when D. Kazhdan published his paper introducing Property (T). As is well-known, and explained for instance in the recent book of Bekka, de la Harpe and Valette, the first explicit construction of expanders, due to Margulis, relied on Property (T); in hindsight, it is rephrased as saying that any infinite discrete group $latex G$ with Property (T), for instance $latex \mathrm{SL}_3(\mathbf{Z})$, is such that the Cayley graphs of all finite quotients of $latex G$, constructed with respect to an arbitrary finite generating $latex S$, forms an expander family of graphs. (Note that it is a basic property — indeed, one of the motivating ones — that a discrete group with Property (T) is finitely generated).
Now here comes an idle discussion of priority and the like, which platonists might want to avoid. The paper of Barzdin and Kolmogorov contains a footnote saying that the details and sharpest results are due to Barzdin; the selected works of Kolmogorov contains a comment by Barzdin that says that the basic ideas are entirely due to Kolmogorov. So it’s not completely clear (to a random reader like me) which of the two authors precisely did come up first with the idea of expanders. One is tempted to suspect that it was Kolmogorov; if that is the case, he must have been past 60 when the idea came up — the paper appeared when he was 64 –, and that would be a very striking counterexample to the common perception that mathematics is a young person’s game… (Rigorous chronologists might like to point out that Selberg’s “3/16” theorem predates the Kolmogorov-Barzdin paper as well as Kazhdan’s Property (T) paper, so that an explicit construction of expanders was, in some sense, known before they were defined; unless, that is, it is discovered that Gauss, Euler or Kepler, in a particularly abstruse private letter or notebook, had anticipated the discovery…)
[Query: the proof of existence of expanders in the paper of Barzdin and Kolmogorov goes by computations with binomial coefficients and the like; now, I don’t want to be more of a probabilist than Kolmogorov, but does anyone know if someone has written somewhere a “clean” proof, using instead the basic properties of binomial random variables and standard analytic/probabilistic inequalities? I would be surprised if this wasn’t possible, and I’ll certainly look for something like that before teaching — probably next semester — about expanders.]
Final remark: for a fairly wide-ranging discussion of the mathematical contributions of Kolmogorov, there is a nice book, available either in French or in English translation (I was one of the translators, which was very interesting since I had no idea previously that Kolmogorov had been influential in mathematical logic or in algebraic topology…) The Barzdin-Kolmogorov paper is mentioned in the bibliography of one chapter, but is not discussed in detail.
