Kẹp đồ thị: cách dùng hai mạng dễ hiểu để nghiên cứu một mạng khó

Trong mô hình mạng điện thoại của Edgar Gilbert, mỗi cặp điểm được nối hay không tùy vào một lần tung đồng xu. Quy tắc ấy dễ hình dung, nhưng nhiều mạng mà nhà toán học muốn nghiên cứu lại có ràng buộc khó hơn: mọi điểm phải có cùng số đường nối. Ý tưởng “kẹp sandwich” giải quyết khoảng cách này bằng cách ghép một đồ thị như thế với hai đồ thị tạo theo kiểu tung đồng xu: một nằm bên trong nó, một bao lấy nó. Khi tính chất cần xét được bảo toàn theo chiều thêm hoặc bớt cạnh, kết quả về hai đồ thị dễ phân tích có thể cho biết điều gì đúng với đồ thị ở giữa. [1]

Hai cách tạo mạng khác nhau ở đâu?

Đồ thị gồm các đỉnh và các cạnh nối giữa các đỉnh. Trong mô hình của Gilbert, ta lần lượt xét mọi cặp đỉnh; với mỗi cặp, một phép tung đồng xu quyết định có cạnh hay không. Đồng xu có thể được điều chỉnh để khả năng xuất hiện cạnh không nhất thiết là một nửa. Vì số cạnh của từng đỉnh không bị ấn định trước, kết quả có thể là một mạng nơi có đỉnh nối với nhiều đỉnh khác, có đỉnh lại nối với ít đỉnh hơn. Loại này được gọi là đồ thị ngẫu nhiên nhị thức. [1]

Đồ thị chính quy thì phải thỏa một điều kiện khác: mọi đỉnh có cùng số cạnh. Nếu một cạnh đã được đặt, lựa chọn cạnh tiếp theo phải tính đến số cạnh còn thiếu ở các đỉnh liên quan. Các lựa chọn vì thế ràng buộc lẫn nhau, khiến việc phân tích khó hơn. Đây không đơn thuần là thay một đồng xu bằng đồng xu khác: hai cách tạo đồ thị tổ chức sự ngẫu nhiên theo hai quy tắc khác nhau. [1]

Tại sao phải kẹp từ cả hai phía?

Hãy tưởng tượng ba đồ thị dùng cùng một tập đỉnh. Mọi cạnh của đồ thị nhị thức phía dưới đều có mặt trong đồ thị chính quy; mọi cạnh của đồ thị chính quy lại có mặt trong đồ thị nhị thức phía trên. “Dưới” và “trên” ở đây nói về quan hệ chứa cạnh, không phải vị trí trên trang giấy. Điều quan trọng là các đồ thị phải được tạo theo một cách ghép cặp phù hợp, trong khi mỗi đồ thị riêng lẻ vẫn tuân theo đúng mô hình ngẫu nhiên của nó. [1]

Một số tính chất chỉ có thể được củng cố khi thêm cạnh. Chẳng hạn, nếu đồ thị phía dưới đã có một chu trình đi qua mỗi đỉnh đúng một lần, thêm cạnh không làm mất chu trình ấy. Ngược lại, có những tính chất được bảo toàn khi bỏ cạnh: nếu đồ thị phía trên không có một kiểu cấu trúc nào đó, đồ thị nằm trong nó cũng không thể có cấu trúc ấy. Hai phía của chiếc kẹp phục vụ hai chiều suy luận khác nhau; không phải mọi kết quả đều chuyển được từ một phía bất kỳ. [1]

Có thể hình dung bằng một ví dụ: thêm đường vào một bản đồ không xóa tuyến đường đã vẽ, còn bỏ đường không thể tạo ra một tuyến mới. Ví dụ này chỉ giúp nhìn rõ hướng suy luận. Với đồ thị ngẫu nhiên, bước khó hơn nhiều là bảo đảm quan hệ chứa cạnh ấy thực sự có thể đạt được mà không làm sai quy tắc tạo ra từng loại đồ thị. [1]

Điều gì khiến việc ghép cặp khó?

