Hypergraphs: Phát Hiện Giải Pháp Cho Một Vấn Đề 50 Năm

Năm 1850, Thomas Penyngton Kirkman, một nhà toán học khi không hoạt động như mục sư chính trong Nhà thờ Anh, mô tả vấn đề 'nữ sinh': 'Mười lăm cô gái đi bộ ba người một hàng trong bảy ngày liên tiếp: yêu cầu là sắp xếp họ hàng ngày, sao cho không có hai người nào đi cùng nhau hai lần.'

Đối với một nhà toán học hiện đại, loại vấn đề này được tưởng tượng tốt nhất dưới dạng siêu đồ thị - một tập hợp các nút được sưu tập thành các nhóm ba hoặc nhiều hơn. 15 cô gái học sinh là các nút, và mỗi nhóm 'ba người một hàng' có thể được coi là một tam giác, với ba đoạn thẳng hoặc cạnh kết nối ba nút.

Vấn đề của Kirkman về cơ bản đặt câu hỏi liệu có một sắp xếp của những tam giác này kết nối tất cả các cô gái học sinh với nhau, nhưng với ràng buộc bổ sung là không có hai tam giác nào chia sẻ một cạnh. Chia sẻ cạnh sẽ ngụ ý rằng hai cô gái phải đi cùng nhau nhiều hơn một lần. Ràng buộc này có nghĩa là mỗi cô gái đi cùng hai người bạn mới mỗi ngày trong một tuần, sao cho mọi cặp có thể gặp nhau đúng một lần.

Vấn đề này và các vấn đề tương tự đã làm đau đầu các nhà toán học suốt gần hai thế kỷ kể từ khi Kirkman đặt câu hỏi của mình. Năm 1973, nhà toán học huyền thoại Paul Erdős đặt một vấn đề tương tự. Ông hỏi liệu có thể xây dựng một siêu đồ thị với hai tính chất dường như không tương thích. Trước hết, mọi cặp nút phải được kết nối bởi đúng một tam giác, như với những cô gái học sinh. Tính chất này làm cho đồ thị đầy tam giác. Yêu cầu thứ hai buộc các tam giác phải được phân bố một cách rất chính xác. (Cụ thể, yêu cầu rằng đối với bất kỳ nhóm nhỏ tam giác nào, phải có ít nhất ba nút nhiều hơn số tam giác.) “Bạn có hành vi đôi chút mâu thuẫn khi bạn có một đối tượng tổng thể dày đặc mà không có các phần dày đặc,” David Conlon, một nhà toán học tại Viện Công nghệ California, nói.

Tháng 1 này, trong một bằng chứng phức tạp 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ó đủ nút. “Lượng kỹ thuật mà họ đã trải qua để đạt được điều này thực sự là đáng kinh ngạc,” Allan Lo, một nhà toán học tại Đại học Birmingham, nói. Conlon đồng tình: “Đó là một công việc thực sự ấn tượng.”

Nhóm nghiên cứu xây dựng một hệ thống thỏa mãn yêu cầu khó khăn của Erdős bằng cách bắt đầu với một quá trình ngẫu nhiên để chọn tam giác và kỹ thuật nó một cách rất cẩn thận để phù hợp với nhu cầu của họ. “Số lượng sửa đổi khó khăn đi vào chứng minh thực sự là khá ấn tượng,” Conlon nói.

Chiến lược của họ là xây dựng siêu đồ thị cẩn thận từ những tam giác cá nhân. Ví dụ, hãy tưởng tượng 15 cô gái học sinh của chúng ta. Vẽ một đường giữa mỗi cặp.

Mục tiêu ở đây là vẽ ra những tam giác lên trên những đường này sao cho các tam giác đáp ứng hai yêu cầu: Đầu tiên, không có hai tam giác nào chia sẻ 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 con nhỏ của tam giác sử dụng một số lượng đủ lớn các nút.

Cách mà các nhà nghiên cứu đã làm điều này có lẽ được hiểu tốt nhất thông qua một phương trình tương tự.

Hãy nghĩ rằng thay vì tạo ra các tam giác từ các cạnh, bạn đang xây dựng những ngôi nhà từ các khối Lego. Các tòa nhà đầu tiên bạn tạo ra là phô trương, với các cấu trúc củng cố và trang trí phức tạp. Khi bạn đã hoàn thành chúng, đặt chúng sang một bên. Chúng sẽ phục vụ như một “bộ hấp thụ” — một loại kho chứa có cấu trúc.

