Giả thuyết giường tầng (bunkbed)

Cho $G = (V, E)$ là một đồ thị hữu hạn, và gọi đồ thị giường tầng của nó là tích Descartes $G \,\square\, K_2$ gồm hai bản sao giống hệt $G_0, G_1$ của $G$ nối với nhau bởi các cạnh dọc $(v, 0)(v, 1)$ tại các đỉnh $v \in T \subseteq V$. Dưới quá trình thấm cạnh độc lập trên $G_0$ và $G_1$ với xác suất giữ cạnh $p \in (0, 1)$, giả thuyết khẳng định rằng với mọi $u, v \in V$, xác suất $(u, 0)$ liên thông với $(v, 0)$ ở cùng tầng luôn lớn hơn hoặc bằng xác suất $(u, 0)$ liên thông với $(v, 1)$ ở tầng đối diện.

Tháng 10 năm 2024, Nikita Gladkov, Igor Pak và Aleksandr Zimin bác bỏ giả thuyết giường tầng (`arXiv:2410.02545`, xuất bản trên PNAS năm 2025) bằng cách xây dựng tường minh một đồ thị phẳng phản ví dụ gồm $7,222$ đỉnh và $14,442$ cạnh, dựa trên phản ví dụ cho thấm siêu đồ thị năm 2024 của Lawrence Hollom (`arXiv:2406.01790`). Chứng minh của họ hoàn toàn bằng giải tích mà không cần vét cạn bằng máy tính.