Jeong Han Kim và Van Ha Vu đã nêu giả thuyết về khả năng xây dựng chiếc kẹp trong những điều kiện thích hợp. Muốn thực hiện nó, không thể chỉ tạo riêng ba đồ thị rồi đặt cạnh nhau: chúng còn phải khớp về cạnh. Nếu tùy ý ép đồ thị nhị thức nằm trong đồ thị chính quy sau khi đã tạo xong, đồ thị thu được có thể không còn tuân theo phân bố ngẫu nhiên cần nghiên cứu. [1]

Bài toán vì vậy nằm ở quy tắc tạo chung, thường gọi là ghép cặp. Quy tắc ấy cần giữ hai lời hứa cùng lúc: từng loại đồ thị có đúng tính ngẫu nhiên vốn có, và quan hệ chứa cạnh giữa chúng xảy ra như yêu cầu. Ràng buộc số cạnh bằng nhau ở mọi đỉnh khiến lời hứa thứ hai đặc biệt khó giữ. Trước khi có lời giải đầy đủ, các nhà toán học đã chứng minh được phía dưới và xử lý phía trên trong một số trường hợp, nhưng chưa hoàn tất chiếc kẹp theo phạm vi giả thuyết. [1]

Lời giải năm 2025 xây các lớp ra sao?

Natalie Behague, Daniel Iľkovič và Richard Montgomery hoàn tất chứng minh vào năm 2025. Để tạo phía dưới, họ xây đồ thị nhị thức và đồ thị chính quy từng cạnh một. Khi lần tung đồng xu thứ nhất thêm cạnh vào đồ thị nhị thức, cạnh ấy cũng được thêm vào đồ thị chính quy. Khi nó không thêm cạnh, một quyết định tiếp theo vẫn có thể thêm cạnh cho đồ thị chính quy, nhằm đáp ứng yêu cầu mọi đỉnh cuối cùng có cùng số cạnh. [1]

Điểm tinh tế nằm ở xác suất của quyết định tiếp theo: nó phải thay đổi theo những cạnh đã có. Nhóm nghiên cứu tìm cách ước lượng xác suất ấy để đồ thị cuối cùng vẫn là đồ thị chính quy ngẫu nhiên đúng nghĩa, đồng thời chứa toàn bộ cạnh của đồ thị nhị thức phía dưới. Để xử lý phía trên, họ đảo chiều cách xây dựng: bắt đầu với những đồ thị có mọi cạnh có thể có, rồi lần lượt bỏ cạnh để thu được đồ thị chính quy nằm trong một đồ thị nhị thức. [1]

Nói “thêm” ở một phía và “bỏ” ở phía kia nghe như hai thao tác đơn giản. Nhưng chúng phải được điều phối để kết quả không chỉ trông có vẻ đúng. Một mạng có số cạnh bằng nhau tại mọi đỉnh chưa đủ cho lập luận; cách nó được chọn trong số các mạng có thể có cũng phải đúng. Chính yêu cầu đó biến chiếc kẹp từ một hình ảnh dễ nhớ thành một định lý có ích. [1]

Chiếc kẹp đem lại lợi ích gì?

Đồ thị nhị thức đã được nghiên cứu rộng rãi vì quy tắc tạo của nó tương đối dễ phân tích. Khi có phép ghép cặp thích hợp, nhà toán học có thể dùng các kết quả ấy để suy ra nhiều tính chất của đồ thị chính quy, thay vì phải chứng minh lại từng tính chất từ đầu. Giá trị của lời giải không nằm ở việc nó tuyên bố mọi đồ thị đều giống nhau, mà ở chỗ nó xác lập một quan hệ đủ chặt để chuyển những kết quả phù hợp theo đúng chiều. [1]

Chiếc kẹp cũng làm rõ một liên hệ ít hiển nhiên: một quá trình chọn cạnh bằng các phép tung đồng xu và một quá trình bị ràng buộc bởi số cạnh ở mỗi đỉnh vẫn có thể được xây dựng để so sánh trực tiếp. Khi gặp một câu hỏi mới về mạng chính quy, nhà nghiên cứu có thêm cách bắt đầu: xem tính chất ấy thay đổi thế nào khi thêm hoặc bỏ cạnh, rồi chọn phía của chiếc kẹp có thể trả lời câu hỏi đó. [1]