Timeline for Applying the amplification trick + probabilistic method on connected graphs
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 8, 2011 at 8:24 | comment | added | Suresh Venkat | What seems tricky here is that if the property holds for any connected graph, and in particular a tree, then even if p = 1/n, there's a high probability of the property failing. So you're dealing in a very narrow range. | |
| Feb 8, 2011 at 3:56 | comment | added | Igor Rivin | That Tao post is very nice... | |
| Feb 7, 2011 at 16:19 | comment | added | Louigi Addario-Berry | I've never heard of such a trick but one thing you could try is first fixing a spanning tree (deterministically or, perhaps more usefully depending on the situation, according to the uniform or another distribution), then doing the random edge deletion only on edges that don't belong to the spanning tree. Without knowing more about the invariants you want to consider, I don't have any better idea than that. | |
| Feb 7, 2011 at 14:11 | history | asked | Jernej | CC BY-SA 2.5 |