Toán họcBản tiền ấn phẩmLý thuyết5 phút đọc

CÁC MẠNG NGẪU NHIÊN KHÔNG CÒN TÔ MÀU ĐƯỢC KHI ĐẠT MỘT MẬT ĐỘ CỐ ĐỊNH

Lấy một đồ thị — các chấm nối với nhau bằng các liên kết — và một hộp màu. Một phép tô màu đúng (proper colouring) với q màu gán cho mỗi chấm một trong q màu sao cho hai chấm được nối với nhau không bao giờ cùng màu. Khi có ít liên kết, việc đó dễ dàng. Khi có nhiều, nó trở nên bất khả.

Giờ hãy dựng đồ thị một cách ngẫu nhiên: n chấm, mỗi cặp được nối độc lập với một xác suất nhỏ, sao cho trung bình mỗi chấm có d láng giềng. Khi d tăng, đồ thị ngẫu nhiên chuyển từ “hầu chắc chắn tô được bằng q màu” sang “hầu chắc chắn không”. Chính xác thì sự chuyển đổi xảy ra ở đâu? Câu hỏi đó, với mọi số màu cố định q từ ba trở lên, là chủ đề của một bài báo mới của Gaia Carenini, tại Đại học Cambridge.

Một điểm chuyển có thể chao đảo

Trong một bài báo năm 1999 có trong danh mục tài liệu tham khảo, Achlioptas và Friedgut đã chứng minh rằng sự chuyển tiếp này là sắc nét (sharp): với mọi kích thước n, tồn tại một bậc trung bình tới hạn d_q(n) sao cho ngay dưới giá trị đó, đồ thị hầu chắc chắn tô màu được, còn ngay trên đó thì hầu chắc chắn không. Cửa sổ trong đó sự chuyển đổi xảy ra co lại về không.

Nhưng điều đó còn để lại một kẽ hở. Không có gì ngăn chính giá trị tới hạn dao động khi đồ thị lớn dần — nằm ở một chỗ với đồ thị có kích thước này, hơi lệch đi với đồ thị lớn hơn, và không bao giờ ổn định. Giả thuyết hội tụ Achlioptas–Friedgut khẳng định điều đó không xảy ra: với mỗi q, tồn tại một hằng số duy nhất d_q, dưới đó các đồ thị ngẫu nhiên tô màu được, còn trên đó thì không.

Các nhà vật lý đã dự đoán gì

Vật lý thống kê đã có một bức tranh về những gì diễn ra. Khi các liên kết được thêm vào, các phép tô màu hợp lệ tụ lại thành các cụm (clusters): các phép tô màu trong cùng một cụm giống nhau, trong khi hai cụm khác biệt nhau ở nhiều chấm. Rồi, ở một giai đoạn gọi là ngưng tụ (condensation), một số ít cụm lớn nắm giữ một phần đáng kể trong tất cả các phép tô màu — và chỉ sau đó tập hợp các phép tô màu mới trở thành rỗng. Cách tổ chức đó giải thích vì sao các lập luận đếm gặp khó khăn ở gần ngưỡng.

Với nhiều màu, các công trình trước đó đã khoanh ngưỡng vào một khoảng hẹp: nó nằm giữa khoảng 2q log q − log q − 2 log 2 và 2q log q − log q − 1, một khoảng có độ rộng 2 log 2 − 1 khi q tăng. Nhưng “hẹp” không có nghĩa là “cố định”, và với số màu nhỏ như ba, câu hỏi vẫn còn bỏ ngỏ.

Một bài toán song sinh, được giải quyết trước

Bài toán tô màu có một người anh em song sinh: tính thỏa mãn được (satisfiability), bài toán chọn giá trị đúng hoặc sai cho các biến sao cho một danh sách các ràng buộc logic ngẫu nhiên đều được thỏa mãn. Ở đó cũng vậy, người ta đã biết có một ngưỡng sắc nét nhưng chưa chứng minh được rằng nó ổn định. Trong một báo cáo năm 2026 được trích dẫn trong bài báo, Carenini đã công bố một chứng minh rằng nó có ổn định, với mọi độ dài ràng buộc từ ba trở lên, bằng cách chỉ ra rằng cửa sổ chuyển tiếp rất hẹp. Bài báo mới điều chỉnh lập luận đó cho bài toán tô màu.

Những cặp bị đóng băng cùng nhau

Chứng minh đi qua một chuỗi các phép quy dẫn. Khi thêm từng liên kết ngẫu nhiên một, gọi H là thời điểm đồ thị không còn tô màu được. Nếu H thay đổi ít từ đồ thị ngẫu nhiên này sang đồ thị ngẫu nhiên khác — trong một cửa sổ khoảng n/(log n)² liên kết — thì ngưỡng phải ổn định. Một bất đẳng thức cổ điển biến điều đó thành một câu hỏi về đồ thị cuối cùng còn tô màu được: trung bình, nó chịu được bao nhiêu liên kết ngẫu nhiên mới?

Đây là khái niệm then chốt: các cặp đóng băng (frozen pairs). Hai chấm tạo thành một cặp đóng băng khi mọi phép tô màu hợp lệ đều gán cho chúng cùng một màu. Một liên kết mới là chí mạng đúng khi nó nối một cặp như vậy. Từng chấm riêng lẻ không thể bị đóng băng vào một màu cụ thể, vì việc hoán đổi các màu cho nhau luôn cho ra một phép tô màu hợp lệ khác; điều bị ép buộc là một quan hệ giữa hai chấm. Carenini theo dõi cách các lớp đóng băng này lớn lên khi các liên kết được thêm vào, bằng cách xóa một liên kết hoặc cả một chấm rồi xem xét những lựa chọn xuất hiện trở lại. Các ước lượng cho thấy đồ thị cuối cùng còn tô màu được không thể trụ lâu, điều này thu hẹp cửa sổ đủ để chứng minh giả thuyết.

Điều vẫn chưa biết

Định lý nói rằng ngưỡng d_q tồn tại với mọi q ≥ 3. Nó không nói ngưỡng nằm ở đâu: bài báo không đưa ra giá trị nào cho ngưỡng, kể cả với ba màu. Bài báo là một bản tiền ấn phẩm có một tác giả duy nhất và chưa được bình duyệt. Bài báo kết thúc bằng một tuyên bố ngắn rằng không lập luận toán học nào trong đó được tạo ra bởi một mô hình ngôn ngữ lớn.