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.

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. Ví dụ chẳng hạn, cho mạng ngẫu nhiên có  nút, trong đó mỗi cạnh sẽ được thêm vào với xác suất , ít có khả năng đồ thị đó sẽ có chu trình Hamilton nếu  nhỏ hơn giá trị ngưỡng , nhưng sẽ có khả năng cao khi giá trị  lớn hơn giá trị ngưỡng.

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. 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  sao cho tỷ lệ giữa hai cái nhỏ hơn  trong đó  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  của các tập con của tập luỹ thừa.

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. Bài chứng minh đã được khen ngợi cho tính thanh lịch và súc tích của nó.

Tham khảo

Xem thêm 
 Đồ thị ngẫu nhiên

Toán học thập niên 2000
Toán học thập niên 2020
Lý thuyết đồ thị
Cơ học thống kê