Worked solution: Gladkov–Pak–Zimin's explicit counterexample disproving the bunkbed conjecture (2024)

Step 4 of 8: The robust hyperedge lemma: a small leak does not spoil the imbalance

In plain words

Since $p_{a|bc}$ can never be pushed all the way to zero, Gladkov, Pak, and Zimin instead ask a more forgiving question: how large can the leaked probability $p_{a|bc}$ be before it wipes out the connectivity imbalance that made Hollom's example work? They prove a precise inequality — as long as the leak stays small relative to the other four outcome probabilities, in a specific quantified sense — the same qualitative violation of the bunkbed inequality survives.

The proof of this inequality is a delicate combinatorial argument: it pairs up unlikely percolation outcomes with likely ones via a carefully chosen re-matching (an involution), showing that outcomes favouring same-level connectivity can always be systematically outweighed by outcomes favouring cross-level connectivity, as long as the leak term is controlled. This is the paper's key technical innovation, making the whole strategy 'robust' to the imperfection any real graph gadget must have.

400\, p_{a|bc} \le p_{abc}\, p_{a|b|c} - p_{ab|c}^2 \implies \Pr^{\text{wz}}[u_1 \leftrightarrow u_{10}] < \Pr^{\text{wz}}[u_1 \leftrightarrow u_{10}']

Detailed analysis

Gladkov, Pak and Zimin's robust hyperedge lemma (2024, Lemma 3.2) states that if the five WZ-model probabilities of a hyperedge (or hyperedge-simulating gadget) satisfy the inequality $400\, p_{a|bc} \le p_{abc}\, p_{a|b|c} - p_{ab|c}^2$ — together with the natural symmetry $p_{ab|c} = p_{ac|b}$ inherited from the gadget's construction — then substituting such gadgets for the hyperedges of Hollom's hypergraph $H$ still yields $\Pr^{\text{wz}}[u_1 \leftrightarrow u_{10}] < \Pr^{\text{wz}}[u_1 \leftrightarrow u_{10}']$ , exactly the reversed inequality needed to disprove the bunkbed conjecture.

The right-hand side $p_{abc}\, p_{a|b|c} - p_{ab|c}^2$ is automatically non-negative, a consequence of the Harris–Kleitman inequality applied to this setting (Gladkov 2024), so the lemma really is a robustness statement: it tolerates a controlled but nonzero leak $p_{a|bc} > 0$ , rather than demanding the impossible $p_{a|bc} = 0$ . The proof itself proceeds by a combinatorial involution: configurations of the full percolation process are paired up so that a configuration favouring the 'wrong' connectivity (same level) is matched with a companion favouring the 'right' one (cross level), of at least comparable probability, in a case analysis over how a fixed reference path through the hypergraph interacts with each hyperedge's outcome.

With this lemma in hand, the only remaining task is to exhibit an actual graph gadget whose five probabilities satisfy the required inequality — which is exactly what the next step constructs.

Knowledge used in this step

Events and probability