Igor Pak's blog

What follows is an unusual story of perseverance. We start with a conjecture and after some plot twists end up discussing the meaning of truth. While the title is a spoiler, you might not be able to guess how we got there…

The conjecture

The bunkbed conjecture (BBC) is a basic claim about random subgraphs. Start with a finite graph G=(V,E) and consider a product graph G x K₂ obtained by connecting the corresponding vertices on levels V⁽¹⁾ and V⁽²⁾. Sort of like a bunkbed. Now consider random subgraphs of a this product graph.

Bunkbed Conjecture: The probability that vertices u⁽¹⁾ and v⁽¹⁾ are connected is greater or equal than the probability that vertices u⁽¹⁾ and v⁽²⁾ are connected.

In other words, the probability of connecting two vertices on the same level cannot be smaller than when connect vertices on different levels. This is completely obvious, of course! And yet the conjecture this problem defeated several generations of probabilists and remained open until now. For a good reason, of course. It was false!

The origins of the conjecture are murky, but according to van den Berg and Kahn it was conjectured by Kasteleyn in the early 1980s. There are many versions of this conjecture; notably one can condition on the subset of vertical edges and ask the same question. Many partial results are known, as well as results for other probabilistic models. The conjecture is false nonetheless!

The direction

Why look for a counterexample if the conjecture is so obviously true? Well, because you always should. For any conjecture. Especially if everyone else is so sure, as in completely absolutely sure without a doubt, that the conjecture is true. What if they are all wrong? I discuss this at length in this blog post, so there is no need to rehash this point.

The counterexample

We disprove the conjecture in a joint paper with Nikita Gladkov (UCLA) and Alexandr Zimin (MIT), both graduate students. Roughly speaking we take the following 3-hypergraph from a recent paper by Hollom.

We then replace each yellow triangle with the following gadget using n=1204, placing a in the shaded vertex, while v₁ and v_n are placed in the other vertices of the triangle (so the red path goes into the red path). For a stronger version of the conjecture that’s all there is. For a weaker version, some additional tweaks needed to be made (they are not so important). And we are done!

The resulting graph is has 7523 vertices and 15654 edges. The difference between probabilities for paths between u₁ and u₁₀ at the same and different levels as in the conjecture is astronomically small, on the order of -10^-6500. But it’s negative, which is all we need. Very very roughly speaking, the red path is the only path which avoids shaded vertices and creates a certain bias which give this probability gap. Formalizing this is a bit technical.

The experiments

Of course, the obvious way to verify our counterexample computationally would fail miserably — the graph is much too large. Instead, we give a relatively elementary completely combinatorial disproof of the BBC that is accessible to a wide audience. I would rather not rehash technical details and ideas in the proof — it’s all in our paper, which is only 12 pages! See also the GitHub code and some explanation.

I do want to mention that giving formal disproof was not our first choice. It’s what we ended up doing after many failures. There is always a bit of a stigma people have about publicly discussing their failures. I know very few examples, only this one famous enough to be mentioned. So let me mention briefly how we failed.

Since I was sure the bunkbed conjecture is false (for reasons somewhat different from my contrarian philosophy), we started with a myriad of computer experiments trying all small graphs. When those failed, we tried to use AI and other computer assisted tools. We burned many hours on a giant UCLA Hoffman2 Cluster getting closer for a while. In hindsight, we didn’t look in the right place, obviously. After several months of computer experiments and no clear counterexample, it felt we are wasting time. We then thought a bit more about philosophy of what we are doing and stopped.

Before I tell you why we stopped, let me make a general recommendation. Please do try computer experiments for whatever you are working on. Make an effort to think it through and design a good experiment. Work hard to test as much as your computer technology allows. If you need some computing power, ask around. Your university might just have the resources. Occasionally, you can even ask a private company to donate theirs.

If you succeed, write a paper and publish it. Make your code and work notes publicly available. If you fail, do exactly the same. If the journals refuse to publish your paper, just keep it on the arXiv. Other people in your area would want to know. And as far as the NSF is concerned, all of this is “work product”. You can’t change the nature of the problem and the results you are getting, but you deserve the credit regardless.

Let me repeat: Do not fear telling other you have not succeeded in your computer testing. Fear others making the same mistakes or repeating the same work that you did.

The curse

One reason we stopped is because in our initial rush to testing we failed to contemplate the implications of Monte Carlo testing of even moderately large graphs. Here is a quote from the paper:

Suppose we did find a potential counterexample graph with only m=100 edges and the probability gap was large enough to be statistically detectable. Since analyzing all of 2^m ≈ 10³⁰ subgraphs is not feasible, our Monte Carlo simulations could only confirm the desired inequality with high probability. While this probability could be amplified by repeated testing, one could never formally disprove the bunkbed conjecture this way, of course.

This raises somewhat uncomfortable questions whether the mathematical community is ready to live with an uncertainty over validity of formal claims that are only known with high probability. It is also unclear whether in this imaginary world the granting agencies would be willing to support costly computational projects to further increase such probabilities (cf. [Garrabrant+’16], [Zeilberger’93]). Fortunately, our failed computational effort avoided this dystopian reality, and we were able to disprove the bunkbed conjecture by a formal argument.

Societal implications aside, it is an interesting question whether a reputable math journal should accept a counterexample that is tested with 99.99% confidence, and the results can be replicated and rechecked by others. Five sigma may be a gold standard in nuclear physics, but math journals tend to prefer 100% correctness (even though some papers they publish are 100% incorrect).

What I do know, is that most journals would refuse to even consider a “five sigma counterexample”. While details of the situations differ quite a bit, I knew what happened to the (rather interesting) Sills–Zeilberger paper, which was eventually published, but not after several desk rejections. But PhD students need jobs in reality, not in theory. That is really why we stopped. Why persevere and create controversy when you can just try doing something else?

P.S. There is yet another layer to all of this. Back in 1999, I asked Avi Wigderson if P=BPP? He said “Yes“. Last week I asked him again. This is 25 years later, almost to the day. He said “Yes, I am absolutely sure of that.” It’s one of his favorite conjectures, of course. If he is right, every probabilistic counterexample can be turned into deterministic. In other words, there would be a fully rigorous way to estimate both probabilities and prove on a computer that the conjecture is false. But you must have guessed what I was thinking when I heard what he said — now he used “absolutely sure“…

P.P.S. There is a very nice YouTube video about our paper made by Trefor Bazett. Another (even better) YouTube video by Johann Beurich (in German). See also this article in Quanta Magazine, this in IFLScience, that in Pour la Science (in French) and that in Security Lab (in Russian) about our work and this blog post.

UPDATE (June 13, 2025). This took awhile, but the paper was just published at PNAS.