Lời giải: Phản ví dụ tường minh của Gladkov–Pak–Zimin bác bỏ giả thuyết giường tầng (2024)

Với một đồ thị liên thông $G = (V, E)$ và một tập con các đỉnh ngang (transversal) được chọn $T \subseteq V$, đồ thị giường tầng $\overline{G}$ gồm hai bản sao $G$ và $G'$ (tầng $0$ và $1$) cùng với một cạnh cột nối $w$ với $w'$ cho mỗi $w \in T$. Trong thấm giường tầng, mỗi cạnh của $G$ và $G'$ được giữ độc lập với xác suất $p \in (0,1)$, còn mọi cột luôn được giữ. Giả thuyết giường tầng năm 1985 của Kasteleyn (Gladkov, Pak & Zimin 2024, Giả thuyết 1.1, gán cho Kasteleyn qua van den Berg & Kesten 2001, Chú thích 5) khẳng định rằng với mọi $G$, $T$, $p$ như vậy, và mọi cặp đỉnh $u, v \in V$, ta có $\Pr^{\text{bb}}_p[u \leftrightarrow v] \ge \Pr^{\text{bb}}_p[u \leftrightarrow v']$ — liên thông tới chính tầng của $v$ có xác suất ít nhất bằng liên thông tới bản sao của $v$ ở tầng khác.

Trường hợp đặc biệt được trích dẫn nhiều nhất lấy $T = V$ (một cột tại mọi đỉnh), nhưng phát biểu tổng quát với tập ngang $T$ tùy ý mới chính là điều Gladkov, Pak và Zimin thực sự giải quyết, và đó là phiên bản mà phản ví dụ của họ bác bỏ. Giả thuyết đã được xác minh trong một số trường hợp đặc biệt — với bánh xe, đồ thị đầy đủ, đồ thị lưỡng phân đầy đủ, đồ thị có tự đẳng cấu hoán đổi $u$ và $v$, và với một hoặc hai đỉnh ngang — và, đáng chú ý, trong giới hạn $p \to 1$, nhưng một chứng minh hay bác bỏ hoàn toàn tổng quát đã lảng tránh các nhà xác suất trong gần suốt bốn thập kỷ kể từ khi nó được đặt ra.

Phần còn lại của chứng minh này dựng một đồ thị tường minh, một tập ngang, và một cặp đỉnh mà bất đẳng thức thất bại tại $p = \tfrac12$, bác bỏ giả thuyết trong trường hợp tổng quát.