4 ms·

> 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 des

> 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 2y ago
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 2y ago
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 2y ago
  The (disproven) conjecture is for finite graphs.
- joelignaatius 2y ago
  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 2y ago
    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 2y ago
      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.
    - deleted 2y ago
      [deleted]
    - heiploy 2y ago
      [dead]
  - deleted 2y ago
    [deleted]
  - heiploy 2y ago
    [dead]
ted537 2y ago
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 2y ago
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 2y ago
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.

keepamovin 2y ago

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 2y ago

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 2y ago
The (disproven) conjecture is for finite graphs.
joelignaatius 2y ago
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 2y ago
  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 2y ago
    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.
  - deleted 2y ago
    [deleted]
  - heiploy 2y ago
    [dead]
- deleted 2y ago
  [deleted]
- heiploy 2y ago
  [dead]

ted537 2y ago

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 2y ago

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 2y ago

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.