Đó là một năm phấn khởi trong nghiên cứu tổ hợp. Đầu năm 2023, giới toán học sửng sốt khi hai trong các vấn đề lớn nhất trong lĩnh vực này đã được giải quyết trong nhiều tháng. Bây giờ, một câu hỏi lớn thứ ba đã giảm xuống với một bằng chứng dài 14 trang “hoàn toàn có tất cả các ý tưởng đúng,” cho biết Mehtaab Sawhney của Viện Công nghệ Massachusetts, người đã nói thêm: “Điều đó hoàn toàn gây sốc.”

Câu hỏi đó liên quan đến cái gọi là số Ramsey - những đại lượng cơ bản phản ánh giới hạn của sự rối loạn có thể xảy ra. Những con số này đo kích thước mà tập hợp các đỉnh và cạnh, được gọi là đồ thị, có thể đạt được trước khi chúng chắc chắn tạo ra mô hình và cấu trúc.

Các nhà toán học đã nghiên cứu các số Ramsey, vốn nổi tiếng là khó xác định, trong gần một thế kỷ. Khi làm như vậy, họ đã phát triển các kỹ thuật dẫn đến những tiến bộ trong nhiều lĩnh vực khác ngoài lý thuyết đồ thị, bao gồm lý thuyết số và mật mã.

Nhưng bằng chứng mới, đăng trực tuyến vào đầu tháng này, đánh dấu sự khởi đầu từ những kỹ thuật đó. Nó không chỉ giải quyết một vấn đề đã cản trở sự tiến bộ trong hơn 40 năm, mà còn đưa ra một lộ trình mới về cách các nhà toán học có thể giải quyết các vấn đề Ramsey trong tương lai.

Lập kế hoạch tổ chức tiệc đáp ứng lý thuyết đồ thị

Để hiểu số Ramsey là gì, hãy tưởng tượng bạn đang tổ chức một bữa tiệc.

Bạn cần mời bao nhiêu người để đảm bảo rằng sẽ có một nhóm người biết nhau hoặc một nhóm hoàn toàn xa lạ? Bạn có thể mã hóa câu hỏi này bằng ngôn ngữ đồ thị. Chỉ định một đỉnh cho mỗi người. Vì n mọi người, bạn nhận được n đỉnh. Kết nối mỗi cặp đỉnh với một cạnh. Tô màu đỏ cho cạnh nếu những người trong câu hỏi biết nhau và tô màu xanh nếu họ là người lạ.

Một nhóm người quen hoặc người lạ được thể hiện bằng một cấu trúc gọi là nhóm: một tập hợp các đỉnh được kết nối bởi các cạnh cùng màu. số Ramsey r(s, t) là số lượng người tối thiểu bạn phải mời để không thể tránh khỏi việc bao gồm một nhóm s người quen hoặc t người lạ - trong ngôn ngữ của lý thuyết đồ thị, một nhóm màu đỏ có kích thước s hoặc một nhóm màu xanh có kích thước t.

Ví dụ, chúng tôi biết rằng r(4, 5) = 25. Vì vậy, bạn có thể tổ chức một bữa tiệc với 24 người, một số người trong số họ biết nhau, không tính nhóm bốn người quen hoặc năm người lạ. Nhưng thêm một người nữa và bạn không thể tránh khỏi việc tạo ra ít nhất một trong những cấu trúc này.

Một trong những bước đột phá đầu năm nay trong tổ hợp đã mang lại giới hạn trên chặt chẽ hơn cho các số Ramsey “đối xứng”, trong đó các cụm màu đỏ và màu xanh lam có cùng kích thước. Với các số Ramsey bất đối xứng — đối tượng của kết quả mới — các nhà toán học ấn định kích thước của cụm màu đỏ và hỏi điều gì xảy ra khi kích thước của cụm màu xanh trở nên lớn tùy ý.

