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$ nút, trong đó mỗi cạnh sẽ được thêm vào với xác suất $p$, ít có khả năng đồ thị đó sẽ có chu trình Hamilton nếu $p$ nhỏ hơn giá trị ngưỡng $(\log N)/N$, nhưng sẽ có khả năng cao khi giá trị $p$ 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 $K$ sao cho tỷ lệ giữa hai cái nhỏ hơn $K\log \ell ({\mathcal {F}})$ trong đó $\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 ${\mathcal {F}}$ 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ó.

Xem thêm

• Đồ thị ngẫu nhiên