Timeline for How to prove a random d-regular graph is an expander with prob >= 0.5?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 15 at 0:20 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
added 12 characters in body
|
| Jan 11, 2018 at 0:33 | comment | added | user6976 | @Igor: Gromov often talks negatively about Kolmogorov's results. Probably it is justified in some cases (e.g., entropy), but in this particular case Kolmogorov wins. | |
| Aug 26, 2011 at 21:42 | comment | added | user6976 | @Igor: And where the word "bipartite" here? Why don't you look at the paper by Kolmogorov and Bardzin before claiming that it contains/does not contain something. | |
| Aug 25, 2011 at 19:54 | comment | added | Igor Rivin | I did not look at the paper. Guth/Gromov say: Strictly speaking, Kolmogorov and Barzdin studied directed graphs where the number of incoming edges at each vertex was always d (say d = 2), but the number of outgoing edges could vary. If we consider these graphs as undirected graphs, the degree is not actually bounded. Random directed graphs are easy to define. Each vertex has d incoming edges, and each of these edges is assigned a starting vertex uniformly at random. (It looks plausible that Kolmogorov and Barzdin work with directed graphs because it is easier to define a random directed graph | |
| Aug 25, 2011 at 16:46 | comment | added | user6976 | I looked at the paper by Kolmogorov and Bardzin. Where do they assume that the graphs are bipartite? | |
| Aug 25, 2011 at 14:38 | comment | added | Igor Rivin | @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. | |
| Aug 25, 2011 at 14:13 | comment | added | user6976 | 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. | |
| Aug 25, 2011 at 14:05 | comment | added | Igor Rivin | 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). | |
| Aug 25, 2011 at 13:37 | comment | added | user6976 | Selected works of Kolmogorov may be in your library. Also see gen.lib.rus.ec: gen.lib.rus.ec/book/… | |
| Aug 25, 2011 at 10:18 | comment | added | expanders | 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? | |
| Aug 25, 2011 at 10:04 | vote | accept | expanders | ||
| Aug 25, 2011 at 10:13 | |||||
| Aug 25, 2011 at 8:42 | history | answered | user6976 | CC BY-SA 3.0 |