Kolmogorov and expanders, I

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 \Gamma; this may not be planar, but it is clear that \Gamma can be represented (without edge-crossings) in \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 n vertices can be embedded in a sphere of radius \sqrt{n} in space; (2) this can not be improved in general, and most strikingly, a sequence \Gamma_n of expander graphs requires at least volume n^{3/2} asymptotically as 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 G with Property (T), for instance \mathrm{SL}_3(\mathbf{Z}), is such that the Cayley graphs of all finite quotients of G, constructed with respect to an arbitrary finite generating 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.

Published by


I am a professor of mathematics at ETH Zürich since 2008.

4 thoughts on “Kolmogorov and expanders, I”

  1. Given that the paper was coauthored, there isn’t a priority issue at all; priority is due to both of them.
    As for the age of 64 – surely we can come with examples of a new idea introduced by somebody older? (Even in the romantic 19th century, weren’t some players – i.e. Weierstrass, Sylvester – active until quite old?)

  2. Maybe “priority” was not the right word; what I mean is, was it Kolmogorov or Barzdin who came up first with the idea of expanders? Of course, the answer might still be “both”, if the spark arose, say, during a conversation in front of a blackboard. I don’t think the question is in bad taste (not that you suggested it), in view of the duelling footnote and comment in the collected works…

    As for finding another example with someone even older, of course that wouldn’t be too surprising. But such an important idea? That sounds harder…

  3. I have no problem with the suggestion that the expander concept had already appeared in some implicit form in Barzdin and Kolmogorov’s work, even possibly earlier before Pinsker’s work, but this suggestion must not be stretched too far to overshadow what Pinsker accomplished in his seminal 1973 paper. His work is far deeper than formally introducing and defining an expander. He provided a remarkable proof of existence of a concentrator with at most 29n edges, first of any such linear size concentrators. Most people who cite his work don’t even take the time to go through his paper to appreciate the complexity and elegance of his proof. As important as it is, the proof of existence of an expander was not even included in the main body of the paper, but only placed in the appendix…

Comments are closed.