MathLabs

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

Step 5 of 8: Building a graph gadget GnG_n: a long path plays the role of a hyperedge
In plain words

The gadget Gladkov, Pak, and Zimin actually use is disarmingly simple: Here pp is the edge-closing parameter used for this weighted gadget (at p=1/2p=1/2 it is ordinary bond percolation). a single long path of nn edges connecting the vertex aa to a chain v1,v2,…,vnv_1, v_2, \dots, v_n, together with a direct edge from aa straight to the far end vnv_n. Label b:=v1b := v_1 and c:=vnc := v_n; as nn grows large, the long detour through the chain becomes an extremely unreliable way for aa to reach cc, so almost all the time either the direct edge does the connecting or nothing does — which is exactly the all-or-nothing behaviour a hyperedge needs, with only a vanishingly small chance of the 'wrong' partial connections that a graph gadget cannot fully avoid.

A short calculation with a recurrence relation pins down the exact probability that aa and vnv_n end up connected through this gadget, and shows that for nn large enough, all five of the WZ-model probabilities line up to satisfy the robust hyperedge lemma's inequality.

Pr⁡p(a↔vn)=1−p2n1+pon the path gadget Gn\Pr_p(a \leftrightarrow v_n) = \frac{1 - p^{2n}}{1+p} \quad \text{on the path gadget } G_n
Detailed analysis

For n≥3n \ge 3 and 0<p<10 < p < 1, define the weighted graph GnG_n on n+1n+1 vertices: a path a=v0,v1,…,vna = v_0, v_1, \dots, v_n of nn edges, plus one extra edge directly joining aa to vnv_n; write b:=v1b := v_1 and c:=vnc := v_n as the two 'outer' attachment points (Gladkov, Pak & Zimin 2024, Lemma 4.1). Because GnG_n is a simple weighted graph, ordinary bond percolation applies to it directly, side-stepping the impossibility of Step 3 by not trying to be an exact hyperedge — only an approximate one, for nn large.

A short recurrence computation (2024, §5, Lemma 5.1) shows that, for the complete gadget (including the direct edge) and the edge-closing parameter pp, Pr⁡p(a↔vn)=1−p2n1+p\Pr_p(a \leftrightarrow v_n) = \tfrac{1 - p^{2n}}{1+p}, which is exponentially close to 11+p\tfrac{1}{1+p} for large nn; combined with further exact computations for the remaining WZ-model probabilities of GnG_n (relating pabc,pa∣bc,pab∣c,pac∣b,pa∣b∣cp_{abc}, p_{a|bc}, p_{ab|c}, p_{ac|b}, p_{a|b|c} to pp and nn), the authors verify directly that the robust hyperedge lemma's inequality 400 pa∣bc≤pabc pa∣b∣c−pab∣c2400\, p_{a|bc} \le p_{abc}\, p_{a|b|c} - p_{ab|c}^2 holds once n≥3⋅401+1=1204n \ge 3 \cdot 401 + 1 = 1204 at p=12p = \tfrac12.

At this specific value n=1204n = 1204, the gadget GnG_n has 12051205 vertices and 24072407 edges, is planar, and satisfies exactly the conditions the robust hyperedge lemma of the previous step requires. Six independent copies of this one gadget are all that is needed to replace the six hyperedges of Hollom's hypergraph, which the next step assembles into the final counterexample.

Knowledge used in this step