Greg Egan on Nostr: Suppose you take a graph G (a collection of nodes joined by edges), make an exact ...
Suppose you take a graph G (a collection of nodes joined by edges), make an exact copy of it, G', and join G and G' with edges along some of their corresponding vertices.
If you randomly delete edges from G and G' with the same probability (but don't delete any of the edges you added between G and G'), can it ever be *less likely* that you can still get from a vertex x in graph G to another vertex y also in G than it is to get from x to the copy of y in G'?
The conjecture that no choice of G can make it less likely is known as the Bunkbed Conjecture. And three mathematicians have just found a counterexample!
H/T Timothy Gowers, Javier Campos
https://igorpak.wordpress.com/2024/10/01/the-bunkbed-
conjecture-is-false/
https://arxiv.org/abs/2410.02545
If you randomly delete edges from G and G' with the same probability (but don't delete any of the edges you added between G and G'), can it ever be *less likely* that you can still get from a vertex x in graph G to another vertex y also in G than it is to get from x to the copy of y in G'?
The conjecture that no choice of G can make it less likely is known as the Bunkbed Conjecture. And three mathematicians have just found a counterexample!
H/T Timothy Gowers, Javier Campos
https://igorpak.wordpress.com/2024/10/01/the-bunkbed-
conjecture-is-false/
https://arxiv.org/abs/2410.02545