MỘT GIỚI HẠN VỀ MẠNG LƯỚI, NAY ĐƯỢC CHỨNG MINH CHO MỌI KÍCH THƯỚC

Hãy lấy vài điểm và nối một số cặp điểm bằng các đường. Các nhà toán học gọi đó là một đồ thị: các điểm là đỉnh của nó, các đường là cạnh của nó, và khoảng cách giữa hai đỉnh là số cạnh ít nhất cần đi để từ đỉnh này tới đỉnh kia. Bây giờ thêm hai quy tắc. Mọi cặp đỉnh phải ở khoảng cách tối đa là 2 — nối trực tiếp, hoặc thông qua một đỉnh kề chung. Và không cạnh nào được thừa: xóa bất kỳ một cạnh nào, sẽ có một cặp đỉnh cách nhau hơn hai bước. Một đồ thị như vậy được gọi là đồ thị tới hạn đường kính 2 (diameter-2-critical). Nó có thể có bao nhiêu cạnh?

Trần của Mantel, và một phỏng đoán táo bạo hơn

Năm 1907, Mantel chứng minh rằng một đồ thị n đỉnh không có tam giác — không có ba đỉnh nào nối đôi một với nhau — có tối đa ⌊n²/4⌋ cạnh: bình phương của n chia cho bốn, làm tròn xuống thành số nguyên. Chỉ một đồ thị đạt tới mức trần đó, là đồ thị hai phía đầy đủ cân bằng (balanced complete bipartite graph): hai nhóm có kích thước bằng nhau nhất có thể, mọi đỉnh của nhóm này nối với mọi đỉnh của nhóm kia, không có cạnh nào bên trong một nhóm.

Mọi đồ thị không có tam giác mà không thể thêm một cạnh nào nữa mà không tạo ra tam giác đều là đồ thị tới hạn đường kính 2. Chiều ngược lại thì không đúng: một số đồ thị tới hạn đường kính 2 có chứa tam giác.

Một đồ thị tới hạn đường kính 2 có 7 đỉnh và 9 cạnh, chứa tam giác v1v3v5. Xóa v1v3 sẽ phá hủy con đường hai bước duy nhất giữa v2 và v3; xóa một cạnh nằm ngoài tam giác sẽ khiến hai đầu của nó không còn con đường hai bước nào. — Hình 1, Das & Fox (2026), arXiv:2610.39032.

Phỏng đoán là tam giác chẳng mang lại thêm gì: một đồ thị tới hạn đường kính 2 có n đỉnh vẫn có tối đa ⌊n²/4⌋ cạnh, và đồ thị hai phía đầy đủ cân bằng vẫn là đồ thị duy nhất đạt tới mức đó. Định lý Mantel sẽ suy ra như một trường hợp đặc biệt. Với 7 đỉnh của hình vẽ, mức trần là 12 cạnh.

Một tháp các số 2

Theo Erdős, như Zoltán Füredi thuật lại, câu hỏi này bắt nguồn từ công trình của Ore vào những năm 1960. Ján Plesník phát biểu cận trên về số cạnh dưới dạng một giả thuyết vào năm 1975; Murty và Simon đề xuất nó một cách độc lập và bổ sung rằng đồ thị hai phía đầy đủ cân bằng là trường hợp cực trị duy nhất — từ đó có tên giả thuyết Murty–Simon. Trong những năm 1970 và 1980, các cận có dạng c·n² dần dần hạ xuống, với c ngày càng tiến gần 1/4.

Năm 1992, Füredi chứng minh giả thuyết cho mọi n đủ lớn, bằng các phương pháp chính quy (regularity methods) — những công cụ bắt nguồn từ bổ đề chính quy của Szemerédi. Cái giá phải trả là kích thước khởi điểm: n phải ít nhất bằng một tháp các số 2 cao khoảng 10¹⁴, tức là 2 lũy thừa 2 lũy thừa 2…, tính từ trên xuống — mỗi số 2 được nâng lên lũy thừa bằng toàn bộ phần nằm phía trên nó — với khoảng 10¹⁴ số 2 chồng lên nhau. Dưới kích thước đó, chỉ những họ đồ thị đặc biệt mới được giải quyết.

Cạnh đối đầu với cạnh vắng mặt

