Timeline for A regular n,2d graph is a good expander.
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 16, 2011 at 18:19 | comment | added | Ori Gurel-Gurevich | Maybe it's time to learn about martingales... | |
| Nov 16, 2011 at 14:37 | comment | added | Henry Cohn | It's worth learning about martingales (in addition to looking for another proof), actually, since they are an extremely useful tool. The beginning of Chapter 7 in Alon and Spencer's book on the probabilistic method gives a nice introduction, and in a couple of pages it covers everything I think you need for the Broder and Shamir proof. | |
| Nov 16, 2011 at 11:28 | answer | added | kassabov | timeline score: 5 | |
| Nov 16, 2011 at 11:24 | comment | added | Emil Jeřábek | There are several related but different definitions of an expander (the most popular ones are in terms of the spectral gap, vertex expansion, or edge expansion). Which one are you using? | |
| Nov 16, 2011 at 7:20 | history | asked | anonymous coward | CC BY-SA 3.0 |