Math’s ‘Bunkbed Conjecture’ Has Been Debunked

The bunkbed conjecture says that the probability of finding the path on the bottom bunk is always greater than or equal to the probability of finding the path that jumps to the top bunk. It doesn’t matter what graph you start with, or how many vertical posts you draw between the bunks, or which starting and ending vertices you choose.

For decades, mathematicians thought this had to be true. Their intuition told them that moving around on just one bunk should be easier than moving between two — that the extra vertical jump required to get from the lower to the upper bunk should significantly limit the number of available paths.

Mathematicians also wanted the bunkbed conjecture to be true. It belongs to a class of statements in an area called percolation theory, which deals with the paths and clusters that exist after graphs have edges deleted at random. These graphs can be thought of as simplified models of how a fluid moves, or percolates, through a porous material, the way water moves through a sponge. The bunkbed conjecture, for its part, would imply a widely believed assumption in physics about how likely a fluid is to travel through a solid. It would also hint at how to solve related problems about the physics of percolation.

But that would only happen if someone could prove that the bunkbed conjecture was true. There was a reason why no one could.

Probably Wrong

Igor Pak, a mathematician at the University of California, Los Angeles, always had his doubts that the bunkbed conjecture was true. “He was skeptical from the very beginning,” said Nikita Gladkov, one of his graduate students. “He’s a big disbeliever in old conjectures.” Pak has been a vocal critic of mathematicians’ tendency to focus their efforts on proving such conjectures. He asserts that equally important advances can come from asking, “What if they are all wrong?”

Pak also had a particular reason for doubting the bunkbed conjecture: It seemed to be far too broad a claim. He was skeptical that it would really hold for every conceivable graph. “Some conjectures are motivated by substance, and other conjectures are motivated by wishful thinking,” he said. The bunkbed conjecture seemed like the latter.

In 2022, he set out to disprove it. He spent a year making failed attempts. Then he instructed Gladkov to use a computer to run an exhaustive, brute-force search on every graph he could. Realizing the task would require some sophisticated programming, Gladkov enlisted a friend he’d known since high school, Aleksandr Zimin, now a graduate student at the Massachusetts Institute of Technology. “We actually were roommates in college — we had a real bunk bed in our dorm,” Gladkov said.

Gladkov, Pak and Zimin were able to manually check every possible graph with fewer than nine vertices. In these cases, they could verify that the bunkbed conjecture held true. But for larger graphs, the number of possible situations blew up. They couldn’t account for all the possible ways that edges could be deleted or paths could be formed.

The team then turned to machine learning. They trained a neural network to produce graphs with circuitous paths that might potentially prefer the upward jump. In many of the examples it spat out, they found that a bottom-bunk path was only the tiniest bit more probable than its top-bunk alternative. But the model didn’t uncover any graphs where the reverse was true.

There was another problem. Each graph the neural network came up with was still so large that the mathematicians couldn’t possibly investigate every single outcome of the coin-flipping step. Rather, the team had to compute the probability of finding upper and lower paths over a subset of these outcomes — much as polls sample from a subset of voters to predict the result of an election.

The mathematicians realized that they could be more than 99.99% confident in any counterexample their neural network gave them — but not 100%. They began to doubt whether pursuing this approach to the problem would be rewarded. It was unlikely to convince the mathematical community; certainly no prestigious journal would consider it a rigorous proof. “Ph.D. students need jobs in reality, not in theory,” Pak wrote on his blog — and Gladkov and Zimin would be looking for jobs soon. “That is really why we stopped,” he continued. “Why persevere and create controversy when you can just try doing something else?”

They gave up on their computational approach, but they didn’t stop thinking about the problem. For the next several months, they focused on formulating a theoretical argument that wouldn’t require a computer. But they didn’t have all the pieces they needed to complete it.

Then a breakthrough came from abroad.

Who Needs Computers?

In June, Lawrence Hollom of the University of Cambridge disproved a version of the bunkbed problem in a different context. Instead of dealing with graphs, this formulation of the conjecture asked about objects called hypergraphs. In a hypergraph, an edge is no longer defined as the connection between a pair of vertices, but rather as the connection between any number of vertices.

Hollom found a counterexample to this version of the conjecture. He created a small hypergraph whose edges each connected three vertices: