Timeline for Instances where an existence result precedes the constructive version
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 15, 2012 at 4:48 | comment | added | JSE | Yes -- by "expander graph" I mean "infinite family of graphs with a spectral gap." Bad notation, I know. | |
| Aug 15, 2012 at 4:06 | comment | added | Igor Rivin | It is pretty hard to construct a graph which is not expanding with some constant, and given a graph of a reasonable size, it is not so difficult to compute the expansion constant (the stupid algorithm is exponential, but for graphs up to around 30 vertices this should not be a problem). It is constructing an infinite family of such that is hard. | |
| Aug 15, 2012 at 3:04 | comment | added | Michael Lugo | More generally, the probabilistic method (en.wikipedia.org/wiki/Probabilistic_method) as pioneered by Erdos comes to mind. | |
| Aug 15, 2012 at 1:27 | history | answered | JSE | CC BY-SA 3.0 |