Math News: The Bunkbed conjecture was just disproven!!!!!!!
ฝัง
- เผยแพร่เมื่อ 9 ต.ค. 2024
- The famous bunkbed conjecture in probabilistic graph theory was disproven with a crazy counterexample with 7222 vertices!
Papers cited:
1) The main paper by Gladkov, Pak, and Zimin: arxiv.org/abs/...
2) The paper by Wagner documenting the machine learning algorithm: arxiv.org/abs/...
3) The paper by Hollom giving the counterexample in the hypergraph generalization: arxiv.org/pdf/...
4) Blog Post by Pak explaining the paper a bit more colloquially: igorpak.wordpr...
5) Blog Post by Pak on "what if they are all wrong", and the value of searching for counterexamples to conjectures: igorpak.wordpr...
BECOME A MEMBER:
►Join: / @drtrefor
MATH BOOKS I LOVE (affilliate link):
► www.amazon.com...
COURSE PLAYLISTS:
►DISCRETE MATH: • Discrete Math (Full Co...
►LINEAR ALGEBRA: • Linear Algebra (Full C...
►CALCULUS I: • Calculus I (Limits, De...
► CALCULUS II: • Calculus II (Integrati...
►MULTIVARIABLE CALCULUS (Calc III): • Calculus III: Multivar...
►VECTOR CALCULUS (Calc IV) • Calculus IV: Vector Ca...
►DIFFERENTIAL EQUATIONS: • Ordinary Differential ...
►LAPLACE TRANSFORM: • Laplace Transforms and...
►GAME THEORY: • Game Theory
OTHER PLAYLISTS:
► Learning Math Series
• 5 Tips To Make Math Pr...
►Cool Math Series:
• Cool Math Series
SOCIALS:
►X/Twitter: X.com/treforbazett
►TikTok: / drtrefor
►Instagram (photography based): / treforphotography
Hi everyone! I’m one of the authors of the paper being discussed.
Dr. Bazett, thank you so much for the fantastic video! It’s as clear and thorough an explanation as we could’ve hoped for, and I really appreciate how quickly you put it together.
Just a small note: the author of the hypergraph paper’s surname is Hollom.
P.S. We are not changing the title to "Debunking the bunkbed conjecture"!
Oh thank you that’s so cool! Loved the paper:)
Too bad about the paper name... Ask ChatGPT for help with paper names next time.
You should. 😂
What about "it's just a bed now :("?
> P.S. We are not changing the title to "Debunking the bunkbed conjecture"!
Ooof. It's okay, you're allowed to be wrong about some things.
The fact that this paper isn't titled "Debunking the bunkbed conjecture" is such a huge miss
ya that's a fail:D
The bunkbed conjecture has been "debunked"
would also make interesting video titles for this
@@DrTrefor You can still change the title 👀
@@csilval18peer review should reject JUST for that reason!
@@DrTreforChange the titleeeeeeee!!!!!
I just explained the problem to a nine-year-old. He paused for a while, gave it some thought, and then repleid: "It's obvious, you just take a hypergraph and replace each triangle with 1204 spokes connected to a center, the probability is about 10^(-4000) greater. I wonder why it took them so long to figure out"
That’s so crazy, my nine year old said the same thing.
As Albert Einstein definitely once said, "If you can't explain it to a six year old and then let them disprove a standing conjecture from the 1980's, widely thought to be true, you don't understand it yourself"
"... and the young man's name: Albert Einstein"
And then everybody clapped
Guys I'm not sure this is true.
Wikipedia editors on their way to change "is" to "was" for the bunkbed conjecture
Not without a disclaimer, at least until the paper is peer reviewed.
Banger "just make every triangle into its own graph with 1000+spokes" angle from these guys
lol ya loved this:D
Does that even converge for infinite spokes?
@@iwersonsch5131Didn't think I'd find the SM64 ABC microcelebrity (nanocelebrity?) Iwer Sonsch here
@@Kebabrulle4869it’s a common name
Really happy to see this! I saw this paper posted on r/mathematics on reddit, and I i tried to read through the paper, but it was difficult for me to really understand it. I did take graph theory in college, but yea, getting through the paper was tough, so it's awesome to have it explained. Thanks Dr Bazett!
Ha, you are like exactly my targeted audience for this video:D
I really like when advances in mathematics have exposure. It would be cool to see more videos like this.
This is actually my first ever "breaking" math video (the paper came out on friday and I was like omg I have to make a video) but I actually hope to do more. Finding the stories that are both interesting AND accessible to a TH-cam audience isn't always the easiest, but I think it is important.
Yes more math news videos would be amazing! Perhaps especially for people who once did math in university but now are doing something else, and aren't part of academic circles anymore. A great way to stay excited about math :)
Graph theory is one of the few branches of modern maths that have conjectures explainable to a layman. Some other are elementary number theory and geometric problems in optimization (like sphere packing, moving sofa)
Still, most current conjectures require years of studying maths to get at least some understanding of their statements
Not to mention highly specialized fields such as algebraic geometry or deep projects like Langlands program
Now I wonder what the smallest graph is which disproves the conjecture
We really don't know! Because their approach was to keep adding more and more spokes until you got a counterexample, it is very plausible that a smaller counterexample exists without such a brute force trick.
If the hypergraph is optimised, I don't know if finding a more optimal graph is feasible.
If there is still a way to optimise the hypergraph, then maybe there's a smaller graph?
@@janzwendelaar907 Well, the hypergraph is optimized for making the smallest number of vertices in the original hypergraph. But given that you have to insert orders of magnitude more extra vertices than there were originally means that there is massive potential for finding a better solution with a hypergraph that is instead optimized for having to insert less extra vertices.
My conjuncture is that this is the smallest graph. I let Igor Pak disprove my conjuncture. When he does, I'll come up with another conjuncture for the smallest graph. At the end of this cycle we will find the true smallest graph.
And now I wonder how much likely you can reach the top bunk than the bottom. I wonder if you can do better than 10^(-4000). It seems unlikely but it might be the case.
The difference in probability they found is 10^(-6509) by the way!
very small (in case that there are people that don't know how to interpret the negative power, here is it written)
1/(10^6509) or 1/100000...(6500 times)...000
very small
How do you compute (or even estimate) a probability that small on a computer? I wouldn't have thought that numerical methods like monte-carlo would be good enough to get error bounds that small in a reasonable computation time.
@@QuantumHistorian
Im also interested in that. maybe the conjecture is true after all
....AKA "effectively zero".
@@Rumpael is the reviewer of these kind of counterexample papers gonna have to validate the result? (not only reviewing for the formatting, etc)
Your restriction to the case of a single "post" is somewhat misleading. The bunkbed conjecture is known to be true if the number of posts is 1 or 2. Indeed, in the counterexample provided in the paper, the number of posts is 3.
Ya that's fair. I was trying to search for the simplest example to animate for TH-cam where we could actually explicitly compute the probabilities and see our example satisfied the conjecture. So please treat that example only as helpful for illustrating the concept, not as the right level of complexity for actually finding a counterexample.
Interesting. I was guessing the counterexample would have a ton of posts like >=20
This just furthers my position that 3 is the weirdest number. Everything gets crazy when you get to 3. Random walks from 2 to 3 dimensions, the number of platonic solids in 3 dimensions, k-satisfiability goes from easy at k=2 to np-hard at k=3 and then all higher k's being reducible to 3-sat, orbits only working in 3 dimensions, and now bunk beds becoming weird with 3 or more posts...
@@sykes1024Yes! I've long thought this since learning about the complexity differences between 2-SAT and 3-SAT in 2005. Then there's also 2-body vs 3-body, I seem to remember something about tiling in 2 vs 3 dimensions, and so on. I wonder if somebody keeps a list of these (and related) threshold effects.
@sykes1024 TREE(3)...
It's a wonderful thing about mathematics that you can have something that everyone looks at and thinks, "This seems like it should be true. It's gotta be!" And then it's not.
The secret to math turned out to be that "cool S" that everyone used to doodle in class.
0:14 If the conjecture “has been disproven to be false” then that means it has been proven to be true.
Putting failed attempts into papers is really an honorable deed.
Ya gotta respect that
@@DrTrefor I do. Nothing is worse than putting years into research and hearing in a side note on a conference that this method had been tried and failed a decade ago, and nobody bothered to tell someone.
I wish you were able to elaborate a bit on the intuition. Basically show why there is a small probability in reverse.
I don't know if that is even possible. If there were a intuitive explanation, then probably would not have been a conjecture for truthfullness in 5he first place
If I were to have a guess, I would say that it probably hinges on 3 factors (though I don't know why they come together in this hyper-graph with the 3 posts, but not the "hyper-edge replacement structure" at the bottom of the screen):
A: There is a super tiny probability that you can go all the way along the red edges in the "hyper-edge replacement structure" to another white vertex of the (hyper-)graph.
B: If you can just go along _enough_ of the red edges, then you're basically guaranteed to have _some_ blue edge along which you can go to the "hub" vertex (which is green and has a post in the (hyper-) graph.
C: (Assuming that none of the red edges goes through the whole way.) The longer the red edge is that you came from, the shorter of a maximum red edge you can have on the same level that stretches back from the opposite white vertex of the hyper-edge; While there isn't the same restriction for neither the red edge stretching back from the opposite white vertex, nor other blue edges coming out through the other pair of hyper-edges on the same post.
But:
D: If you can do this to swap the probability on the bottom hyper-edge then it would preclude you from doing the same swap on the right hyper-edge.
E: If that was all there was to flipping the probability, then that wouldn't explain why you can't do it with only the "hyper-edge replacement structure"; nor why it works for a hyper-graph like this where the number of red edges is *even.*
@@Pystro Basically, I think your first three points come together to the observation that the probability that there's a path in the bottom bunk that contains none of the green vertices is very small. The paths that do contain green vertices also can be slightly modified into paths through the top bunk. The question is then, what gives the top bunk paths the miniscule advantage that they have?
If we have a v v' "post", then the probabilities are the same as if we can reach one, we can reach both.
If v/v' can only be reached by a node x/x', and we have a post x/x', then the probabilities are the same as the probability that vx and v'x' has fade is the same.
If we miss lot of post, this means that to reach v' you need to reach one post, AND to have a path u post + post v'. While u v doesn't have this constraint.
If we have lot of post, then we can "jump" other/under missing links. At any point of the graph, the probability to get to v/v' without any should be the same as the decay is the same for the bottom/top graph.
Adding post should only increase the probability we can reach the top graph (+ the probability to jump under/over a missing link, but both is true for top/bottom graph).
I don't see how the conjecture can be wrong with the given issue...
Just hopping the paper didn't had floating point computations errors xD.
I wish you would explain a bit more why replacing the hyper edges with that structure leads to the result. Something about the number of edges leaving a big possibility of there still being a connected path?
Trying to disprove a Conjecture can help you understand them if you fail too
ya absolutely definitely worth it for gaining intuition
too early to claim bunkbed is debunked - the probability is tiny in a probabilistic method setting. It has to pass through critical scrutiny of reviewers. But the fact that their attempt was more logical than computational gives me hope.
Absolutely. Treat everything here with the normal caveat of a preprint that hasn't gone through peer review - and I'm certainly NOT qualified to be a peer reviewer here.
the fact that it's logical and not computational should give u less hope...if the argument is logical it can have flaws and can be disproven but if it's computational then well the result is right there...nothing you can do about it... perhaps the computational algorithm could be wrong but that's much less likely than a logical flaw
@@theshoulderofgiants You are right, but I meant hope in a different context. I hope there is still enough space for human logical reasoning to come up with great ideas and great results in an era where computation is taking over research.
@@theshoulderofgiants lol, there are a gazillion more different things that can go wrong when dealing with numerical computations, and ESPECIALLY SO when the graph is so large and differences so tiny like in this proof
@@theshoulderofgiantsIt's extremely hard to prove a nontrivial program is correct. And of course then there could always be a flaw in THAT proof!
I’m sure it’s mentioned in the more formal definition of this problem, but the “posts” are not subject to bond percolation, right?
That's right. Take some subset of the vertices and fix posts there THEN do bond percolation on the bunks.
@@DrTrefor Umm, Wikipedia article says that "the probabilities assigned to the posts can be arbitrary. A random subgraph of the bunkbed graph is then formed by independently deleting each edge based on the assigned probability." And I kinda assumed that the posts have non-zero probability of being deleted. I haven't read the paper, or re-watched the video (yet). But surely the posts are subject to percolation, aka. deletion?
@@nikonyrh If it can be arbitrary for the posts, then even if you force it to be nonzero for the posts, then we can just set the chance of removal for the posts to be like 10^‐10000000000, so that it wouldn't change the result if a counterexample like this exists
@@diribigal Ahaa yes, so the interesting part is that "P(u v')" can become GREATER than (not just equal to) "P(u v)", thus being a counterexample (duh). Thanks!
I suppose counterexamples become larger or impossible, as the probability of deleting posts increases.
"What if they're all wrong" really sounds like the hacker ethos. "A system unbreakable? You'll see as I'll try and break it."
Low probability, large payoff.
Maybe it is hindsight, but throughout the first half of this video, I kept yelling 'No!' towards my screen. The conjecture doesn't intuitively feel obviously true to me; I imagine that allowing a certain number of vertical connections, one can find a suitable path from bottom to top that leads to the destination there but no way back (and no direct way between the start and 'lower' destination). Feels are very often wrong, but my point is that I don't find the result surprising at all.
Informative video, there's just one detail that I think is missing: the vertices they're trying to connect in Hollum's counterexample are the top and bottommost.
7:15 The graph has 7222 nodes. So, *probably* not going to be able to imagine it. And the probability difference is minuscule. So, *probably* not going to be obvious.
We can still look for smaller counterexamples, though.
All these years, they've been asking if we could go to v-prime, but nobody was asking if we should. Mathematicians will be the end uf us all.
The way they choose to use the hypergraph to attack the problem is really interesting.
From a human perspective it makes a lot of sense that if you replace a solid triangle with a lot of "closely packed" edges you can expect a similar result, but you really have to think carefully as to why this method had a chance.
The way I see it, every triangle on each floor is connected to one post and two non-post vertices, and the fact that helps this hypergraph beat the generalized conjecture is that severing one triangle means two non-post vertices disconnect for the price of disconnecting one post, so what they needed is something that copies this behavior.
So each triangle is replaced with N spokes connecting N extra vertices to the bed post, and connected in a single file between themselves, and the outer extras each connect to one of the non-post vertices in this triangle we're replacing.
I'll call blue edges spokes, red edges arcs.
So, take the leftmost vertex. If its spoke and arc connections both decay, then this vertex is both disconnected from the post and from the rest of the vertices in the ring.
If the first arc stays connected, but the second arc and the two first spokes decay (less likely because we require more decays), then again the leftmost vertex is disconnected from both.
Even less likely, if the first 3 spokes and the arc from vert 2 to 3 are all lost, we get the same result.
Each of these possibilities is not very likely, and diminishingly so, but we just need one of these to occur, so the total probability is pretty substantial.
Have these occurrences in both extreme vertices, and the new spokes-ring manage to do the job of a triangle.
Using neural networks to solve graph theory problems is so funny. The graph was defeated by another graph.
funny story, they went back and checked that neural network they were using was very similar to the counterexample and this is all a lie I just made it up
it's the superior graph!!!
More math content like this!!
Its really chill listening to some math that isnt a lecture LOL
Idk why.
Igor Pak! Gosh dang, he has been putting out so much stuff recently. An absolute genius of a guy
I’ve never heard of this conjecture, but pretty cool 🤔
It's a good mathematician that doesn't believe arguments from authority. Your math is always smarter than you.
And I like the fact of not depending on computers at all, and using brain power
It feels off that the conjecture would fail with such a tiny margin. If this paper holds, it would be interesting to see an upper bound of the difference in probabilities.
Reviewers be like "it's too smol we can't accept, come back when difference is bigger"
I suspect it's just that they increased the number of edges until the probability overtook the other, probably could've made a bigger difference if they kept adding edges
It's probably a minimal or close to minimal example. Nothing "off" about that.
super high quality broski, deserve more clout
Maybe I'm just saying something silly for not fully understanding it, but as far as I understand it in simple terms: no matter the configuration, you always have to walk a minimum of 1 more pole to get to v' compared to v. That makes it more susceptible to degradation, reducing the probability of reaching it. The debunking really comes across to me as "add so many more poles that a difference of 1 pole becomes neglectable in the probability calculation". Like how if you flip coins you have a higher probability for heads at least once if you flip 2 coins instead of 1 coin, even if this higher probability gets well within the margin of error if you flip 1000 coins vs 1001 coins (practically 100% in both cases, but still, 1 extra coin = 1 extra chance = higher probability).
As I understand it the counterexample in the paper has only 3 posts
The post decay rate is separate from the other decay rate, so for purposes of disproving the conjecture you can set it to zero.
If the violation of the conjectured inequality is so tiny - isn't there a chance the guys had a bug in their multiprecision fractional number implementation? Something like the Pentium FDIV bug?
If they were computing it with standard floating points it wouldn't even have that much precision, I assume this calculation has been checked by hand *or* with a rational-number library rather than floating point
@@psymar Even so, the library is only as good as its assumptions about the computer firmware.
4:45 - no... that does'nt seem true...
the same way you can think that's easier to walk in the bottom graph you now have the top one to "cut away" and connect more things.
but then all of your connections and the things you jumped to are definetly conected before you realize if it's pair can be reached.
so it only makes things worse.
but trully, because I can flatten this graph and just get another bipartition to call one bottom and one top, it creates a simmetry that you shouldn't be able to prove either way is better than another.
This is actually insane!
right?!?
Thanks for the video. What I miss here is the explanation of why that conjecture is interesting to even think about in the first place.
I heard it has applications in all kinds of furniture assembly, not just bunkbeds.
So now, we need to find the constant that bounds the difference. It promises to be a rather interesting mathematical constant!
13:30 - YESSS!!! DONE BY SACLING!
imagine you have like 50 graphs on top of one another to get to u to v^50' you've added so many more paths to to the last graph through the addition of the posts that you can almost be certain that p(c->v50) >>> p(c->v). maybe 50 is still a small number for that.
Also this proof assumes you have a 50-50 chance of an edge staying or going, what is the equation for the number of edges needed based on the probability they disappear?
Really insane!! But it seems almost accessible for a "normal person" with a computer to check just that specific counterexample. Oh, maybe if we go from 1204 to, say, 12040, the difference in probabilities will grow? Anyway, this triangle subgraphs are key. Once they are solved, the rest can be probably brut-forced. Or not, whatever, we'll see. Very exciting and inspiring. I am not a mathematician, so I don't care that even if I can solve it (unlikely), it is going to be reinventing the wheel. Thanks a lot for the film!
2:05 Surely all of these configurations are not equally likely, right? Since each edge being removed is the equivalent of a coin toss, the probability of connectedness should be a weighted sum based on the probability of each of the 15 outcomes. Configurations with 0 and 4 edges removed should not be given the same weight towards the probability as the more likely 1,2, and 3.
Not quite, this would be the case if the edges were not distinct, however each and every edge is unique. So if you go edge-by-edge, deciding whether or not it is deleted or stays the same, each with probability 1/2, you will get that every specific configuration has a probability of 1/16. If you look at the configurations listed on the screen, you will see that naturally more of them do have 1, 2, or 3 edges removed because of what you said, but each specific configuration is still equally likely.
They are equally likely, each configuration has a probability of (1/2)^4 of occurring, because to get a specific configuration you need 4 coin flips to go the right way. The fact that it's more likely to remove 1,2, or 3 edges than 0 or 4 is reflected in the fact that there are just more configurations where 1,2, or 3 edges have been removed (4, 6, and 4 configurations, respectively) than there are configurations where 0 or 4 edges have been removed (1 of each).
@@michaelpristin9944 @finnsoutherland7382 Thanks you guys, I forgot that the "weighting" is already covered in the fact that the possibility space contains more "middling" removals than extreme removals.
Now we need Tom Scott to come back with ""Bunkbed Debunked", Debunked", Debunked
if the difference is 10^(-40) magnitude, does the paper account for errors in computation or did they calculate exactly first mathematically then to give a concrete value they used the computer and it gave 10^(-40)?
My understanding is once the counterexample was found, the computer CAN be fairly precise at computing our the relative probabilities even though the difference is tiny. However in the earlier stage of running machine learning algorithms to try and discover the counterexample, they were doing monte carlo simulations and those were much much less imprecise to find an example like this even if they could have dealt with the huge size (which they couldn't)
It's 10^(-4000)
@@jesusthroughmary mb. but that makes it even more concerning.
@@akirakato1293 I think that's why he made the caveat about peer review
…so…let me get this straight…no one thought to just draw a line from u to the prime of the unlabeled vertices on the top (I’ll call it x’) and then from x’ to v’? Or from u directly to v’ for that matter? Also, the 16 bond percolation graphs from before one creates the “second bunk” should number 17 as I think you’re missing a direct connection from u to v.
I guess the trick is that you're not necessarily just going to an intermediate node on the bottom bunk, going up to the top, then going to v'. You could go up, down, then back up (repeat as often as you like). Not sure why that would make a difference, and as a software engineer I'm definitely aware that accurately computing such a small number is tricky and could easily have went wrong somewhere.
I like how they refer to the Bunkbed Conjecture as BBC in the paper!😂
ha, when I was reading it I thought what on earth is the BBC doing in this paper....oh wait
Big black clock 😂
Big bad crocs
6:55 what kind of statement is that? there is no reason why it would be that way. for the bottom you only have to get from u to w, and for the top, you now have multiple options to get from w to v, while at the bottom you already used up one connection to get to w. you literally have more options.
What about increasing the number of triangles from 1202 to something larger? Does the gap between the probabilities increase further?
The difference in probability is like 10^(-4000) or 10^(-6509)?? That's... unbelievably tiny. Since computers were involved in the computation, are they absolutely certain that there was no rounding errors involved?
Honestly, I don't see how this conjecture can be false...
You have the same copy above, plus you need to walk on the connector, how can this somehow be strictly more likely?
It can, potentially, have multiple ways to get to get to the top and only one way to get to the other side of the bottom without first going to the top and back down.
@@psymar Still, there are seemingly always more ways to get to vertex v than to vertex v'. Indeed, the above copy, being the same copy, has the same number of ways to disrupt it. Not only that, you also need to have an edge to the top bit and of course to reach that edge.
I don't get what you mean when you start adding the posts. It's a completely different graph, right? Don't you have to take P(uw)*P(wv') instead of using P(w'v`) or do the posts not count? So if there was a post from v to v', it would be 5/16 still?
According to wikipedia, any edge in the top bunk must have the same probability as the corresponding edge in the bottom bunk, but the probabilities of the posts can be arbitrary
I assume the posts were just implicitly set to 1 for this example for simplicity
I too was a little confused at first tho
Room for so much more activities!
I don't understand how you can make a hyper bunkbed. Wouldn't the spokes necessarily have to connect to two points on one side and one on the other and thus not be symmetrical?
In Hollum's example along each "bunk" the edges are 3-edges but the posts between the bunks are 2-edges.
@@DrTrefor Aha
Where does the number 1204 come from? It feels like this probably has some grounding in existing math. I'm betting it wasn't just conjured out of thin air.
out of curiosity, how interesting is this to high end mathematicians or people in the math field in general? Is it like 'oh that's cool' or... 'OH MY GOD THIS CHANGES EVERYTHING!!!'?
So they're basically approximating the hyperedges with a large amout of simple edges, like polygons approximate complex shapes? And then as the number of intermediate edges in the approximation grows, the probabilities concerning the graph would converge to the probabilities concerning the hypergraph?
This sounds almost too naive to be true, which makes it even better.
Can you do a video that explaisn why alot of this graph theory results are even usefull?
Its easy to see what you can use continuous math for.
But when it comes to graph theory, half the theorems you learn dont seem very applicable to real life. Their only applicable to certain edge cases. People seem to use graph theory more to train themselves in proofs rather than as an actual tool.
In your experience, how often do conjectures like this get resolved?
Depends what exactly is meant. Conjectures of some type get disproven every day, people think up ideas and other people knock them down. However this conjectured managed to stand since 1985 and was widely believed to be true as I understand it, so it is definitely rarer that something of that nature gets disproven.
how is 10^-4000 significant? Do they have arbitrary precision floating point arithmetic
Probably used a rational-number library instead of floating points
Have weaker forms of the conjecture been proven such as "if there's only one post" or "if you can only travel along a post once"? A conjecture I'll toss is that if at least 1 post exists along every possible path from u to v, the probability of reaching v or v1 will always be equal. Edit: I suddenly realize I've just been assuming the posts themselves never fade. As a followup, I think that if posts have a chance to fade, and there is at least 1 post along every possible path, the chance to reach v would always be higher, never equal.
According to wikipedia, the conjecture has been proven for "specific types of graphs, such as wheels, complete graphs, complete bipartite graphs and graphs with a local symmetry"
I don't believe only traveling each post once would make a difference, since if you travelled a post twice you would have a loop in your path which you could just omit to satisfy the requirement.
(Not quite sure tho, if I'm missing sth please tell me)
@@cimadev I meant the inability to go down through a second post, admittedly I worded it poorly.
@@qedsoku849 Oh, so there can be multiple posts but you can use at most one?
[Edit: I guess you have to use exactly one cause otherwise you never get to the top bunk]
You should probably have specified that the "post" edges are never removed.
Well, there goes the Double Decker Couch concept!
they should have called the paper "debunkbed: the conjecture is false"
I am sorry for asking this question, but when I started uni, I was really passionate about all kinds of math. But now at when I have finished university and started working as a real engineer (and basically not using any math right now), I feel like I can only appreciate complicated math, which is used to solve real practical problems. So, why would anyone care about these bunk-bed graphs and then randomly removing some lines in the graph and then checking is you can go between four points? Seem like very arbitrary with 1 billion equally arbitrary combinations.
Graph theory is very useful in a number of areas, including in the optimization of computation algorithms or system design.
@@XGD5layer Yes of course, but why would anyone care about probabalistic bunkbed graphs?
You sure it isn't a floating point error? 🤔
I heard Godel discovered his first incompleteness theorem by trying to prove the Hilbert program to be true.
Bunkbed: DESTROYED!!
why did my brain auto tldr the title as "They debunked the bunkbed conjecture"
Hopefully it was a floating point arithmetic error on the computer 😅
What motivated this conjecture? I mean like what initiated the study of bunkbeds, like, why?
Probably once there is a big counterexample, people will quickly find smaller ones
Description is incomplete: is the number of posts variable and they fade too (i.e probability over all possible sets of posts)? All graphs equally likely or edges fade with equal probability?
They will get the Nobel Prize in Physics one day for this *sarcasm*
Misopportunity for a paper title: the bunkbed conjecture debunked.
If this were the the first of April, I would have doubted that this proof were genuine.
Can't wait till it turns out that this was a floating point inaccuracy or something like that lol
Can the posts between the upper and lower graphs decay as well, or are they exempt?
Does adding more edges increase the diffrence in probabilities?
I think I have to watch it 1204 times, because I can not understabd how it is possible. Does it imply going up and down?
It seems a very esoteric problem... does anyone outside of those researching it care one way or another? Does it matter - i.e. have any wider ramifications elsewhere, in maths or beyond? Put another way, does this "bunk-bed" idea model anything elsewhere?
This did not confuse me because I am so bad at descrete probability that while studying math I trained myself to have next to no intuition and to only trust formal proofs or calculations.
Waitasecond ... so the probabilities are not computed, they are estimated?
There are many graph theoretic conjectures out there. I wish that you have spent some time explaining why this one is interesting or useful, because otherwise I am not sure why it is any better than any other randomly chosen conjecture.
Also, while I agree that I would put this conjecture in the "likely to be true" section, but I don't think that it is "obvious" (and of course, if the counter example is true, then certainly it is neither). There is just not enough context, or connection to other known results or even conjectures to make this claim. Is this conjecture easy to check for some large families of graphs?
Sometimes conjectures get a sort of "status" within their respective communities not necessarily because the result is crucial to applications, say, but just because people have been consistently trying to chip away at it for decades. At some sort of objective level I don't think this necessarily IS "better" than any other randomly chosen conjecture. I can say that an exhaustive search was performed, but exhaustive searches get huge in graph theory even for small sizes so they stopped searching exhaustively after at most 8 vertices and 15 edges, still pretty small. The machine learning algorithm was searching on larger graphs like # vertices = 30, still tiny compared to the eventual counterexample.
@@DrTrefor
I think that too many times mathematicians tend to work on problems just because someone worked on a similar problem before, instead of looking for a good motivation. This is unfortunate, since in many cases there is good motivation which is almost ignored (though I still don't know if it holds in this case).
Any way, reading the introduction to this counter example paper, the authors say that the conjectured was proved for several families of graphs (e.g. complete graphs, complete bipartite graphs, wheels). They also mention that there are analogues theorems with simple random walks and Ising model on bunked graphs, though unfortunately they still don't really explain why it should be interesting, or at least I couldn't find such an explanation.
@@eofirdavidone reason a problem can be interesting is because people have worked on it and failed to make it true or false. it becomes even more interesting if these attempts produce new approaches which can work on other problems, which is one of the reasons so many people worked on fermat's last theorem.
i also like the authors idea of working on problems where the answer is obvious, but the work has not been done to find out if it is true or not, as that is probably a good place to work on.
So does this mean that a whole lot of math which assumed the Bunkbed conjecture was true just collapsed?
Well, that's going to be a pig to review.
i suspect that this isn't a minimal counter example - unclear how you would radically reduce it.
Ya I think this is only minimal in the sense that IF you start with Hollum's counterexample and try this trick then you need that many spokes. But we'd have to presume it likely there are far smaller counterexamples not discovered.
Physics has a much bigger problem.
Their theorems and interpretations of theories can intrinsically not be proven and are often rather rooted in deep ideological beliefs.
Even if someone managed to convince or prove an isomorphism exists to a standard theory interpretation, the majority would just resist and denounce the value of the reinterpretation since it is phenomenologically the same.
Point being: in mathematics one can pursue to disprove conjectures, but in physics it's pointless.
Does the edge from u' even matter in this? If the edge from u is lost it matter, but the u' edge doesn't. That should matter.
If you're referring to the example in the video, then no, I don't think the edge from u' has any relevance, which is why we see 1/8 instead of 1/16 for the probability of reaching v' after traversing the post edge
I heard IKEA had a million dollar prize for anyone that could prove the conjecture. Too bad for them if turns out to be false. They were hoping to use it to design new vanishing bunkbeds or something like that just kidding I have no idea what I'm talking about.
I believe without a shred of a doubt this is true but can we really call this a proof? it is just asymptotically approaching truth. (Awesome video explaining the paper! I appreciate it)
"The conjecture has just been disproven, in a new paper, to be false." 0:13 < That means the conjecture is true.
I love the English language.
Yes . Poorly worded for sure .
I feel like you missed a great opportunity to say that the "Bunkbed conjecture was just Debunked".
You might say it was DE-BUNK(B)ED !!! ;-)
So basically the conjecture is false but only in specific cases?
dude, you just wasted 15 minutes of my life.
Yes, I watched it till the end.And subscribed.
ha. you can find my proof in the margin of a book in the library of congress. 100 dollars to the person who can find it.
Whats the applicability of this in the real world? (is not irony, i really want to know)
This smells of floating point error
Video title "Math News: The Bunkbed conjecture was just disproven!!!!!!!". I am smiling just thinking about how that came about. Did the Dr go "I would like some click-bait", "... but I can't", "... but maybe(?)", "... what about putting multiple exclamation points?", "... Yeah, that is a good compromise!". Then probably spend all day contemplating the exact number (we now know it is 7; a prime pick). Well that is my guess anyway.
That's a lot of factorial symbols