Giả thuyết Kahn–Kalai

Giả thuyết Kahn–Kalai, hay còn gọi là giả thuyết ngưỡng kì vọng, là một giả thuyết trong nhánh lý thuyết đồ thị và cơ học thống kê, được đề xuất bởi Jeff Kahn và Gil Kalai trong 2006.^[1][2]

Nội dung

Giả thuyết quan tâm tới bài toán ước lượng tổng quát khi xảy ra chuyển pha trong các hệ thống.^[1] Ví dụ chẳng hạn, cho mạng ngẫu nhiên có ${\displaystyle N}$ nút, trong đó mỗi cạnh sẽ được thêm vào với xác suất ${\displaystyle p}$, ít có khả năng đồ thị đó sẽ có chu trình Hamilton nếu ${\displaystyle p}$ nhỏ hơn giá trị ngưỡng ${\displaystyle (\log N)/N}$, nhưng sẽ có khả năng cao khi giá trị ${\displaystyle p}$ lớn hơn giá trị ngưỡng.^[3]

Các giá trị ngưỡng thường rất khó để mà tính, song cận dưới cho giá trị ngưỡng (hay gọi là "ngưỡng kì vọng") thì thường dễ tính hơn.^[1] Giả thuyết Kahn–Kalai nói rằng hai giá trị trên gần với nhau theo cách được định nghĩa như sau: tồn tại hằng số phổ dụng ${\displaystyle K}$ sao cho tỷ lệ giữa hai cái nhỏ hơn ${\displaystyle K\log \ell ({\mathcal {F}})}$ trong đó ${\displaystyle \ell ({\mathcal {F}})}$ là kích thước của phần tử tối tiểu lớn nhất của họ tăng dần ${\displaystyle {\mathcal {F}}}$ của các tập con của tập luỹ thừa.^[4]

Chứng minh

Trong 2022, Jinyoung Park và Phạm Tuấn Huy xuất bản bản in trước đề xuất một bài chứng minh cho giả thuyết này.^[3][4] Bài chứng minh đã được khen ngợi cho tính thanh lịch và súc tích của nó.^[5]

Tham khảo

1. ^ “Jinyoung Park and Huy Tuan Pham Prove the Kahn-Kalai Conjecture - IAS News”. Institute for Advanced Study (bằng tiếng Anh). 18 tháng 4 năm 2022. Truy cập ngày 25 tháng 4 năm 2022.
2. Kahn, Jeff; Kalai, Gil (2006-04-02). "Thresholds and expectation thresholds". arΧiv:math/0603218. 
3. ^ Cepelewicz, Jordana (25 tháng 4 năm 2022). “Elegant Six-Page Proof Reveals the Emergence of Random Structure”. Quanta Magazine (bằng tiếng Anh). Truy cập ngày 25 tháng 4 năm 2022.
4. ^ Park, Jinyoung; Pham, Huy Tuan (2022-03-31). "A Proof of the Kahn-Kalai Conjecture". arΧiv:2203.17207 [math.CO]. 
5. “Ex-middle school math teacher from Korea solves discrete math puzzle - Pulse by Maeil Business News Korea”. pulsenews.co.kr (bằng tiếng Hàn). Truy cập ngày 27 tháng 4 năm 2022.

Xem thêm

• Đồ thị ngẫu nhiên