Mathematicians debunk the “bunk bed conjecture”, 40 years later

Is staying at the same level easier than changing levels?

For decades, the “bunk bed conjecture” was a cornerstone of graph theory, widely accepted as true (despite having no proof).

Proposed by physicist Pieter Kasteleyn in 1985, the conjecture suggested an apparently intuitive idea about probabilities in graph traversal. However, a team of mathematicians has disproved this long-held hypothesis in a paper on arXiv.

What is the “bunk conjecture”?

The conjecture involves “bunk graphs,” which consist of two identical graphs connected vertically by “posts.” It postulated that, for any two points (vertices) \(u\) and \(v\) in the graph, the probability of reaching \(v\) from \(u\) at the same level (base) is always greater or equal to the probability of reaching \(v’\) (the corresponding point on the upper level) through the connecting posts, explains .

The idea seemed self-evident: intuitively, staying at the same level would seem easier than changing levels. Attempts to prove the conjecture have always maintained their logic, and no counterexample has been found—until now.

The refutation

The refutation of a hypothesis often requires only a counterexample, and that is precisely what the mathematician Igor Pak and his colleagues sought to find. Initially, they used computational methods, testing small graphs and using AI and neural networks. However, their algorithms were unable to identify definitive counterexamples, and even if one were found, it would likely not meet the strict standards of mathematical proof.

The discovery came when an article by Lawrence Hollom, a postgraduate at the University of Cambridge, presented an alternative perspective. Hollom’s research examined a generalized version of the bunk bed conjecture involving hypergraphs and found it to be false, which inspired Pak’s team to construct a counterexample to the original conjecture.

The result was a colossal graph with 7,222 vertices and 14,442 edges. Although the difference in probabilities for the graph was miniscule — on the order of \(10^{-6500}\) — it was definitely negativeproving that the conjecture was false.

The refutation of the bunk bed conjecture has theoretical and practical implications. For applied mathematics and physics, the validity of the conjecture would have reinforced assumptions about phenomena such as the percolation of fluids into solids. Their falsity complicates these models, forcing researchers to reevaluate fundamental beliefs.

For mathematicians, the lesson is clear: Even the most intuitive conjectures require close examination. As Princeton mathematician Noga Alon said, “we have to be suspiciouseven of things that intuitively seem very likely to be true.”