Swammerdami
Squadron Leader
In the sequel I assume that the reader is familiar with at least the rudimentary notions of Graph theory.
"The Bunkbed Conjecture is False" is a meme now popular on Yahoo News. I examined it briefly and came to this conclusion:
(1) Graph theory is a fascinating field of mathematics, simplistic in that finite sets are used along with mostly simple connectivity relations.
(2) The specific question for which the "Bunkbed Conjecture" is relevant is this:
Given a graph containing a path from a to b, if edges are excised from the graph what is the chance that some path from a to b continues to exist? (This can be quantized variously, but for our needs here almost any approach will work!)
(3) A bunk-bed graph is a graph formed from the graph G by appending a graph G* identical to G and erecting "pillars" (edges) between each g and g* where the latter point is the point in G* which is the image of g in G.
(4) The "Bunkbed Conjecture" is that the connection probabilities in G are all at least as good as the probabilities for the bunkbed graph G+G*+Pillars.
(5) A graph was displayed which contradicts this conjecture.
And now "my contribution."
(6) Consider the graph G+G*+Pillars1+Pillars2+Pillars3.
With the pillar triplicated it is unlikely to disappear in its entirety (all three edges); and thus, if allowed, would lead swiftly to defiance of the Conjecture.
Three pillars happened to be (barely) enough. If it hadn't worked we could have used ten pillars, or a hundred, or a googol.
(7) The rest of the proof merely fleshes out the details to convert the system just described, to a STANDARD (vertices connected by at most one edge) graph. Instead of multiple-edge pillars, the published proof uses "length-3 edges" -- and describes a procedure to implement this approximately, as a network of length-2 edges.
Anyone want to check my work?
"The Bunkbed Conjecture is False" is a meme now popular on Yahoo News. I examined it briefly and came to this conclusion:
(1) Graph theory is a fascinating field of mathematics, simplistic in that finite sets are used along with mostly simple connectivity relations.
(2) The specific question for which the "Bunkbed Conjecture" is relevant is this:
Given a graph containing a path from a to b, if edges are excised from the graph what is the chance that some path from a to b continues to exist? (This can be quantized variously, but for our needs here almost any approach will work!)
(3) A bunk-bed graph is a graph formed from the graph G by appending a graph G* identical to G and erecting "pillars" (edges) between each g and g* where the latter point is the point in G* which is the image of g in G.
(4) The "Bunkbed Conjecture" is that the connection probabilities in G are all at least as good as the probabilities for the bunkbed graph G+G*+Pillars.
(5) A graph was displayed which contradicts this conjecture.
And now "my contribution."
(6) Consider the graph G+G*+Pillars1+Pillars2+Pillars3.
With the pillar triplicated it is unlikely to disappear in its entirety (all three edges); and thus, if allowed, would lead swiftly to defiance of the Conjecture.
Three pillars happened to be (barely) enough. If it hadn't worked we could have used ten pillars, or a hundred, or a googol.
(7) The rest of the proof merely fleshes out the details to convert the system just described, to a STANDARD (vertices connected by at most one edge) graph. Instead of multiple-edge pillars, the published proof uses "length-3 edges" -- and describes a procedure to implement this approximately, as a network of length-2 edges.
Anyone want to check my work?
The bunkbed conjecture is false | Hacker News
news.ycombinator.com