Mấy hôm trước thấy trên Twitter xôn xao về việc "Jinyoung Park và Huy Pham đã giải được Giả thuyết Kahn-Kalai", một kết quả rất quan trọng trong ngành Tổ hợp và Topo (chính xác hơn là trong mảng Random Graph - Đồ thị Ngẫu nhiên). Mình thì không quá rành về lĩnh vực này, nhưng thấy có tên Việt Nam nên tò mò thử đọc thêm xem kết quả thế nào và xem Huy Pham là ai cho biết Tuy không hiểu nhiều nhưng biết được rằng kết quả này đúng là một bước đột phá trong ngành, và Huy Pham chính là em Phạm Tuấn Huy, người từng giành được hai HCV IMO các năm 2013 và 2014 (nghĩa là tận 10 năm từ khi người trước đó là anh Lê Hùng Việt Bảo đạt được thành tích này; liên tiếp ngay sau Huy thì còn có thêm hai em cũng lặp lại được thành tích).
Bài báo được đăng trên arXiv: https://arxiv.org/abs/2203.17207.
Do thời gian không cho phép nên xin mượn tạm bài viết bằng tiếng anh bên dưới của Gil Kalai (đồng tác giả của giả thuyết Kahn-Kalai) để cung cấp thêm thông tin và bối cảnh cũng như các chi tiết kỹ thuật liên quan. Diễn đàn có Nxb và các anh em khác hiểu biết hơn mình nhiều, hi vọng có thể tham gia bình luận và cung cấp thêm thông tin.
Huy hiện đang làm PhD Toán ở Stanford: https://web.stanford.edu/~huypham. Ngoài hai HCV IMO thì thành tích học đại học và nghiên cứu của em ấy cũng ấn tượng không kém (thấy có làm cả về Deep Learning với một bài Oral ở ICLR). Đồng tác giả Jinyoung Park cũng có profile rất thú vị: từ giáo viên dạy Toán cấp 2 rồi qua Mỹ làm PhD và hiện tại đang làm postdoc ở Stanford.
Xin chúc mừng hai tác giả!
Amazing: Jinyoung Park and Huy Tuan Pham settled the expectation threshold conjecture!
Posted on April 2, 2022 by Gil Kalai
A brief summary: In the paper, A proof of the Kahn-Kalai conjecture, Jinyoung Park and Huy Tuan Pham proved the 2006 expectation threshold conjecture posed by Jeff Kahn and me. The proof is wonderful. Congratulations Jinyoung and Huy Tuan!
The 2006 expectation threshold conjecture gives a justification for a naive way to estimate the threshold probability of a random graph property. Suppose that you are asked about the critical probability for a random graph in G(n,p) for having a perfect matching (or a Hamiltonian cycle). You compute the expected number of perfect matchings and realize that when p is C/n this expected number equals 1/2. (For Hamiltonian cycles it will be C’/n.) Of course, if the expectation is one half, the probability for a perfect matching can still be very low; indeed, in this case, an isolated vertex is quite likely but when there is no isolated vertices the expected number of perfect matchings is rather large. Our 2006 conjecture boldly asserts that the gap between the value given by such a naive computation and the true threshold value is at most logarithmic in the number of vertices. Jeff and I tried hard to find a counterexample but instead we managed to find more general and stronger forms of the conjecture that we could not disprove.
Two years ago Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park proved a weak form of the conjecture which was proposed in a 2010 paper by Michel Talagrand. (See this post.) Indeed, the expectation threshold conjecture had some connections with a 1995 paper of Michel Talagrand entitled Are all sets of positive measure essentially convex? In a 2010 STOC paper Are Many Small Sets Explicitly Small? Michel formulated a whole array of interesting conjectures and commented that he feels that these conjectures are related to the expectation threshold conjecture to which he offered a weaker fractional version. This weak version suffices for various applications of the original conjecture. Keith, Jeff, Bhargav, and Jinyoung’s work built on the breakthrough work of Alweiss, Lovett, Wu and Zhang on the Erdős-Rado ‘sunflower’ conjecture.
Proving the full expectation threshold conjecture looked like a difficult task. The only path that people saw was to try to relate Talagrand’s fractional expectation threshold with our expectation threshold. (Indeed Talagrand also conjectured that they only differ by a multiplicative constant factor. This looked if true very difficult to prove.) However this is not the path taken by Jinyoung Park and Huy Tuan Pham and they found a direct simple argument! Jinyoung and Huy Tuan also used their method to settle one of the central conjectures (Conj 5.7) from Talagrand’s paper and this will be presented in a forthcoming paper.
The logn gap in our conjecture looked rather narrow but now that it was proved we can ask for conditions that will guarantee a smaller gap. For example, when is the gap only a constant?
Here is a nice IAS video on Jinyoung Park’s path to math.
Here is a lecture by Michel Talagrand.
Bài viết đã được chỉnh sửa nội dung bởi Nesbit: 07-04-2022 - 16:02
Update link arXiv