CÂU ĐỐ ĐỒ THỊ TỪ THẬP NIÊN 1960 CUỐI CÙNG ĐÃ KHÉP LẠI

Lấy một số điểm và nối một vài cặp trong đó bằng các đường: các nhà toán học gọi đó là một đồ thị, các điểm là đỉnh và các đường là cạnh. Một chu trình là một vòng khép kín đi qua các đỉnh phân biệt rồi trở về điểm xuất phát. Một câu hỏi tự nhiên là liệu các cạnh của một đồ thị có thể được chia ra — mỗi cạnh dùng đúng một lần — thành các chu trình hay không.

Như bài báo nhắc lại, câu trả lời đã được biết từ lâu: điều đó khả thi khi và chỉ khi mỗi đỉnh chạm vào một số chẵn cạnh. Những đồ thị như vậy được gọi là đồ thị Euler. Câu hỏi tiếp theo là cần bao nhiêu chu trình. Và với những đồ thị mà chỉ dùng chu trình thì không đủ, người ta cho phép dùng cả các cạnh đơn lẻ làm mảnh.

Giả thuyết

Vào thập niên 1960, Erdős và Gallai phỏng đoán rằng các cạnh của mọi đồ thị có n đỉnh đều có thể được chia thành một số chu trình và cạnh đơn lẻ nhiều nhất là tỉ lệ với n — viết là O(n). Erdős đã đưa bài toán này vào một vài tuyển tập bài toán mở của ông. Một giả thuyết liên quan của Hajós đòi hỏi nhiều nhất (n − 1)/2 chu trình cho mọi đồ thị Euler.

Tuyến tính là điều tốt nhất có thể mong đợi: Erdős đã chỉ ra rằng có những đồ thị cần khoảng 1,5 n mảnh. Câu hỏi là liệu một hằng số nhân với n có luôn đủ hay không.

Năm mươi năm cận dịch chuyển chậm chạp

Chính Erdős và Gallai đã nhận ra một phương pháp đơn giản: lặp đi lặp lại việc bỏ đi chu trình dài nhất. Nó cho khoảng n log n mảnh — và theo bài báo, đó vẫn là cận tổng quát tốt nhất trong gần năm mươi năm. Gần đây hơn, Conlon, Fox và Sudakov hạ nó xuống n log log n, rồi Bucić và Montgomery xuống n log* n, trong đó log* n — số lần phải lấy logarit để xuống dưới một — tăng chậm đến mức khó tưởng tượng. Các cách tiếp cận này làm việc theo từng vòng, và mỗi vòng tốn khoảng n chu trình, nên số vòng luôn len lỏi vào kết quả đếm cuối cùng. Giả thuyết cũng đã được chứng minh cho những họ đồ thị đặc biệt, chẳng hạn đồ thị ngẫu nhiên.

Những trọng số trả giá cho các vòng

Jaehoon Kim, thuộc KAIST ở Hàn Quốc, nay chứng minh giả thuyết: tồn tại một hằng số cố định C sao cho mọi đồ thị có n đỉnh đều tách được thành nhiều nhất Cn chu trình và cạnh. Như một hệ quả, giả thuyết của Hajós đúng sai khác một hằng số nhân.

Lời chứng minh từ bỏ cách làm theo vòng. Một quy trình duy nhất loại bỏ từng chu trình và cạnh một, và tổng số được kiểm soát bởi hai đại lượng, mỗi đại lượng đều nằm dưới một hằng số nhân với n.

Một thế năng dựa trên bậc. Mỗi đỉnh nhận một trọng số giảm dần theo số cạnh của nó, xấp xỉ 1 / (bậc × log² bậc). Một chu trình là nặng nếu tổng trọng số các đỉnh của nó ít nhất bằng 1. Loại bỏ một chu trình nặng làm giảm một “thế năng” tổng thể ít nhất 1 đơn vị, và thế năng này ban đầu không vượt quá một hằng số nhân với n. Vì vậy chu trình nặng chỉ có thể bị loại bỏ O(n) lần.
Số đỉnh. Khi không còn chu trình nặng nào, đồ thị là “nhẹ” — và định lý mới chủ chốt chứng tỏ rằng một đồ thị nhẹ có bậc lớn phải chứa một vùng dày đặc, gần như khép kín. Vùng đó được tách thành một số chu trình và cạnh tỉ lệ với kích thước của nó, sau đó ít nhất một phần năm mươi số đỉnh của nó chỉ còn nhiều nhất hai cạnh và bị loại hẳn. Vì mỗi đỉnh chỉ có thể bị loại một lần, phần này cũng tốn O(n).

Sơ đồ ba đường đi được nối thành một chu trình qua ba vùng expander tô bóng, với các đường nối nét đứt nhiều màu.

Bên trong những phần dày đặc của đồ thị, các đoạn đường đi được khép lại thành một chu trình duy nhất nhờ các đường nối đi qua “expander”; một phép tô màu ngẫu nhiên giữ cho các đường nối của cùng một chu trình tách rời nhau. — Hình 3, Kim (2026), arXiv:2610.07840.

Để tách những vùng dày đặc đó, lời chứng minh mở rộng bộ công cụ của Bucić và Montgomery về các “expander” bền vững — những đồ thị trong đó mọi tập đỉnh đều có nhiều đỉnh kề — và tô màu các đỉnh một cách ngẫu nhiên để các đường nối của cùng một chu trình không bao giờ va vào nhau.

Những gì vẫn còn bỏ ngỏ

Hằng số C cực kỳ lớn, và tác giả không tìm cách tối ưu nó. Việc tìm hằng số tốt nhất — ít nhất là 1,5 — vẫn còn bỏ ngỏ, cũng như dạng chính xác của giả thuyết Hajós và một giả thuyết liên quan của Gallai về việc tách đồ thị thành các đường đi. Mẹo gán trọng số chỉ cần những trọng số có tổng hội tụ, và tác giả gợi ý rằng nó có thể hữu ích trong các bài toán phân rã khác.

Đây là một bản tiền ấn phẩm của một tác giả duy nhất, chưa qua kiểm tra bình duyệt.

Xung đột lợi ích. Tác giả cho biết đã sử dụng rất nhiều ChatGPT (OpenAI) và Claude (Anthropic) trong việc phát triển các lập luận và soạn văn bản cùng hình vẽ, đồng thời đã tự kiểm chứng mọi kết quả và chịu hoàn toàn trách nhiệm về bài báo. Văn bản bạn đang đọc cũng do Claude viết.