On Kasteleyn's bunkbed conjecture in some classes of graphs

• Thesis title in Czech: Kasteleynova Dvoupatrová domněnka v některých třídách grafů
• Thesis title in English: On Kasteleyn's bunkbed conjecture in some classes of graphs
• Key words: Perkolace|náhodné grafy|diskrétní pravděpodobnost
• English key words: Percolation|random graphs|discrete probability
• Academic year of topic announcement: 2024/2025
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: doc. Mykhaylo Tyomkyn, Ph.D.
• Author: Bc. Daniela Lněničková - assigned and confirmed by the Study Dept.
• Date of registration: 22.12.2024
• Date of assignment: 24.12.2024
• Confirmed by Study dept. on: 26.12.2024
• Date of electronic submission: 17.07.2025

Guidelines

Kasteleyn's bunkbed conjecture from 1985 states that in any finite graph G, for any two vertices v and w, in the binomial random graph model on GxZ_2 (the edges being the two copies of G plus the `vertical' edges between (u,0) and (u,1)) the probability that (v,0) and (w,0) are connected by a path, is at least the corresponding probability for (v,0) and (w,1). While the conjecture has been disproved in 2024, by a tailor-made counterexample on 7222 vertices, the conjecture is known to hold in a number of natural classes of graphs (complete and complete bipartite graphs, trees, cycles). This project aims to investigate the conjecture in further classes of graphs and directed graphs.

References

B. Bollobas and O. Riordan. Percolation. Cambridge Univ. Press, New York, 2006, 323 pp

N. Gladkov, I. Pak and A. Zimin. The bunkbed conjecture is false. Preprint (2024) arXiv:2410.02545

P. van Hintum and P. Lammers. The bunkbed conjecture on the complete graph, European J. Combin. 76 (2019), 175–177

L. Hollom. A new proof of the bunkbed conjecture in the p ↑ 1 limit, Discrete Math. 347 (2024), no. 1, Paper No. 113711, 6 pp