5 ms·
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/mo
by 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 agoThe (disproven) conjecture is for finite graphs.
- joelignaatius 2y agoI 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 agoYes, 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 agoIt 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]