De-bunking the bed

Everything will cancel out, I promise.¹

The Bunk Bed Conjecture, formulated in the early 80s, states that, for any graph $G$, given an identical copy of it $G'$ that is connected to $G$ via some edges connecting the corresponding transverse vertices $v, v'$ of the two graphs: the probability that two vertices $u, v \in G$ remain connected after each of the edges is retained or deleted probabilistically according to Bernoulli Bond Percolation is greater than or equal to the probability that some other path $u \leftrightarrow v'$ exists which traverses both $G$ and $G'$.

In this article, I take a look at a recent development in this corner of the graph theoretic academic circle, namely this paper² titled The Bunkbed Conjecture is False by Gladkov, Pak, and Zimin, which relies heavily by the similarly recent findings in this paper³ by Lawrence Hollom called The bunkbed conjecture is not robust to generalisation.

Bernoulli Bond Percolation

For a graph $G = (V, E)$, each edge is independently retained with $p \in [0, 1]$, or deleted with probability $1 - p$.

$\mathbb P_p[u \leftrightarrow v]$ denotes the probability that $u, v \in V$ remain connected after atrophy subject to $p$.

A Bunkbed graph $\widehat{G} = (\widehat{V}, \widehat{E})$ is constructed by connecting a copy of some graph $G$, denoted $G'$ to itself by some "bunkbed" posts marked $T \subseteq V$. By connecting all such transverse vertices $t \in T$, to their corresponding $t' \in T'$, we obtain a subgraph of the product graph $G \times K_2$:

N.B. $K_n$ is the komplett graph on $n$ vertices. If $T = V$ –that is _each vertex ought to be used as a transverse bunk post– then $\widehat G = G \times K_2$.

So our bunkbed graph $\widehat{G}$ is the union of both sets of vertices from $G$ and $G'$ together with the union of their edges, as well as the edges formed between their transverse vertices:

