Graph Theory: The Bunk Bed Conjecture is False

In mathematics, certain conjectures arouse very strong convictions among specialists – for example, few mathematicians think that the Riemann hypothesis or the Syracuse conjecture are false. However, sometimes a statement that everyone thought was true turns out to be wrong. This is what happened for the “bunk bed conjecture”, in graph theory: at the beginning of October 2024, Nikita Gladkov and Igor Pak, from the University of California at Los Angeles, as well as Aleksandr Zimin , from MIT (the Massachusetts Institute of Technology), all in the United States, have posted a pre-publication online in which they present several counterexamples to a statement which, however, has gained wide acceptance since its first formulation in 1985.

Consider a graph G connected (i.e. a set of vertices linked together by edges, forming a single structure) and duplicate it to obtain a second graph G’identical. Now let’s choose a subset of the vertices of Gand connect each of them by a new edge to the corresponding vertex of G’. In this way, we construct a new graph resembling a bunk bed, the lower bunk of which is the graph Gthe one at the top of the graph G’and the amounts are these edges joining cousin vertices of G et G’. Now imagine that each edge of this “bunk bed” disappears with a certain probability p. As G was connected (in one piece), it was always possible, in the initial graph, to join any two vertices of G – let’s say A et B – by a continuous path of edges of G. Like certain summits of G were connected to corresponding vertices of G’and that G’was also connected, it was also possible, in the initial bunk bed, to connect A at the top of G’corresponding to B – let’s call it B’. But what happens once certain edges are randomly removed? The 1985 conjecture states that, in the final bunk bed (after probabilistic removal of edges), the probability that a path joining A et B is higher than the probability that a path joining A et B’.

In working on this conjecture, Nikita Gladkov and his colleagues were inspired by the results of Lawrence Hollom, a doctoral student at the University of Cambridge, England, who was also studying the problem, initially to demonstrate that the statement was correct. As the result resisted him, he concentrated on the same question transposed to slightly more “docile” objects. »: hypergraphs, a generalization of graphs where edges can connect more than two vertices. “As I wasn’t making much progress, I started looking at similar problems on hypergraphs, but simpler. However, I noticed that for the bunk bed conjecture to be true, many other, simpler statements had to be true as well… and that it was ultimately going to be very difficult to guarantee that these statements were always verified, all at the same time! » Result: the researcher changed his mind, and, in June 2024, he presented in a prepublication a counterexample to the bunk bed conjecture for hypergraphs.

It is from this work that Nikita Gladkov, Igor Pak and Aleksandr Zimin in turn managed to construct a counterexample to this conjecture, this time for graphs, in the case where the probability of edges disappearing worth p = 1/2. “Our counterexample is a graph G at 7,222 peaks, says Nikita Gladkov. It’s huge, but that size comes from the fact that we hand-built it from Lawrence Hollom’s hypergraph. We therefore understand very well why he does not verify the conjecture! » In this giant counter-example, there are indeed two vertices A et B of the graph G such as the probability that a path joining A et B in the bunk bed, after deletion of each edge with probability 1/2, is smaller than the probability that a path joining A et B’. Ridiculously smaller, it’s true: the difference in probability is less than 10^-4331. But smaller all the same.

Note that, still in the case where p = 1/2, the researchers identified a much smaller counterexample: a graph G at 82 peaks. But the latter is less well understood: “We don’t know how to do without a computer to prove that it is indeed a counterexample,” laments Nikita Gladkov.

Igor Pak likes to say that out of a week of mathematics research, it is good to devote six days to proofs and one day to counterexamples. Nikita Gladkov agrees: “Perhaps this episode shows that we need to be more skeptical about classic conjectures. When you manipulate large, not very rigid structures, there are a lot of degrees of freedom: this leaves room for unexpected and counterintuitive things to happen. »