4 ms·
It is helpful that the post links to the Wikipedia page: https://en.wikipedia.org/wiki/Bunkbed_conjecture https://en.wikipedia.org/wiki/Bunkbed_conjecture Read
by solidsnack9000 2y ago
It is helpful that the post links to the Wikipedia page: https://en.wikipedia.org/wiki/Bunkbed_conjecture https://en.wikipedia.org/wiki/Bunkbed_conjecture
Reading that and then rereading the post, it all made a whole more sense: why the conjecture is intuitively appealing and why the computational approach doesn't readily result in a proof.
- knodi123 2y agoI still don't get it. So you make this graph, with a random number on each edge. Then you duplicate that graph, stack them like a bunkbed, and connect every lower vertex to the one above it. Then you delete all edges with a number below some threshold. Wouldn't the upper and lower graphs still be identical? Since you had the same edge weights in both? So the route from any upper node X to any upper node Y should be 1 less than the route length between X and the point beneath Y. What did I miss?
- cochne 2y agoThere is no thresholding, you delete edges randomly based on the probability assigned.
- knodi123 2y agoThanks, that's an important distinction.
- TheRealPomax 2y agoYou missed the part where the conjecture is about subgraphs: after forming the "bunk bed", we start randomly deleting edges based on edge probability, so there may no longer be a direct path from x to y in what was originally the upper graph.
- torstenvl 2y agoThat seems irrelevant since then there would be no path in the lower graph either. This must be true because deletions are based on probability and the corresponding edges between upper graph and lower graph are required to have the same probability.
- TheRealPomax 2y agoEach edge is independent from each other edge: you don't roll a die and then go "4: remove every edge that's 4 or less", you make a separate roll for each edge.
- arjvik 2y agoSame probability, but still independently sampled.
- calfuris 2y agoHaving the same probability of deletion doesn't mean that they will necessarily share the same fate.
- torstenvl 2y agoAh. The Wikipedia description of the conjecture does not say that each edge is independently randomly deleted (or not) based on the probability assigned to that edge. I just assumed the probabilities were the weights in a weighted graph and had some other effect (e.g., likelihood of success traversing that edge, comparative likelihood of choosing that edge vs another when traversing the graph, etc.).
- yread 2y agoI don't know. To me it sounds like it's obvious the conjecture doesn't hold. if you have a path in the upper bunk that gets broken you are screwed but if that path is broken you have the option to switch to path in the lower bunk at ANY moment. So you have n+1/n higher chance of a break but n-1 ways how to avoid it
- supernewton 2y agoThe conjecture is true for all small graphs that they tried, so if it's "obviously" false to you then something went wrong with your intuition somewhere.
- zmgsabst 2y agoOr everyone else’s, since his intuition arrived at the right asymptotic answer.
- tech_ken 2y agoI'm pretty sure you're sampling the "bedposts" as well, the upper and lower subgraphs aren't just connected at every node; I understood the rough (and incorrect) intuition to be like: P[nodes in upper bunk connected] > P[nodes in lower bunk connected] * P[sufficient "bedpost" edges survive connecting upper and lower] Since P[nodes in upper bunk connected] = P[nodes in lower bunk connected] And by definition P[sufficient "bedpost" edges survive connecting upper and lower]<1
- winwang 2y agoIntuitively (subjectively) why this argument doesn't work: if you switch to the path in the lower bunk, you can switch to the upper bunk "at any moment", regardless of if there is a path which exists on the lower bunk. In this example, a1 is connected to both c1 and c2: a1 b1 -- c1 | | | a2 -- b2 -- c2 If, instead of deleting edges, we assigned a distance d = 1/p, then you'd expect (and probably easily prove) that the distance to the target vertex is at most the distance to its partner in the other bunk. The fact that this intuitive "problem translation" doesn't actually translate to probabilities is quite surprising (to me)!
- 2y ago
- auggierose 2y agoYeah, the introductory sentence in the post doesn't really do a good job explaining what the bunkbed conjecture is. If I was interested in it, I would have to look it up somewhere else.