Bunkbed conjecture
The bunkbed conjecture (also spelled bunk bed conjecture) is a statement in percolation theory, a branch of mathematics that studies the behavior of connected clusters in a random graph. The conjecture is named after its analogy to a bunk bed structure. It was first posited by Pieter Kasteleyn in 1985.[1] In 2024, Nikita Gladkov, Igor Pak, and Alexander Zimin gave a counter-example to the bunkbed conjecture, proving that it is false.[2][3][4]
Description
[edit]The conjecture has many equivalent formulations.[5] In the most general formulation it involves two identical graphs, referred to as the upper bunk and the lower bunk. These graphs are isomorphic, meaning they share the same structure. Additional edges, termed posts, are added to connect each vertex in the upper bunk with the corresponding vertex in the lower bunk.
Each edge in the graph is assigned a probability. The edges in the upper bunk and their corresponding edges in the lower bunk share the same probability. The probabilities assigned to the posts can be arbitrary.
A random subgraph of the bunkbed graph is then formed by independently deleting each edge based on the assigned probability.
Equivalently, it can be assumed that all edges have the same deletion probability .[5]
The bunkbed conjecture states that in the resulting random subgraph, the probability that a vertex x in the upper bunk is connected to some vertex y in the upper bunk is greater than or equal to the probability that x is connected to y′, the isomorphic copy of y in the lower bunk.
Interpretation and significance
[edit]The conjecture suggests that two vertices of a graph are more likely to remain connected after randomly removing some edges if the graph distance between the vertices is smaller. This is intuitive, and similar questions for random walks and Ising model were resolved positively.[6][7] The original motivation for the conjecture was its implication that, in a percolation on the infinite square grid, the probability of (0, 0) being connected to (x, y) for x, y ≥ 0 is greater than the probability of (0, 0) being connected to (x + 1, y).[6]
It was proved for specific types of graphs, such as wheels,[8] complete graphs,[9] complete bipartite graphs, and graphs with a local symmetry.[10] It was also proved in the limit p → 1 for any graph.[11][12]
Counterexamples for generalizations of the bunkbed conjecture have been published for site percolation, hypergraphs, and directed graphs.[13] The original disproof is based on a small counterexample in the 3-uniform hypergraph case with 10 vertices; the counterexample for the standard bunkbed conjecture with all edge probabilities equal to 1/2 (equivalent to the general case) has a planar bunk with 7222 vertices and 14442 edges, and where there is an x and y where connecting x to y′ is more probable by around . They also show that there is a counterexample in the general case with 28 vertices and 54 edges on the bunk and an x and y where difference in probabilities of around in favor of x to y′.[2][3]
References
[edit]- ↑ van den Berg, Jacob; Kahn, Jeff (2001). "A correlation inequality for connection events in percolation". Annals of Probability. 29 (1): 123–126. doi:10.1214/aop/1008956324. JSTOR 2652916.
- 1 2 3 Nikita Gladkov; Igor Pak; Aleksandr Zimin (2025). "The bunkbed conjecture is false". Proceedings of the National Academy of Sciences. 122 (24) e2420725122. arXiv:2410.02545. Bibcode:2025PNAS..12220725G. doi:10.1073/pnas.2420725122.
- 1 2 Gladkov, Nikita; Pak, Igor; Zimin, Aleksandr (2025). "The bunkbed conjecture is false". Proceedings of the National Academy of Sciences of the United States of America. 122 (24) e2420725122. Bibcode:2025PNAS..12220725G. doi:10.1073/pnas.2420725122. PMC 12184427. PMID 40512791.
- ↑ Howlett, Joseph (2024-11-01). "Math's 'Bunkbed Conjecture' Has Been Debunked". Quanta Magazine. Retrieved 2024-11-02.
- 1 2 Rudzinski, James; Smyth, Clifford (2016). "Equivalent Formulations of the Bunk Bed Conjecture". North Carolina Journal of Mathematics and Statistics. 2: 23–28. Retrieved December 17, 2023.
- 1 2 Häggström, Olle (1998). "On a conjecture of Bollobás and Brightwell concerning random walks on product graphs". Combinatorics, Probability and Computing. 7 (4): 397–401. doi:10.1017/S0963548398003605.
- ↑ Häggström, Olle (2003). "Probability on bunkbed graphs". Proceedings of FPSAC. 3: 19–27.
- ↑ Leander, Madeleine (2009). "On the bunkbed conjecture" (PDF). Självständiga arbeten i matematik. Retrieved December 17, 2023.
- ↑ van Hintum, Peter; Lammers, Piet (2018). "The bunkbed conjecture on the complete graph". European Journal of Combinatorics. 76: 175–177. arXiv:1803.07647. doi:10.1016/j.ejc.2018.10.002.
- ↑ Richthammer, Thomas (2022). "Bunkbed conjecture for complete bipartite graphs and related classes of graphs". arXiv:2204.12931 [math.PR].
- ↑ Hutchcroft, Tom; Kent, Alexander; Nizić-Nikolac, Petar (2023). "The bunkbed conjecture holds in the p↑1 limit" (PDF). Combinatorics, Probability and Computing. 32 (3). Cambridge University Press: 363–369. doi:10.1017/S096354832200027X. S2CID 263889353.
- ↑ Hollom, Lawrence (2023). "A new proof of the bunkbed conjecture in the p↑1 limit". arXiv:2302.00031 [math.CO].
- 1 2 Hollom, Lawrence (2024-06-03). "The bunkbed conjecture is not robust to generalisation". arXiv:2406.01790 [math.CO].