Các nhà toán học Jacques Verstraete và Sam Mattheus của Đại học California (UC) San Diego đã giải được một bài toán lý thuyết Ramsey khó hiểu mà chưa có nhiều tiến bộ kể từ khi Paul Erdös vĩ đại thực hiện một số đột phá vào năm 1937.
Thật phù hợp, lý thuyết Ramsey khá phức tạp – một nhánh của trò chơi số liên quan đến trật tự trong các cấu trúc, được đặt theo tên của nhà toán học và triết học người Anh Frank P. Ramsey – thường được mô tả trong bối cảnh của một bữa tiệc. Bài toán nổi tiếng nhất trong góc lý thuyết đồ thị của toán học, r(3,3), thường được gọi là định lý về bạn bè và người lạ, giả sử rằng trong một nhóm sáu người, bạn sẽ tìm thấy ít nhất ba người đều biết nhau một hoặc ba người khác đều không biết nhau. Rõ ràng, câu trả lời cho r(3,3) là sáu.
Verstraete nói: “Đó là sự thật của tự nhiên, sự thật tuyệt đối. “Không quan trọng tình huống thế nào hay bạn chọn sáu người nào – bạn sẽ tìm thấy ba người đều biết nhau hoặc ba người không biết nhau. Bạn có thể tìm được nhiều hơn, nhưng bạn là đảm bảo rằng sẽ có ít nhất ba người trong nhóm này hay nhóm kia.”
Khi r(3,3) được tìm thấy, các bộ óc toán học tìm cách trả lời các vấn đề tiếp theo: r(4,4), r(5,5) và r(4,t) trong đó số điểm không được kết nối là khác nhau .
Điều gì đã xảy ra sau khi các nhà toán học phát hiện ra đáp số của r(3,3) là 6? Đương nhiên, họ muốn biết r(4,4), r(5,5) và r(4,t) trong đó số điểm không được kết nối là thay đổi. Erdös và George Szekeres đã tìm thấy câu trả lời cho r(4,4) là 18 vào thế kỷ trước. Trong khi đó, r(5,5) vẫn chưa được biết.
“Nhiều người đã nghĩ tới r(4,t) – nó là một bài toán mở trong hơn 90 năm qua,” Verstraete nói. “Nhưng đó không phải là thứ được ưu tiên hàng đầu trong nghiên cứu của tôi. Mọi người đều biết điều đó khó và mọi người đều cố gắng tìm ra nó, vì vậy trừ khi bạn có ý tưởng mới, bạn sẽ không thể đi đến đâu cả.”
Mặc dù về mặt giá trị, nó có vẻ không phải là loại vấn đề phải mất gần 100 năm mới giải quyết được, nhưng trong lý thuyết đồ thị thì vẻ ngoài lại bị đánh lừa. Ví dụ: khi giải r(5,5), nếu bạn biết câu trả lời nằm trong khoảng từ 40 đến 50 và bạn bắt đầu với 45 điểm trên biểu đồ thì sẽ có 10 234 biểu đồ để điều tra.
Verstraete giải thích: “Bởi vì những con số này nổi tiếng là khó tìm nên các nhà toán học tìm kiếm các ước tính”. “Đây là điều mà Sam và tôi đã đạt được trong công việc gần đây của chúng tôi. ‘Làm thế nào chúng tôi không tìm thấy câu trả lời chính xác mà tìm ra ước tính tốt nhất cho những con số Ramsey này?”
Verstraete lần đầu tiên biết đến r(4,t) trong Erdös trên Đồ thị: Di sản của những vấn đề chưa được giải quyết , được viết bởi các giáo sư Fan Chung của UC San Diego và Ron Graham quá cố. Vấn đề là một phỏng đoán của Erdös, người đã đề nghị 250 đô la Mỹ cho người đầu tiên có thể giải được nó. Chúng tôi tưởng tượng lời đề nghị 250 đô la vào những năm 1930 có thể ‘bổ ích’ hơn so với năm 2023.
Mặc dù Verstraete đã nghĩ đến r(4,t) một thời gian, nhưng phải đến khoảng bốn năm trước, khi đang giải một bài toán khác với một nhà toán học khác, ông mới tạo ra một bước đột phá liên quan đến đồ thị giả ngẫu nhiên sẽ đặt anh ta trên con đường giải quyết câu đố của Ramsey.
Vào năm 2019, Verstraete và nhà toán học đó, Dhruv Mubayi, đã giải được r(3,t), nhưng đó chỉ là những gì họ đạt được. Mãi cho đến khi hợp tác với Mattheus, người có nền tảng về hình học hữu hạn, giấc mơ giải quyết vấn đề tiếp theo mới bắt đầu có vẻ như có thể trở thành hiện thực.
Verstraete nói: “Hóa ra đồ thị giả ngẫu nhiên mà chúng tôi cần có thể được tìm thấy trong hình học hữu hạn”. “Sam là người hoàn hảo để đồng hành và giúp xây dựng những gì chúng tôi cần.”
Vẫn mất gần một năm nhưng giải pháp cho r(4,t) đã được tìm ra: Về cơ bản, để có một bữa tiệc trong đó sẽ luôn có bốn người đều biết nhau hoặc t những người không biết nhau, nó sẽ cần khoảng t 3 người có mặt. (Gần đúng vì nó không chính xác bằng ba.)
Verstraete nói: “Chúng tôi thực sự đã mất nhiều năm để giải quyết. “Và đã có nhiều lúc chúng tôi bế tắc và tự hỏi liệu mình có thể giải quyết được hay không. Nhưng người ta không bao giờ nên bỏ cuộc, dù mất bao lâu đi chăng nữa.”
Các nhà toán học không cho biết liệu r(5,5) hiện có xuất hiện trên bảng trắng hay không vì họ chờ nghiên cứu của mình được bình duyệt và chấp nhận trong thời gian chờ đợi.
Verstraete nói: “Nếu bạn thấy vấn đề khó khăn và bạn đang mắc kẹt, điều đó có nghĩa đó là một vấn đề tốt. Fan Chung nói rằng một vấn đề tốt sẽ chống trả. Bạn không thể mong đợi nó chỉ bộc lộ ra ngoài”.
“Tôi nhận được cuộc gọi từ Fan nói rằng cô ấy nợ tôi 250 USD,” anh nói thêm.
Đáng buồn thay, không có sự điều chỉnh lạm phát nào đối với phí của những người tìm thấy những năm 1930 đó.