Bây giờ hãy bắt đầu xây dựng những tòa nhà từ những viên gạch còn lại của bạn, tiến hành mà không có nhiều kế hoạch. Khi nguồn cung của bạn giảm đi, bạn có thể phát hiện mình có một số viên gạch lạc lõng, hoặc những ngôi nhà có cấu trúc không chắc chắn. Nhưng vì các tòa nhà hấp thụ đã được làm quá mức và được củng cố, bạn có thể nhặt một số viên gạch ra đây và đó và sử dụng chúng mà không gặp thảm họa.

Trong trường hợp của hệ thống tam giác Steiner, bạn đang cố gắng tạo ra các tam giác. Hấp thụ của bạn, trong trường hợp này, là một bộ sưu tập kỹ lưỡng các cạnh được chọ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 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 điều đó, bạn phân giải bộ hấp thụ thành các tam giác.

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 đã nghịch với quy trình, tìm ra cách mới để tránh qua các rào cản. Ví dụ, một biến thể mạnh mẽ gọi là hấp thụ lặp lại chia các cạnh thành một chuỗi lồng ghép của các tập hợp, sao cho mỗi tập hợp đều hoạt động như một bộ hấp thụ cho tập hợp lớn hơn tiếp theo.

“Trong thập kỷ qua hoặc đó đã có những cải tiến đáng kể,” Conlon nói. “Đó là một loại nghệ thuật, nhưng họ đã thực sự đưa nó lên mức nghệ thuật cao tại thời điểm này.”

Vấn đề của Erdős khó khăn ngay cả với hấp thụ lặp lại. “Rất rõ ràng rất nhanh chóng tại sao vấn đề này không được giải quyết,” Mehtaab Sawhney, một trong bốn nhà nghiên cứu giải quyết vấn đề này, cùng với Ashwin Sah, người như Sawhney là sinh viên sau đại học tại Viện Công nghệ Massachusetts; Michael Simkin, một học viên nghiên cứu 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 rất thú vị và khó khăn.”

Ví dụ, trong các ứng dụng khác của hấp thụ lặp lại, sau khi bạn kết thúc việc bao phủ một tập hợp—ent cả là bằng tam giác cho hệ thống tam giác Steiner, hoặc bằng các cấu trúc khác cho các vấn đề khác—bạn có thể coi nó như đã giải quyết và quên nó. Tuy nhiên, các điều kiện của Erdős đã ngăn chặn bốn nhà toán học này làm điều đó. Một cụm tam giác gặp vấn đề có thể dễ dàng liên quan đến các nút từ nhiều tập hấp hút.

“Một tam giác bạn chọn 500 bước trước, bạn cần nhớ cách nghĩ về nó một cách nào đó,” Sawhney nói.

Những gì bốn người cuối cùng tìm ra là nếu họ chọn tam giác của họ một cách cẩn thận, họ có thể tránh được việc theo dõi từng điều nhỏ nhất. “Điều tốt hơn là nghĩ về bất kỳ tập hợp nhỏ nào gồm 100 tam giác và đảm bảo rằng tập hợp tam giác đó được chọn với xác suất đúng,” Sawhney nói.

Những tác giả của bài báo mới lạc quan rằng phương pháp của họ có thể mở rộng ra ngoài vấn đề này. Họ đã áp dụng chiến lược của mình vào một vấn đề về ô vuông Latin, giống như một bài đố sudoku được đơn giản hóa.

Hơn nữa, có nhiều câu hỏi có thể cuối cùng sẽ nhường chỗ cho các phương pháp hấp thụ, theo lời của Kwan. “Có rất nhiều vấn đề trong tổ hợp học, đặc biệt là trong lý thuyết thiết kế, nơi các quy trình ngẫu nhiên là một công cụ rất mạnh mẽ.” Một trong những vấn đề như vậy, giả thuyết Ryser-Brualdi-Stein, cũng liên quan đến ô vuông Latin và đã chờ đợi một giải pháp từ những năm 1960.

Mặc dù hấp thụ có thể cần phát triển thêm trước khi nó có thể giải quyết vấn đề đó, nhưng nó đã đi một quãng đường dài kể từ khi được sáng tạo, theo lời của Maya Stein, giám đốc phó của Trung tâm Mô hình Hóa Toán học tại Đại học Chile. “Điều đó thực sự là điều tuyệt vời khi thấy cách những phương pháp này phát triển.”

Bài viết gốc được tái in với sự cho phép của Quanta Magazine, một tờ báo độc lập với biên tập của Sở học Simon, có nhiệm vụ làm tăng sự hiểu biết của công chúng về khoa học bằng cách đưa ra các phát triển và xu hướng nghiên cứu trong toán học và các ngành khoa học tự nhiên và cuộc sống.