Các nhà toán học chỉ có thể tính toán chính xác một số ít các số Ramsey nhỏ nhất. Họ đã chứng minh rằng r(4, 5) = 25 vào năm 1995. Nhưng không ai biết giá trị của r(4, 6). Tương tự như vậy, vào đầu những năm 1980, họ đã cho thấy việc này r(3, 9) = 36, nhưng r(3, 10) vẫn là một vấn đề mở. (Trường hợp đối xứng cũng khó như vậy: r(4) = 18, nhưng giá trị của r(5) không được biết.)

Và vì vậy, thay vào đó, các nhà toán học cố gắng ước tính các số Ramsey - đưa ra các giới hạn trên và dưới cho các giá trị của chúng.

Vào những năm 1990, họ đã sử dụng các kỹ thuật tạo biểu đồ ngẫu nhiên để chứng minh rằng nếu nhóm màu đỏ cố định ở mức 3 và nhóm màu xanh lam ngày càng lớn hơn, thì kích thước của số Ramsey sẽ tăng lên bằng bình phương kích thước của nhóm màu xanh lam. Nói cách khác, r(3, t) khoảng t².

Bằng chứng mới đặt ra câu hỏi điều gì sẽ xảy ra khi kích thước của nhóm màu đỏ được đặt ở mức 4 thay vì 3. Vào những năm 1930, người ta đã chứng minh rằng r(4, t) phát triển không nhanh hơn xung quanh t³. Nhưng giới hạn dưới tốt nhất, được tìm thấy vào những năm 1970, là khoảng t^5/2 - nhỏ hơn đáng kể.

Nỗ lực thu hẹp khoảng cách bằng cách nâng giới hạn dưới hoặc giảm giới hạn trên đã thất bại trong nhiều thập kỷ, cho đến khi một cặp nhà toán học bổ sung thêm một thành phần quan trọng.

Ẩn trong đồng bằng

Trong 2019, Sam Mattheus, sau đó là một sinh viên tốt nghiệp tại Đại học Tự do Brussels (VUB) đang tìm kiếm nguồn cảm hứng. Chuyên môn của ông là về hình học hữu hạn, nghiên cứu về sự sắp xếp các điểm, đường và các cấu trúc khác trong các không gian được xác định đặc biệt. Nhưng mặc dù anh ấy thấy công việc thú vị, anh ấy cảm thấy bị hạn chế bởi mức độ nghiêm ngặt và chính xác của những cấu trúc hình học này.

Rồi anh thấy một tờ giấy bởi hai nhà toán học, Dhruv Mubayi của Đại học Illinois, Chicago và Jacques Verstraete của Đại học California, San Diego. Họ đang cân nhắc lại cách tiếp cận các vấn đề của Ramsey. Trong khi các kỹ thuật truyền thống liên quan đến việc tạo ra các biểu đồ một cách ngẫu nhiên để có được các ước tính chính xác về các số Ramsey, thì Mubayi và Verstraete đã bắt đầu với các cấu trúc “giả ngẫu nhiên” trông có vẻ ngẫu nhiên, nhưng không phải vậy.

Một cái gì đó nhấp vào Mattheus. Có lẽ, anh ấy nghĩ, quan điểm hình học của anh ấy có thể giúp ích. Trong vài năm tiếp theo, khi hoàn thành công việc tốt nghiệp của mình, anh ấy vẫn giữ ý tưởng này trong đầu. Sau đó, anh ấy đã nộp đơn xin học bổng Fulbright, điều này sẽ cho phép anh ấy theo đuổi nghiên cứu sinh sau tiến sĩ với Verstraete ở Hoa Kỳ

Năm 2022, ngay sau khi Mattheus được trao giải Fulbright (cùng với học bổng khác), anh ấy đã chuyển đến UCSD và bắt đầu làm việc với Verstraete trên r(4,t). Các nhà toán học muốn nâng giới hạn dưới lên để đáp ứng giới hạn trên đã biết. Để làm điều đó, họ sẽ phải tìm một biểu đồ với gần như t³ các đỉnh không có cụm màu đỏ có kích thước 4 hoặc cụm màu xanh lam có kích thước t.

