Đến nội dung


Nesbit

Đăng ký: 26-12-2004
Offline Đăng nhập: Hôm nay, 15:42
****-

Chủ đề của tôi gửi

Phạm Tuấn Huy và Jinyoung Park đã giải được Giả thuyết Kahn-Kalai

06-04-2022 - 20:09

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 :D 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  :ohmy: 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
 
 
File gửi kèm  kahn-kalai.png   262.55K   6 Số lần tải
 
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óng đá mùa giải 2021-2022

14-09-2021 - 16:06

Thấy có một số anh em cũng quan tâm đến bóng đá nên tạo topic này để anh em chém gió thư giãn sau những giờ giải toán căng thẳng  :D

Nếu tạo topic từ hè thì chắc là đã sôi động lắm vì mùa chuyển nhượng vừa rồi quá bá đạo, đặc biệt lần lượt cả Messi lẫn Ronaldo thay nhau toả sáng trên thị trường  :oto: Nhưng thôi mùa giải vẫn còn dài và bóng đá luôn có chuyện để chém.

 

Tối nay khai màn Champions League, anh em sẽ xem hay ủng hộ đội nào?

 

Tâm điểm của tối nay chắc chắn là trận đại chiến giữa Barcelona và Bayern Munich. Mình không để ý lắm về chuyển nhượng của Bayern nên không biết chi tiết, nhưng với việc mua một loạt trụ cột của Leipzig thì đã mạnh nay lại càng mạnh (mặc dù đã để Alaba qua Real Madrid). Đặc biệt tiền đạo chủ lực Lewandowski vẫn đang tiếp tục thăng hoa (tay này không phải là tiền đạo mà phải gọi là bá đạo mới đúng, quá khủng khiếp). Ngược lại thì Barcelona lại mất đi cầu thủ hay nhất lịch sử của họ (và cũng là một trong những cầu thủ hay nhất lịch sử bóng đá từ trước tới nay): Lionel Messi. Chưa kể đến sự ra đi của nhiều cầu thủ khác để giảm quỹ lương (như Griezmann chẳng hạn, mặc dù lúc ở đó thì anh cũng khá thọt :P).

 

Barca thì đang trong quá trình vất vả tái thiết lại đội bóng trong khi Bayern thì như hổ mọc thêm cánh, kèo có vẻ khá chênh lệch, nhưng nên nhớ rằng đêm nay trận đấu được diễn ra tại thánh địa Camp Nou có khán giả, một nơi có thể trở thành địa ngục với bất cứ đội bóng nào (lưu ý là hai mùa vừa rồi Barca cũng có thua te tua ở sân nhà vài lần nhưng đó là lúc không có khán giả nhé anh em).

 

Dự đoán: Barcelona 1 - 3 Bayern Munich (Lewandowski lập cú đúp).

 

 

Một trận đấu khác có lẽ cũng nhận được sự chú ý của nhiều người (không kể fan MU :P) là Young Boys vs Manchester United. Trận này hấp dẫn ở sự trở lại của ông vua Champions League: Cristiano Ronaldo. Mặc dù đã toả sáng rực rỡ trong ngày ra mắt lần thứ hai ở MU với việc lập cú đúp ở những thời điểm quan trọng, Ronaldo cần toả sáng ở Champions League để khẳng định vị thế của mình ở đấu trường này và chứng tỏ cho thế giới biết rằng thất bại của Juventus ở ba mùa CL vừa rồi chỉ là... tai nạn.

 

Dự đoán: Young Boys 1 - 3 Manchester United (Ronaldo ghi 1 bàn, rời sân phút 70).