Additionally, note that the transverse edges of $\widehat T$ are not generally subject to percolation (otherwise we wouldn't be able to say very much at all about the bunkbed conjecture). Unambiguously, we can write $\mathbb P_p^{bb}[u \leftrightarrow v]$ to denote probabilistic post-percolation connectivity on a bunkbed graph, but the superscript is often omitted when contextually obvious.

The Bunkbed Conjecture

Formally, the bunkbed conjecture is stated:

That is: it is always at least as likely that we can go from $u$ to $v$ or vice versa without needing to traverse up or down to the bunked copy $G'$. For decades, though a general proof proved to be elusive, this seemed intuitively obvious.

Obvious to all except the skeptical authors of this paper, one of whom posed the question in a philosophical blogpost about the field of mathematical disproof:

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?⁴

Let's take a look at why this conjecture is apparently so obvious. Recycling the example graph $G$ from before, and labeling two of the vertices $u$ and $v$

we can consider all $2^4$ possible atrophied states after bond percolation (4 edges with two states each: retained/deleted) and observe that in only 5 of those 16 states does there remain a path from $u \leftrightarrow v$:

so

In the minimally non-trivial toy example with a singular bottlenecking transverse post, the ~intuition of the Bunk Bed Conjecture finds its footing:

In order to make it down/up from $G$ to $G'$ a path must first exist from $u$ to the transverse vertex $t$. Then, there must be an additionally connected component from $t'$ to $v'$. Occam's razor dictates that this (the product of two probabilities rather than one) should generally be less likely. Referring to the above table, we again see that there are 5 percolated configurations where there exists a path from $u \leftrightarrow t$ and even more configurations with residual paths from $t' \leftrightarrow v'$. Nevertheless, combining these two outcomes produces a strictly less-likely outcome than just relying on paths entirely contained within $G$.

The delta between the two probabilities $\mathbb P_{1/2}[u \leftrightarrow v] - \mathbb P_{1/2}[u \leftrightarrow v']$ in the counter example graph that the authors discovered is less than $-10^{4332}$ which is well within the margin of computational error for non-arbitrary precision floating point numbers, let alone the monte-carlo sampling technique they used, so we can see how finding such a counter example proof –even with sophisticated pruning of the search space– would be akin to finding a needle in a ball pit.

Hollom's Hypergraph

The main theorem presented in Gladkov, Pak, and Zimin's paper is a specific counterexample disproving the BBC. The counterexample is a finite, planar connected graph comprised of 7,222 vertices, 14,442 edges, where three of the vertices are selected to be transverse.

The proof relies on a reverse-engineered construction on a hypergraph which is a higher-dimensional graph where vertices are connected by faces rather than mere edges. A hypergraph is said to be uniform or $n$-uniform if all of the hyperedge faces have the same number of edges ($n$). A path on a hypergraph is a sequence of vertices $(v_l, v_m, v_n, ...)$ where any two vertices in the path $v_i, v_j$ lie on the same hyperedge.

Around the same time that Gladkov, Pak, and Zimin started working on disproving the Bunkbed Conjecture via brute force... (though we know that Pak has had this conjecture on his hit list for at least 4 years,⁵ Hollom was exploring the generalizability of various graph theoretic conjectures to hypergraphs. Back in June, he proved that the BBC does not hold for hypergraphs, presenting the following counter example:

Let $H$ be a finite connected hypergraph on the set of vertices $V$, $\mathbb P_p[u \leftrightarrow v]$ be the probability of connectivity between $u,v \in V$ after hypergraph percolation, where a hyperedge $e \in H$ is retained with probability $p$ and deleted according to $1-p$.

To build the hyper bunkbed graph, we select some $T \subseteq V$ to be the set of transverse vertices connecting $H$ and $H'$ to form $\widehat H$. Hollom considers a slightly nuanced version of the BBC called the alternate BBC in which an edge $e \in H$ is retained iff the mirrored $e' \in H'$ is deleted and vice versa according to $p = 1/2$. Without loss of generality, counterexamples to the alternate BBC hold for the general BBC since the former focuses on a subset of graphs whose behavior is described by the latter BBC as well).

For the specific graph presented above with six $3$-edges, Hollom shows that for

we have

for $2^6$ atrophied configurations, 13 of the 64 residual graphs contain paths from $u_1 \leftrightarrow u_{10}'$ whereas only 12 contain contain direct paths from $u_1 \leftrightarrow u_{10}$.

Gladkov et al took Hollom's result and used it to prove –in a sick monke-brained way– a robust proof of their non-hyper counterexample. This is the kind of mathematical reasoning that sounds like "there's no way this should work, but it does," and I love it.

Harris-Kleitman Inequality

In order to better quantify hyper graph percolation behavior, Gladkov et al leverage an existing model developed by Wierman and Kiff⁴ which proceeds as follows.

For any hypergraph edge $e = \{ a, b, c \}$ , where $a \in T$ is a transverse vertex, there are four possible probabilistic outcomes:

• $p_{abc}$ all three vertices are in the same connected component,
• $p_{a|b|c}$ none of the three vertices are in the same connected component,
• $p_{a|bc}$ just the non-transversal vertices remain connected,
• and $p_{ab|c} = p_{ac|b}$ that the transversal vertex remains connected to exactly one of the other vertices.

Each of these outcomes is chosen independently of other hyperedges, and because these five outcomes enumerate all possible outcomes, we know that they sum to 1 as well:

For the hypergraph $H$, introduced above, with $T = \{u_2, u_7, u_9 \}$ being the set of transverse vertices, adhering to WZ-percolation described above, if the connection probabilities satisfy

then, as a consequence of Harris-Kleitman inequality, we also get:

"Woah woah woah," you might be saying "what the hell is even that?". In the context of graphs the Harris-Kleitman inequality states that for any two events that become more likely as additional edges are added to a graph (such as hyperedge connectivity $p_{abc}$ or dis-connectivity $p_{a|b|c}$), the probability that both events occur together is greater than or equal to the product of their individual probabilities.

Stated more comprehensively in a separate paper⁶ by Gladkov (with foreshadowing acknowledgements to Pak and Zimin as well), for a set of edges $V = \{1,2, ..., n\}$, with a set of edges $E$ independently weighted by $p_{e\in E} \in (0, 1)$, we form a graph $G$ and attain a spanning supgraph $H \subseteq G$ with probability

Using the same WZ-percolation notation above, the Harris-Kleitman inequality w.r.t. Bernoulli graph percolation states that:

Rearranging some terms and dropping the superfluous $p_{12|3}p_{1|23}$ term which is impossible to achieve on a hypergraph we arrive at:

indicating that $p_{13|2} \equiv p_{ab|c}$ needs to be increased by three orders of magnitude in order to satisfy the WZ-percolation constraint. But how would we go about juicing a probability $p_{e} \in [0,1]$ to $400$? Well, one way to do it would be to add 400 copies of each vertex pair of the form $p_{ab|c}$...

Put the Womack on 'em

Leveraging the symmetries and asymmetries within Hollom's hypergraph subject to WZ-percolation, the authors of the general BBC disproof show that for $n \ge 3$, $p \in [0, 1]$, a graph $G_n$ on $n+1$ vertices (resembling the following biblically accurate gadget graph) with vertices $b = v_1$ and $c = v_n$, the following relationship is true:

where

To apply Hollom's result to the non-hyper instance of the BBC, the authors fix $p=1/2,$ and $n= 3 \cdot 401 + 1$ yielding a gadget graph $G_{1204}$ with 2407 edges which they insert into Hollom's graph, replacing each hyperedge with a copy of $G_n$ constructed above, where $a\in G_n$ is the transversal vertex from $T = \{u_2, u_7, u_9\}$, and $b,c$ are simply the other two vertices.

For example, here $a$ maps to $u_2$, $v_1$ to $u_4$, and $v_n$ to $u_5$. We repeat for the other five 3-edges of $H$.

The resulting graph is still planar, but with far higher "resolution" if you will, with $10 + 6 \cdot 1202 = 7222$ vertices, and $6 \cdot 2407$ edges. This triangulated version of $H$, once bunk'd, satisfies:

even if only by the tiniest proportion. The reason this works is that for each $\mathbb P_p[a \leftrightarrow v_k]$, we have 1202 "chances" to connect via a retained edge.

Go-go gadget $G_n$

The proof follows neatly from three recurrence relations on the spoke gadget.

Claim:

There are two cases to consider for $p_n = \mathbb P_n[a \leftrightarrow v_n]$:

Case 1: $e = (a, v_n)$ is retained, which occurs with probability $1-p$, leaving $a$ directly connected to $v_n$:

Case 2: $\color{red}e\color{black} = (a, v_n)$ is deleted, which occurs with probability $p$, so $v_n$ is only (maybe) connected to $a$ via $\color{green}e'\color{black} = (v_{n-1}, v_n)$ which is, in turn, retained with probability $p$. If $e'$ is a casualty of percolation, then $v_n$ is unreachable from $a$, otherwise the probability that $a$ and $v_{n-1}$ are in the same connected component is recursively given by $\color{blue}p_{n-1}\color{black}$, so the complete term is $p(\lnot \color{red}e\color{black})p( \color{green}e'\color{black})\color{blue}p_{n-1}\color{black} = p^2p_{n-1}$ .

Combining the probabilities of these two cases together we get:

And with the base case of $p_0 =0$, we can derive the formula in the claim:

Applying this lemma to a path traversing each of the three sentinel vertices of hyper edge, we have the additional claim that:

To derive this decidedly chunkier recurrence we consider now four cases on $p_n = \mathbb P_p [a \leftrightarrow v_1 \leftrightarrow v_n]$, faceting on the percolation of two edges $(a, v_1)$ and $(a, v_n)$:

case 1: $(a, v_1)$ and $(a, v_n)$ are both retained with probabilities $1-p$, such that $a$ is directly connected to both $v_1, v_n$ for a composite probability of $(1-p)^2$.

case 2: $\color{red}e\color{black} = (a, v_n)$ is deleted with probability $p$, leaving $v_n$ to be connected to the rest of the graph only by $\color{green}e'\color{black} = (v_{n-1}, v_n)$, which itself is retained with probability $p$, which –as established above– means $v_n$ is still reachable from $a$ with probability $p^2p_{n-1}$.

case 3: $\color{red}e\color{black} = (a, v_1)$ is deleted with probability $p$, same as above from the opposite direction: $p^2p_{n-1}$.

case 4: $\color{red}e_1\color{black} = (a, v_1)$ and $\color{red}e_n\color{black} = (a, v_n)$ are both deleted with probabilities $p$. In order for $a$ to still reach both $v_1$ and $v_n$, then the edges $\color{green}e_1'\color{black} = (v_1, v_2)$ and $\color{green}e_n'\color{black} = (v_{n-1}, v_n)$ must be retained with probabilities $p$, and we apply the recurrence relation inwards from both directions to determine if $a, v_2, ..., v_{n-1}$ are in the same connected component, yielding: $p^4p_{n-2}$.

Again, combining all terms we get:

which, with the initial conditions of $p_0 = 0$, and $p_1 = 1 - p$ and an inductive proof (painfully omitted by the authors, damn you) yields the formulae .

Solving linear recurrences is a standard technique. Usually one goes by finding the characteristic polynomial of the recurrent relation and its roots known as characteristic roots of the recurrence. The next step depends on whether the roots are different or not.

Here we are in this case and the roots coincide. So one just needs to guess the constants (1-p)/(1+p) and -1.⁷

Now, I'm not sure what strain of combinatorial analysis paq Nikita was smoking to derive the desired equation of:

but we can verify that it's true via the technique he courteously shared with me. First, we verify the base cases.

For $n = 0 \implies p_0 =0$, we have:

For $n = 1 \implies p_1 = 1-p$, we have:

which also checks out. Next we examine the characteristic polynomial of $p_n = (1-p)^2 + 2p^2p_{n-1} - p^4p_{n-2}$ which has the form:

We rewrite $p_n$ in the standard form as:

ignoring the constant $(1-p)^2$ and substitute $p_n = r^n$ to the homogenous residual equation:

yielding the roots:

giving us a general solution of the form:

And, substituting our initial conditions of $p_0 =0, p_1 = 1-p$ back into this general solution, we can solve for $A$ and $B$ to arrest the recurrence:

which, through some tedious binomial expansions, simplifies to the desired form:

And finally, in the case where the transverse vertex $a$ is not connected to $v_1$, but $v_1$ is connected to $v_n$:

we multiply the weights of the path connecting $v_1 \leftrightarrow v_n$ yielding $p^{n-1}$ combined with the probability that $a$ is not connected to this path (implying that all edges of the form $(a, v_k)$ are deleted which happens with probability $p^n$) yielding $p^{2n-1}$.

leveraging a relation identified by [Gla24]:

Finally, we can leverage all these formulae in the notation of hyperedge connectivity to show that:

We have equations for:

• $p_{abc}: \mathbb P_p[a \leftrightarrow v_1 \leftrightarrow v_n]$
• $p_{ab|c}: \mathbb P_p[a \leftrightarrow v_1]$
• $p_{ac|b}: \mathbb P_p[a \leftrightarrow v_n]$
• $p_{a|cb}: \mathbb P_p[a \not\leftrightarrow v_1 \leftrightarrow v_n]$

but none for $p_{a|b|c}$, so we need to rewrite the left hand side of the equation in terms of the hyperedge probabilities that we do know. Additionally, I'll alias the hyperedge probability terms for readability as follows:

and recall that

So now we can homogenize the equation as follows:

This result satisfies the same percolation condition which Hollom's hypergraph utilizes which is:

So we know that the gadget produces the desired outcome.

Footnotes