Để có được bằng chứng của họ để làm việc, họ đã định dạng lại vấn đề. Hãy tưởng tượng đơn giản là xóa mọi cạnh màu xanh. Mục tiêu bây giờ là tìm một biểu đồ không có cụm màu đỏ có kích thước 4 và không có bộ kích thước độc lập t (tức là tập hợp t đỉnh không có cạnh).

Công trình năm 2019 của Mubayi và Verstraete ngụ ý rằng nếu bạn có thể xây dựng một biểu đồ giả ngẫu nhiên mà không có các cụm màu đỏ có kích thước 4, thì bạn có thể lấy các phần ngẫu nhiên của nó để có được các biểu đồ nhỏ hơn mà không cần bất kỳ tập hợp độc lập lớn nào. Đây chính là điều mà Mattheus và Verstraete muốn tìm kiếm. Bằng cách bắt đầu với một biểu đồ thậm chí còn lớn hơn, họ hy vọng tìm được một biểu đồ có gần như t³ đỉnh đáp ứng tiêu chí của họ. Verstraete nói: “Bên trong những biểu đồ này ẩn chứa những biểu đồ Ramsey tốt hơn.

Vấn đề là tìm ra cấu trúc giả ngẫu nhiên phù hợp để bắt đầu.

Các nhà toán học đã phải đạt được điều đó bằng một con đường hơi vòng vèo. Họ không bắt đầu với đồ thị giả ngẫu nhiên. Họ đã không bắt đầu với một biểu đồ nào cả.

Thay vào đó, Mattheus nhớ đến một vật thể kỳ lạ gọi là đơn vị Hermiti, thứ mà các nhà hình học hữu hạn có xu hướng rất quen thuộc - nhưng một nhà toán học làm việc trong lĩnh vực tổ hợp dường như chưa từng gặp phải.

Đơn vị Hermiti là một tập hợp đặc biệt các điểm trên một đường cong, cùng với các đường đi qua các điểm đó trong các cấu hình cụ thể. Điều quan trọng là, nó cũng có thể được biểu diễn dưới dạng một biểu đồ bao gồm nhiều nhóm lớn nhưng hầu như không chồng chéo lên nhau.

Đồ thị này nổi tiếng và nhiều tính chất của nó đã được nghiên cứu. Nhưng nó chưa bao giờ được xem xét trong bối cảnh các vấn đề của Ramsey. “Nó rất cụ thể đối với ngành hình học hữu hạn này,” Mattheus nói.

Biểu đồ thoạt nhìn có vẻ không hữu ích vì nó chứa quá nhiều bè phái lớn. Nhưng một tính năng chính của đơn vị Hermiti là nó chỉ chứa các nhóm cỡ 4 có các đỉnh được nhóm lại với nhau theo một cách không điển hình. Do tính chất này, các nhà toán học tương đối dễ dàng phá hủy các nhóm không mong muốn đó bằng cách xóa các cạnh một cách ngẫu nhiên.

Những lần xóa này đã mang lại cho họ một biểu đồ mới không có nhóm kích thước 4 - nhưng nó vẫn chứa các tập hợp độc lập lớn. Bây giờ Mattheus và Verstraete cần chứng minh rằng đồ thị này là giả ngẫu nhiên. Khi làm như vậy, cuối cùng họ đã có thể sử dụng bằng chứng năm 2019 như họ mong muốn. Họ lấy các đồ thị con ngẫu nhiên với khoảng t³ đỉnh và có thể đảm bảo rằng các đồ thị con đó không chứa các tập kích thước độc lập t.

Điều này đã hoàn thành bằng chứng. “Công trình này hoàn toàn đẹp,” Sawhney nói.

Công trình báo trước một sự thay đổi trong cách các nhà toán học nghĩ về các bài toán Ramsey. “Việc cố gắng sử dụng tính ngẫu nhiên để cố gắng vượt qua mọi thứ và đạt được giới hạn tốt nhất có thể là điều rất, rất tự nhiên,” ông nói. David Côn Lôn của Viện Công nghệ California. “Nhưng điều này thực sự cho thấy rằng sự ngẫu nhiên chỉ giúp bạn tiến xa.”