Trong 1850, Thomas Penyngton Kirkman, một nhà toán học khi anh ta không hoàn thành trách nhiệm chính của mình với tư cách là một cha sở tại Nhà thờ Anh Quốc, đã mô tả “vấn đề nữ sinh” của mình: “Mười lăm cô gái trẻ trong một trường học đi ra ngoài ba lần trong bảy ngày liên tiếp: cần phải sắp xếp họ hàng ngày, để không có hai người sẽ đi bộ hai lần cùng nhau. "
Đối với một nhà toán học hiện đại, loại bài toán này được hình dung tốt nhất như một siêu đồ thị - một tập hợp các nút được thu thập theo nhóm từ ba trở lên. 15 nữ sinh là các nút, và mỗi nhóm “ba cạnh” có thể được coi là một hình tam giác, với ba đường thẳng hoặc các cạnh, nối ba nút.
Bài toán của Kirkman về cơ bản hỏi liệu có sự sắp xếp các hình tam giác này kết nối tất cả các nữ sinh với nhau hay không, nhưng với một hạn chế bổ sung là không có hai hình tam giác nào có chung một cạnh. Edge-sharing ngụ ý rằng hai nữ sinh phải đi cùng nhau nhiều hơn một lần. Hạn chế này có nghĩa là mỗi cô gái đi với hai người bạn mới mỗi ngày trong một tuần, để mỗi cặp có thể gặp nhau đúng một lần.
Vấn đề này và những vấn đề khác tương tự như nó đã làm điên đảo các nhà toán học trong gần hai thế kỷ kể từ khi Kirkman đưa ra câu hỏi của mình. Năm 1973, nhà toán học huyền thoại Paul Erdős cũng đặt ra một điều tương tự. Anh ấy hỏi liệu có thể xây dựng một siêu đồ thị với hai đặc tính dường như không tương thích hay không. Đầu tiên, mỗi cặp nút phải được nối với nhau bằng chính xác một hình tam giác, như với các nữ sinh. Tính chất này làm cho đồ thị có hình tam giác dày đặc. Yêu cầu thứ hai buộc các tam giác phải được trải ra một cách rất chính xác. (Cụ thể, nó yêu cầu rằng đối với bất kỳ nhóm nhỏ hình tam giác nào, có ít nhất ba nút nhiều hơn số hình tam giác.) “Bạn có hành vi hơi mâu thuẫn này khi bạn có một đối tượng tổng thể dày đặc không có phần dày đặc,” David Côn Lôn, một nhà toán học tại Viện Công nghệ California.
Tháng Giêng này, trong một bằng chứng phức tạp dài 50 trang, bốn nhà toán học đã chứng minh rằng luôn có thể xây dựng một siêu đồ thị như vậy miễn là bạn có đủ các nút. “Số lượng kỹ thuật mà [họ] đã trải qua, chỉ để có được điều này, thật đáng kinh ngạc,” nói Allan Lộ, một nhà toán học tại Đại học Birmingham. Conlon đồng tình: "Đó là một tác phẩm thực sự ấn tượng."
Nhóm nghiên cứu đã xây dựng một hệ thống đáp ứng các yêu cầu quỷ quái của Erdős bằng cách bắt đầu với một quy trình ngẫu nhiên để chọn các hình tam giác và thiết kế nó một cách cực kỳ cẩn thận để phù hợp với nhu cầu của họ. Conlon nói: “Số lượng các sửa đổi khó đi vào bằng chứng thực sự rất đáng kinh ngạc.
Chiến lược của họ là cẩn thận xây dựng siêu đồ thị từ các hình tam giác riêng lẻ. Ví dụ, hãy tưởng tượng 15 nữ sinh của chúng ta. Vẽ một đường thẳng giữa mỗi cặp.
Mục đích ở đây là tìm ra các tam giác nằm trên các đường thẳng này sao cho các tam giác đó thỏa mãn hai yêu cầu: Thứ nhất, không có hai tam giác nào có chung một cạnh. (Các hệ thống đáp ứng yêu cầu này được gọi là hệ thống ba Steiner.) Và thứ hai, đảm bảo rằng mọi tập hợp con tam giác nhỏ đều sử dụng một số lượng nút đủ lớn.
Cách các nhà nghiên cứu đã làm điều này có lẽ được hiểu rõ nhất với một phép loại suy.
Nói rằng thay vì tạo hình tam giác từ các cạnh, bạn đang xây nhà từ những viên gạch Lego. Một số tòa nhà đầu tiên bạn làm rất xa hoa, với kết cấu gia cố và trang trí phức tạp. Khi bạn đã hoàn thành những việc này, hãy đặt chúng sang một bên. Chúng sẽ đóng vai trò như một “chất hấp thụ” - một loại kho dự trữ có cấu trúc.
Bây giờ hãy bắt đầu tạo các tòa nhà từ những viên gạch còn lại của bạn, tiếp tục mà không cần lên kế hoạch nhiều. Khi nguồn cung cấp Legos của bạn cạn kiệt, bạn có thể thấy mình đang gặp một số viên gạch lạc chỗ hoặc những ngôi nhà không chắc chắn về mặt cấu trúc. Nhưng vì các tòa nhà hấp thụ quá cũ và được gia cố, bạn có thể nhổ một số viên gạch ở đây và ở đó và sử dụng chúng mà không gây ra thảm họa.
Trong trường hợp của hệ thống ba Steiner, bạn đang cố gắng tạo ra các hình tam giác. Trong trường hợp này, bộ hấp thụ của bạn là một bộ sưu tập các cạnh được lựa chọn cẩn thận. Nếu bạn thấy mình không thể sắp xếp phần còn lại của hệ thống thành hình tam giác, bạn có thể sử dụng một số cạnh dẫn vào bộ hấp thụ. Sau đó, khi bạn làm xong việc đó, bạn chia nhỏ bộ hấp thụ thành các hình tam giác.
Sự hấp thụ không phải lúc nào cũng hoạt động. Nhưng các nhà toán học đã mày mò quá trình này, tìm ra những cách mới để xoay quanh các chướng ngại vật. Ví dụ, một biến thể mạnh mẽ được gọi là hấp thụ lặp lại chia các cạnh thành một chuỗi các tập hợp lồng nhau, để mỗi cạnh hoạt động như một bộ hấp thụ cho phần lớn nhất tiếp theo.
Conlon nói: “Trong hơn một thập kỷ qua, đã có những cải tiến lớn. “Đó là một thứ gì đó của một loại hình nghệ thuật, nhưng họ đã thực sự nâng nó lên tầm nghệ thuật cao vào thời điểm này.”
Vấn đề của Erdős rất phức tạp ngay cả với sự hấp thụ lặp đi lặp lại. “Rất nhanh chóng đã trở nên rõ ràng tại sao vấn đề này vẫn chưa được giải quyết,” nói Mehtaab Sawhney, một trong bốn nhà nghiên cứu đã giải quyết nó, cùng với Ashwin Sah, người cùng với Sawhney là nghiên cứu sinh tại Học viện Công nghệ Massachusetts; Michael Simkin, một nghiên cứu sinh sau tiến sĩ tại Trung tâm Khoa học Toán học và Ứng dụng tại Đại học Harvard; và Matthew Kwan, một nhà toán học tại Viện Khoa học và Công nghệ Áo. "Có những nhiệm vụ kỹ thuật khá thú vị, khá khó khăn."
Ví dụ, trong các ứng dụng khác của hấp thụ lặp đi lặp lại, khi bạn hoàn thành việc bao phủ một tập hợp - hoặc với hình tam giác, đối với hệ thống ba Steiner hoặc với các cấu trúc khác cho các vấn đề khác - bạn có thể xem xét nó đã được xử lý và quên nó đi. Tuy nhiên, các điều kiện của Erdős đã ngăn cản bốn nhà toán học làm điều đó. Một cụm tam giác có vấn đề có thể dễ dàng liên quan đến các nút từ nhiều bộ hấp thụ.
Sawhney nói: “Một hình tam giác bạn đã chọn cách đây 500 bước, bạn cần phải nhớ cách nghĩ về nó như thế nào.
Điều mà cả bốn cuối cùng đã tìm ra là nếu họ chọn các hình tam giác của mình một cách cẩn thận, họ có thể tránh được việc phải theo dõi từng thứ nhỏ nhặt. Sawhney nói: “Điều tốt hơn nên làm là nghĩ về bất kỳ tập hợp nhỏ nào gồm 100 hình tam giác và đảm bảo rằng tập hợp các hình tam giác đó được chọn với xác suất chính xác”.
Các tác giả của bài báo mới lạc quan rằng kỹ thuật của họ có thể được mở rộng ra ngoài vấn đề này. Họ có đã áp dụng chiến lược của họ một vấn đề về Hình vuông la tinh, giống như một sự đơn giản hóa của một câu đố sudoku.
Ngoài ra, có một số câu hỏi cuối cùng có thể đặt ra đối với các phương pháp hấp thụ, Kwan nói. "Có rất nhiều vấn đề trong tổ hợp, đặc biệt là trong lý thuyết thiết kế, nơi mà các quy trình ngẫu nhiên là một công cụ thực sự mạnh mẽ." Một trong những vấn đề như vậy, phỏng đoán của Ryser-Brualdi-Stein, cũng là về các ô vuông Latinh và đã chờ đợi một giải pháp từ những năm 1960.
Mặc dù sự hấp thụ có thể cần phát triển thêm trước khi có thể giải quyết được vấn đề đó, nhưng nó đã đi một chặng đường dài kể từ khi ra đời cách đây 30, Maya Stein, Phó Giám đốc Trung tâm Mô hình Toán học tại Đại học Chile. “Đó là điều thực sự tuyệt vời khi thấy những phương pháp này phát triển như thế nào.”
