Gần thế kỷ tìm lời giải cho bài toán của Ramsey

Chúng ta đã từng cùng chứng kiến: khởi đầu một thử nghiệm toán học với một bài toán dường như không thể giải nổi. Điều gì sẽ xảy ra nếu phát hiện ra lời giải cho một bài toán tồn tại gần như cả thế kỷ? Với các nhà toán học đã biết lý thuyết Ramsey thì đây là một trong những trường hợp điển hình. Trên thực tế, có rất ít nỗ lực thực hiện để giải bài toán Ramsey, kể từ những năm 1930.

Giờ đây, các nhà nghiên cứu trường đại học California San Diego Jacques Verstraete và Sam Mattheus đã tìm ra câu trả lời cho r(4,t), một bài toán Ramsey tồn tại đã lâu và khiến cả thế giới toán học phải lúng túng hàng thập kỷ ¹.

Bài toán của Ramsey là gì?

Theo cách diễn giải toán học, một đồ thị là một tập hợp các điểm và các đường nối giữa các điểm đó. Lý thuyết Ramsey đề xuất nếu đồ thị đó đủ lớn, bạn sẽ có thể tìm ra một số bậc bên trong đó – cả một tập hợp điểm không đường nối giữa chúng hay một tập hợp điểm với mọi đường nối có thể giữa chúng (các tập hợp này được gọi là ‘bọn/bè lũ’). Điều này được thể hiện như r(s,t), nơi s là các điểm với các đường và t là điểm không đường.

Với những người không thạo lý thuyết đồ thị, bài toán nổi tiếng bậc nhất của Ramsey, r(3,3), thi thoảng được gọi là “lý thuyết về những người bạn và những kẻ lạ mặt” và được giải thích dưới dạng một bữa tiệc: trong một nhóm có sáu người, bạn sẽ tìm ra ít nhất ba người biết rõ từng người khác hoặc ba người không biết tất cả những người khác. Câu trả lời cho bài toán r(3,3) là sáu.

“Đó là thực tế của tự nhiên, một sự thật thuần túy”, Verstraete diễn giải. “Không phụ thuộc vào tình huống là gì và sáu người nào bạn chọn – bạn sẽ tìm thấy ba người biết rõ tất cả từng người khác hoặc ba người không hề biết gì về từng người khác. Bạn có thể tìm nhiều người hơn nhưng bạn đảm bảo có ít nhất ba người thuộc hội nhóm này hay hội nhóm khác”.

Điều gì xảy ra sau khi các nhà toán học tìm thấy là r(3,3) = 6? Thật tự nhiên, họ muốn biết r(4,4), r(5,5), và r(4,t), nơi số các điểm không kết nối có sự biến động. Lời giải cho r(4,4) là 18 và được chứng minh bằng việc sử dụng một lý thuyết do Paul Erdös và George Szekeres sáng tạo vào những năm 1930.

Hiện tại vẫn còn chưa xác định lời giải cho r(5,5).

Một bài toán xứng để chiến đấu

Tại sao những gì dường như đơn giản lại quá khó để giải? Hóa ra là bài toán luôn phức tạp hơn vẻ bên ngoài của nó. Cứ tạm cho là anh biết rõ lời giải của bài toán r(5,5) là một con số nằm giữa khoảng 40–50. Nếu bắt đầu với 45 điểm, sẽ có khoảng hơn 10234 đồ thị để xem xét.

“Do những con số này quá khó để tìm ra, các nhà toán học tìm kiếm những ước tính”, Verstraete giải thích. “Đó là những gì mà tôi và Sam đã đạt được trong công trình nghiên cứu gần đây của chúng tôi. Làm thế nào chúng tôi không thể tìm ra nổi câu trả lời chính xác mà chỉ có những ước tính tốt nhất về những con số của Ramsey?”.

Các sinh viên toán học các bài toán Ramsey từ rất sớm, vì vậy r(4,t) đã được Verstraete quan tâm khi bắt đầu sự nghiệp nghiên cứu. Trên thực tế, đầu tiên ông thấy bài toán này trong cuốn “Erdös on Graphs: His Legacy of Unsolved Problems” (Erdös về các đồ thị: di sản của những bài toán chưa giải của ông) do hai giáo sư UC San Diego professors là Fan Chung và sau là Ron Graham viết. Bài toán này là một giả thuyết từ Erdös, người đề xuất trao 250 USD cho người đầu tiên giải được bài toán này.