Chứng minh mới, của Sanjana Das và Jacob Fox thuộc Khoa Toán, Đại học Stanford, đúng với mọi n từ 3 trở lên. Nó sử dụng một cặp ghép cực đại (maximal matching): một tập hợp cạnh, không có hai cạnh nào chung một đỉnh, mà không thể thêm cạnh nào nữa mà không làm hai cạnh gặp nhau. Một cặp ghép trên n đỉnh chứa tối đa ⌊n/2⌋ cạnh.

Bổ đề then chốt: trong một đồ thị tới hạn đường kính 2, với bất kỳ cặp ghép cực đại nào, các cạnh nằm ngoài cặp ghép không bao giờ nhiều hơn các phi cạnh (non-edge) — tức các cặp đỉnh không được nối với nhau. Phần còn lại là số học. Hai lần số cạnh không vượt quá số cặp đỉnh cộng với kích thước của cặp ghép. Với 10 đỉnh: 45 cặp cộng tối đa 5 cạnh của cặp ghép là 50, do đó có tối đa 25 cạnh. Với mọi n, tổng đó đúng bằng hai lần mức trần của Mantel.

Bản thân bổ đề là một phép kiểm đếm cẩn thận. Một phi cạnh được gọi là tới hạn nếu chỉ có một con đường hai bước duy nhất nối hai đầu của nó, như với cả mười hai phi cạnh trong Hình 1. Các tác giả gắn mỗi phi cạnh tới hạn với hai cạnh trên con đường của nó và chia mạng kết quả thành các mảnh liên thông. Trong một mảnh, số cạnh vượt số phi cạnh tới hạn nhiều nhất là một, và mỗi mảnh có phần dư đó phải được bù bằng một phi cạnh không tới hạn. Để tìm ra chúng, các tác giả dùng lối ra hoán đổi (switch exits): lấy một cạnh hoặc một phi cạnh tới hạn của mảnh và đổi một đầu của nó lấy đỉnh được ghép với đầu đó trong cặp ghép. Mỗi phi cạnh không tới hạn bị nhận tối đa hai lần, mỗi mảnh có phần dư đưa ra ít nhất hai lần nhận, và phép đếm khép lại.

Ai đã tìm ra điều gì

“Chứng minh này phần lớn được AI tìm ra, cụ thể là GPT-5.6 Sol vào ngày 11 tháng 8 năm 2026,” các tác giả viết trong một tuyên bố ngắn về AI. Mô hình đã tìm ra một chứng minh đầy đủ cho cận ⌊n²/4⌋, mà họ đã đơn giản hóa. Với số đỉnh chẵn, nó cũng chứng minh rằng đồ thị hai phía đầy đủ cân bằng là trường hợp cực trị duy nhất, dựa trên một kết quả do Sumner chứng minh về các đồ thị trong đó mọi cặp ghép cực đại đều hoàn hảo, tức phủ mọi đỉnh.

Với số đỉnh lẻ, không cặp ghép nào hoàn hảo, và nhiều đồ thị có mọi cặp ghép cực đại đều bỏ sót đúng một đỉnh: lập luận của mô hình không thể điều chỉnh để áp dụng. Các tác giả đã tìm ra một chứng minh khác cho trường hợp đẳng thức, đúng với mọi n, và tự viết bài báo; một lượt rà soát cuối cùng qua GPT-6 Astra dẫn tới “một vài chỉnh sửa nhỏ”. Bài báo là một bản tiền ấn phẩm, chưa được bình duyệt, và không đề cập đến phiên bản nào của lập luận được máy tính kiểm chứng.

Trở lại năm 1907

Nếu một đồ thị chạm đúng mức trần, bất đẳng thức then chốt trở thành đẳng thức với mọi cặp ghép cực đại. Bằng cách chọn các cặp ghép một cách khéo léo, các tác giả chứng minh rằng một đồ thị như vậy hoặc là một hình sao (star) — một đỉnh nối với tất cả các đỉnh khác, ngoài ra không có gì — hoặc không có phi cạnh tới hạn nào. Trong một đồ thị tới hạn đường kính 2, mọi cạnh của một tam giác đều nằm trên một con đường tới hạn nào đó, nên không có phi cạnh tới hạn nghĩa là không có tam giác; hình sao cũng không có tam giác. Do đó, một đồ thị chạm mức trần là đồ thị không có tam giác, và bước cuối cùng chính là định lý mà giả thuyết muốn củng cố: kết quả năm 1907 của Mantel, vốn chỉ để lại duy nhất đồ thị hai phía đầy đủ cân bằng ở mức trần.