[HN Gopher] The bunkbed conjecture is false
___________________________________________________________________
The bunkbed conjecture is false
Author : surprisetalk
Score : 114 points
Date : 2024-10-02 15:01 UTC (7 hours ago)
(HTM) web link (igorpak.wordpress.com)
(TXT) w3m dump (igorpak.wordpress.com)
| solidsnack9000 wrote:
| It is helpful that the post links to the Wikipedia page:
| 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 wrote:
| I 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 wrote:
| There is no thresholding, you delete edges randomly based on
| the probability assigned.
| knodi123 wrote:
| Thanks, that's an important distinction.
| TheRealPomax wrote:
| You 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 wrote:
| That 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.
| arjvik wrote:
| Same probability, but still independently sampled.
| calfuris wrote:
| Having the same probability of deletion doesn't mean that
| they will necessarily share the same fate.
| yread wrote:
| I 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 wrote:
| The 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.
| tech_ken wrote:
| I'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_
| keepamovin wrote:
| Wow, funny how our intuitions fail on objects with _7523 vertices
| and 15654 edges_
| fbn79 wrote:
| and funny 7523 is a prime number.
| f1shy wrote:
| But 16564 not!
| keepamovin wrote:
| Nice! 15654 = 2*3*2609
|
| and (7253/15654)**(phi*pi)*100 ~ 2
|
| haha :)
| y-curious wrote:
| It was always obvious for me. But they did call me gifted in
| the third grade.
| keepamovin wrote:
| Hahaha it was obvious that it was _false_ for you???
| dataflow wrote:
| > This is completely obvious, of course!
|
| Could someone explain why the conjecture seemed obviously true? I
| have no background with it, but just reading the description
| here, I was caught off guard by the sentence. What made it seem
| obvious?
| keepamovin wrote:
| Why is it "obviously true" (that lower probabilities of
| connection between than on levels)?
|
| Because if it wasn't true then that would imply that V on
| different levels (as reached presumably by a canonical DFS tree
| // spanning tree) were closer (in terms of paths) than V on the
| same level, which would mean that those V should have "more
| likely" been on the same level (as however measured).
|
| TL;DR - 'obviously true' because there's a level between them
| so (on average) of course!
| jprete wrote:
| The upper and lower bunk graphs are symmetrical in their
| probabilities, so it would intuitively seem like connecting to
| the same bunk's point would be easier/more likely than
| connecting to the other bunk's point. The first would require
| zero (or an even number of) crossings, the latter would require
| one (or an odd number of) crossings. Every crossing would
| _seem_ to only decrease the odds of the path existing, or at
| best leave it the same.
|
| To me it smells like a trap, though. This feels like exactly
| the kind of problem where some algorithmically chosen infinite
| graph would break the conjecture, possibly through some kind of
| NP-hardness-proof-style transformation of the problem into
| another form, and who knows, maybe the Axiom of Choice gets
| involved too (but probably not based on the headline!).
| sweezyjeezy wrote:
| The (disproven) conjecture is for finite graphs.
| joelignaatius wrote:
| I may be missing something. If theres edges u1 to v1 and
| symmetrical graph u2 to v2 then any post has to be between u1
| to u2 for any u. Which means traversing a post would
| essentially be adding an edge to the graph (no matter the
| probability). It seems intuitively obvious (which is stated
| here as incorrect) that going through a post would be more
| expensive.
| elseweather wrote:
| Yes, it seems intuitively obvious, which is why
| mathematicians spent a long time trying to prove that the
| conjecture was true. It turns out The conjecture is false
| in a non-obvious way. The result described in the blog post
| is a specific counterexample: the conjecture fails, just
| barely, for a specific graph with several thousand nodes
| and edges. It's not the kind of counterexample you would
| intuit in your head or even on a whiteboard.
| joelignaatius wrote:
| It would seem the next logical step would be to come up
| with a series of examples where the conjecture fails and
| then extrapolate from there what new rules you come up
| with. And then possibly attempt to draw an isomorphism
| from another field. At some point mathematics will turn
| into an LLM problem (I know hype cycle). I'm interested
| in knowing if there are branches of mathematics which are
| near inaccessible to non computational methods of proof.
| And then there would be levels of mathematics where the
| proof itself would be true, but it would be much like me
| asking you for the intuition except it would be man
| versus the computer. If you do this level of mathematics
| and you put it in a box you have some real world result
| the operations of which are non comprehensible but
| demonstrably have an analogy to something understandable.
| Schrodinger's AI.
| ted537 wrote:
| I also know nothing but here's something missing from the blog
| post:
|
| "A random subgraph of the bunkbed graph is then formed by
| independently deleting each edge based on the assigned
| probability."
|
| So the (apparently incorrect) intuition is that an
| (upper<->lower) connection starts with an extra edge in the
| connection, so an (upper<->lower) connection has a greater risk
| of disconnect via random edge removal. Therefore, a same-level
| connection is more likely to remain after the random edge
| removal.
| cashew22 wrote:
| Here is my reasoning: start with two vertices u and v in the
| first floor and the vertex corresponding to v in the second
| floor (call it w). u and v are connected if, after deleting
| some edges randomly, there is still a path from u to v,
| similarly for u and w. But for any fixed path from u to w, you
| can get a shorter path from u to v by just going across between
| the floors one less time. Because a shorter path is more likely
| to survive than a longer one (by a factor of p), it makes sense
| that overall, the probability of some path from u to v
| surviving is larger than some path from u to w surviving. But,
| that reasoning breaks down, in part because when you drop the
| last crossing edge, there are many ways of adding it back in,
| so each path from u to v might correspond to many paths from u
| to w.
| stonemetal12 wrote:
| Intuitively the longer a path is the more likely it is to be
| broken when you start randomly removing edges, and before you
| remove edges the shortest path from U1 to V2 is the shortest
| path from U1 to V1 plus a post. Therefore it seems like the
| path from U1 to V2 is more likely to be broken than the path
| from U1 to V1.
| geminger wrote:
| So it's been debunked.
| thehappypm wrote:
| Bunkbed Bet Bested
| andrewflnr wrote:
| While I wouldn't accept a probabilistic "proof" of a theorem like
| this, it does seem clear to me that those results are important
| for directing the focus of research, especially in cases where
| they go against intuition. Given that most of the math community
| was barking up the wrong tree, even if these guys only had the
| probabilistic result, surely that would eventually help someone
| find the right proof? That's at least worth publishing as a
| letter or something, right?
|
| Ed: reflecting on my first sentence, I guess I tend to think of
| proofs as being at least as important a product of math as the
| raw truth of a statement. A fact is a fact, but a proof
| represents (some level of) understanding, and that's the good
| stuff. Experiments are potentially good science, but usually not
| math.
| bubblyworld wrote:
| Can you elaborate? It's possible to prove probabilistic results
| about discrete objects rigourously - in fact this is a
| reasonably common technique (going back to work by Paul Erdos,
| and probably further). It can give you concrete information
| about the existence or non-existence of these objects (if
| something exists with non-zero probability in a finite set
| there has to be at least one example). It's not a "less valid"
| way to prove things, just a particular choice of approach.
| Sometimes it makes things easier, sometimes it doesn't.
| ilya_m wrote:
| We are talking about different kinds of "probabilistic"
| proofs. Igor Pak's blog post and the root message in this
| thread refer to statements that are validated only
| probabilistically. The probabilistic method, by Erdos and
| others, is a proof as rigorous as any. "Probabilities" in the
| this method are just a convenient apparatus for counting
| objects.
|
| (As an aside, there's important distinction with statements
| that are believed to be true based on empirical evidence,
| such as hardness of factoring or the Riemann conjecture. If
| the bunkbed conjecture was refuted based on Monte Carlo
| simulations, it'd be possible to reduce the level of
| uncertainty arbitrarily low by throwing more resources at
| running more simulations.)
| bubblyworld wrote:
| Right - I admit I stopped reading the blog post at the
| point they linked to the paper and started reading that
| instead (which contains a rigorous proof). Having read the
| rest of the blog now I can see where the OP is coming from.
| samatman wrote:
| What you're describing is different from the distinction the
| parent is making, which is between providing a high
| probability of evidence that a conjecture is true, versus
| proving the conjecture true through a rigorous formal proof.
|
| Often there are three useful states: none, some, and all. You
| describe a rigorous proof-of-some, because a _proven_
| probability of not-zero guarantees a counterexample exists.
| It 's still news when or if the counterexample is found, but
| given the standard of rigorous proof is met, it does exist.
| Of course another option is to construct a counterexample, as
| was done here.
|
| The case of probability discussed in the Fine Article was
| rigorously demonstrating a 99.99% chance that the probability
| is not zero. That's informative but it isn't proof. _Proof_
| that the probability is not zero, absent the counterexample
| which we now know (rather than expect on good grounds)
| exists, is also a proof. But that isn 't the case being
| discussed here.
| bubblyworld wrote:
| Yeah, I missed that there was a discussion of empirical
| evidence in mathematics in the blog post (rather than the
| probabilistic method).
| feoren wrote:
| > if something exists with non-zero probability in a finite
| set there has to be at least one example
|
| I think you mean an _infinite_ set here. If I have a set
| containing one single coin, and I flip every coin in my set,
| both heads and tails have a non-zero probability to exist
| within my flipped set. But there 's certainly not an example
| of both heads and tails in my single-coin set. Indeed for any
| finite set of coins, there's some chance that either heads or
| tails never shows up.
|
| However, if I have an infinite set of coins and I flip them
| all, certainly both heads and tails must exist (although I
| wouldn't be surprised if even this depends on the axiom of
| choice or something.)
| IshKebab wrote:
| This post could _really_ do with a couple of diagrams of what
| these graphs are. I _think_ I got it from the description but I
| 'm not sure...
| willcipriano wrote:
| It does not in fact give you extra space in your room to do
| activities.
___________________________________________________________________
(page generated 2024-10-02 23:00 UTC)