“Nhiều người nghĩ về r(4,t) – đó là một bài toán mở trong vòng 90 năm”, Verstraete nói. “Nhưng đây không phải là ưu tiên của tôi. Mọi người đều biết nó khó và mọi người cũng cố gắng giải nó, vì vậy trừ phi bạn có ý tưởng mới chứ đâm đầu vào đó bạn chẳng biết nó sẽ dẫn mình tới đâu đâu”.

Sau đó 40 năm, Verstraete bắt đầu nghiên cứu một bài toán Ramsey khác với một nhà toán học tại ĐH Illinois-Chicago là Dhruv Mubayi. Cùng với nhau, họ đã khám phá ra đồ thị giả ngẫu nhiên có thể thúc đẩy hiểu biết hiện tại về những bài toán cũ đó.

Vào năm 1937, Erdös đã khám phá ra là sử dụng các đồ thị ngẫu nhiên có thể đem đến những cận dưới tốt cho các bài toán Ramsey. Những gì Verstraete và Mubayi khám phá ra là mẫu từ các đồ thị giả ngẫu nhiên thường đem đến những cận tốt hơn cho các con số Ramsey hơn các đồ thị ngẫu nhiên. Các cận đó – những giới hạn trên và dưới cho câu trả lời có thể – đã giới hạn phạm vi ước tính mà họ có thể làm. Nói theo cách khác, họ đã tiến gần hơn tới sự thật.

Vào năm 2019, Verstraete và Mubayi đã dùng các đồ thị giả ngẫu nhiên để giải bài toán r(3,t). Tuy nhiên Verstraete phải vật lộn để xây dựng một đồ thị giả ngẫu nhiên để có thể giúp giải được r(4,t).

Ông bắt đầu nghiên cứu những lĩnh vực khác nhau của toán học bên ngoài toán tổ hợp, bao gồm hình học hữu hạn, đại số và xác suất. Cuối cùng ông hợp lựccùng với Mattheus, một postdoct trong nhóm nghiên cứu của mình và có nền tảng về hình học hữu hạn.

“Hóa ra là có thể tìm thấy đồ thị giả ngẫu nhiên mà chúng tôi cần trong hình học hữu hạn”, Verstraete nói. “Sam là một người hoàn hảo để đi cùng tôi và giúp xây dựng những gì chúng tôi cần”.

Tuy đã có đồ thị giả ngẫu nhiên, họ vẫn phải giải được vô số miếng ghép khác của toán học. Mất gần một năm để làm điều đó nhưng cuối cùng họ nhận ra là mình có một lời giải: r(4,t) gần với một hàm bậc ba của t. Nếu bạn muốn một bữa tiệc nơi sẽ luôn luôn có bốn người biết rõ từng người hay t người không biết tí gì về nhau, bạn cần sự hiện diện của khoảng t3 người. Có một dấu sao nhỏ bởi vì hãy nhớ là đó chỉ là một ước tính và không phải là câu trả lời chính xác. Nhưng t3 đã rất gần với một câu trả lời chính xác.

Phát hiện này đã được tạp chí Annals of Mathematics bình duyệt. Và một bản ở dạng tiền ấn phẩm được đưa lên trang arXiv ².

“Chúng tôi thực sự mất nhiều năm để giải nó”, Verstraete nói. “Và nhiều lúc chúng tôi bế tắc và tự hỏi là liệu chúng tôi có thể giải quyết được bài toán không. Nhưng đúng là không nên bỏ cuộc, dù mất nhiều thời gian đi chăng nữa”.

Verstraete nhấn mạnh vào tầm quan trọng của sự kiên nhẫn – điều mà ông vẫn thường nhắc nhở với học trò của mình. “Nếu anh tìm thấy bài toán này quá khó và anh bế tắc thì điều đó có nghĩa là đây là bài toán tốt. Fan Chung đã từng nói một bài toán tốt xứng đáng để anh dành sức chiến đấu. Anh không nên chờ đợi bài toán tự bộc lộ bí mật của chính mình với anh”.

Verstraete biết là nỗ lực được đền đáp xứng đáng “tôi đã nhận được một cuộc gọi từ Fan nói rằng cô ấy sẽ đưa cho tôi 250 USD”.

Tô Vân tổng hợp

Nguồn: https://phys.org/news/2023-10-math-problem-century.html

https://today.ucsd.edu/story/ramsey-problems

————————————–

1. https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics

2.https://arxiv.org/abs/2306.04007