8
$\begingroup$

How to prove a random $d$-regular graph is an expander with prob $\ge 0.5$?

Context: Many resources, like

http://math.mit.edu/~fox/MAT307-lecture22.pdf

state the theorem in the general case, but then prove it only for the bipartite case. The full case is supposedly proved in Pinsker's 1973 paper. However, I can't dig up a copy.

Anyone know of a proof for the general case (i.e. d-regular, undirected, not-necessarily-bipartitite graph)?

Thanks!

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
6
$\begingroup$

Pinsker's original paper is now available online in the archive of the International Teletraffic Congress: https://itc-conference.org/itc-library/itc07.html

Pinsker, Mark S. On the Complexity of a Concentrator. 7th International Teletraffic Congress, pp. 318/1-318/4, 1973

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Fixed the broken link $\endgroup$
    – Hermann Gruber
    Commented Jan 14 at 18:08
5
$\begingroup$

Perhaps you should look at the paper by Barzdin and Kolmogorov instead, which was before Pinsker and proved the same result, see http://blogs.ethz.ch/kowalski/2011/02/13/kolmogorov-and-expanders-i/. This paper is available in English in the collection of Kolmogorov's selected papers.

Improve this answer
$\endgroup$
9
  • $\begingroup$ This links to a survey by Lubotzky, which mentions Barzdin + Kolmogorov's "On the realization of nets in 3-dimensional space" (which I can't find a pdf of); and a book by Lubotzky. Is there a direct link somewhere I'm missing? $\endgroup$
    – expanders
    Commented Aug 25, 2011 at 10:18
  • $\begingroup$ Selected works of Kolmogorov may be in your library. Also see gen.lib.rus.ec: gen.lib.rus.ec/book/… $\endgroup$
    – user6976
    Commented Aug 25, 2011 at 13:37
  • $\begingroup$ The arxiv preprint by Gromov and Guth (front.math.ucdavis.edu/1103.3423) discussed the Kolmogorov-Barzdin paper at great length. It is pretty clear that they (KB) DID NOT prove the Pinsker results, but something closer to the usual trivial "a random bipartite graph is random" result. I think it is not very nice to give credit where it is not due (and take away credit from Pinsker, who proved the foundational result in the field). $\endgroup$
    – Igor Rivin
    Commented Aug 25, 2011 at 14:05
  • $\begingroup$ I did not read any of the papers cited. The statement that KB proved the same result is in the text I put a link to, which quotes Lubotzky. I do not know whether any of these quotes are correct. $\endgroup$
    – user6976
    Commented Aug 25, 2011 at 14:13
  • $\begingroup$ @Mark: I don't blame you -- as I say, Guth and Gromov discuss the K/B paper at great length (since Barzdin/Kolmogorov is in the title of their paper), and while they give a lot of credit to KB, it is clear that they did NOT prove the Pinsker theorem, although they proved either exactly or approximately the bipartite result. There is a tendency in the community to give too much credit to the great men (be they Gauss or Kolmogorov). It is curious also that every expander reference easily findable on line only proves the bipartite version. Particularly since the Pinsker paper is 4 pages long. $\endgroup$
    – Igor Rivin
    Commented Aug 25, 2011 at 14:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .