NỐI MỌI ĐIỂM VỚI NHAU: SỐ GIAO ĐIỂM ÍT NHẤT ĐÃ ĐƯỢC CHỨNG MINH

Đặt năm điểm lên một tờ giấy và nối mọi cặp điểm bằng một đường cong: tổng cộng mười đường cong. Chúng có thể uốn cong tùy ý, nhưng không đường nào được đi qua một điểm thứ ba. Hãy thử tránh mọi giao điểm, và bạn sẽ thất bại. Với năm điểm, ít nhất 1 giao điểm là không thể tránh; với sáu điểm, ít nhất 3; với mười điểm, ít nhất 60.

Các nhà toán học gọi một hình vẽ như vậy là một cách vẽ đồ thị đầy đủ (complete graph) Kₙ — n điểm, mọi cặp đều được nối — và số giao điểm ít nhất mà một cách vẽ có thể đạt được là số giao cắt (crossing number) của nó. Martin Balko, thuộc Đại học Charles ở Cộng hòa Séc, gọi câu hỏi này là “một trong những bài toán nổi tiếng nhất của lý thuyết đồ thị tô pô”.

Con số của một nghệ sĩ

Cuối thập niên 1950, nghệ sĩ người Anh Anthony Hill đã dựng được các cách vẽ Kₙ với đúng

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

giao điểm, trong đó ⌊ ⌋ nghĩa là làm tròn xuống. Phỏng đoán rằng không cách vẽ nào làm tốt hơn được Guy công bố lần đầu, sau đó được Harary và Hill thảo luận, và được Erdős cùng Guy phổ biến rộng rãi. Nó được biết đến với tên giả thuyết Harary–Hill, hay giả thuyết Guy.

Công thức tăng nhanh:

4 điểm trở xuống: 0 giao điểm
5 điểm: 1
7 điểm: 9
10 điểm: 60
14 điểm: 315

Sáu thập kỷ của những câu trả lời từng phần

Các cách vẽ với đúng Z(n) giao điểm đã tồn tại cho mọi số điểm; phần khó là chứng minh rằng không cách vẽ nào làm tốt hơn.

Trong hơn sáu mươi năm, điều đó chỉ được chứng minh cho những loại cách vẽ đặc biệt — chẳng hạn khi mọi điểm nằm trên một đường thẳng và mỗi đường cong chỉ ở một phía của đường thẳng đó, hoặc khi các điểm nằm trên một mặt cầu và mỗi đường cong đi theo đường ngắn nhất. Chính Balko, cùng Fulek và Kynčl, đã giải quyết một lớp như vậy. Đến năm 2021, máy tính đã xác nhận công thức với tối đa 14 điểm. Với số điểm rất lớn, các kết quả tổng quát tốt nhất bảo đảm ít nhất 98,5%, rồi 98,99%, của Z(n).

Một chứng minh, rồi một chứng minh sáng sủa hơn

Năm 2026, OpenAI công bố một chứng minh cho mọi số điểm, được bài báo của Balko liệt kê là một “OpenAI Math Release preprint” và ghi công cho định lý. Bài báo không nói chứng minh đó đã được tìm ra như thế nào. Theo lời Balko, bản gốc “tương đối ngắn” nhưng “khá khó theo dõi”. Bản thảo của ông trình bày một biến thể tinh gọn mà, như ông viết, “chỉ đòi hỏi kiến thức sơ cấp về đại số tuyến tính và lý thuyết đồ thị”. Một nhà toán học khác, Gelasio Salazar, đang chuẩn bị một bản trình bày chi tiết riêng.

Đếm hệ số thay vì đếm giao điểm

Vì các cách vẽ đã biết đạt được Z(n), chỉ cần chứng minh cận dưới. Chứng minh gồm bốn bước.

Chỉ cần xét số lẻ. Một cách vẽ tốt nhất có thể được vẽ lại sao cho các đường cong chung một điểm không bao giờ cắt nhau; khi đó mỗi giao điểm liên quan đến 4 điểm khác nhau. Lần lượt xóa từng điểm trong 6 điểm: mỗi hình 5 điểm còn lại có ít nhất 1 giao điểm, và mỗi giao điểm tồn tại sau đúng 2 trong 6 lần xóa (nó biến mất mỗi khi một trong 4 điểm của chính nó bị xóa, và tồn tại sau 2 lần còn lại). Vậy hai lần số giao điểm ít nhất là 6: số giao điểm ít nhất là 3, tức Z(6). Cách đếm tương tự áp dụng cho mọi số chẵn.
Một họ đa thức. Gán cho mỗi điểm một con số riêng. Một giao điểm liên quan đến hai đường cong, tức bốn điểm, tức bốn con số. Balko dùng các đa thức bốn biến, được chọn sao cho họ đa thức có đúng Z(n) hệ số độc lập khi n lẻ — với 7 điểm, 3 × 3 = 9.
Quá ít giao điểm thì còn chỗ trống. Đòi hỏi một đa thức triệt tiêu tại một giao điểm là một phương trình. Khi số phương trình ít hơn số hệ số tự do, đại số tuyến tính luôn để lại một nghiệm khác không. Vậy một cách vẽ có ít hơn Z(n) giao điểm sẽ đi kèm một đa thức khác không triệt tiêu tại mọi giao điểm của nó; hãy lấy đa thức có bậc thấp nhất.
Mặt phẳng phản kháng. Hình học xuất hiện qua một sự kiện kinh điển: một đường khép kín trong mặt phẳng cắt một đường khép kín khác từ phải sang trái đúng bằng số lần cắt từ trái sang phải. Với các trọng số được chọn khéo, điều này cho ra một tổng các bình phương của các giá trị của đa thức, một số được tính dương, một số tính âm, có tổng bằng không. Các số hạng dương đều nằm tại các giao điểm, nơi đa thức bằng không, nên các số hạng âm cũng phải triệt tiêu. Áp dụng lần thứ hai sự kiện về đường khép kín khiến đa thức chia hết cho một nhân tử cố định; phép chia cho ra một đa thức khác không có bậc thấp hơn với cùng tính chất, điều này là không thể, vì ta đã lấy đa thức có bậc thấp nhất.

Lập luận về dấu đó là thay đổi chính của Balko: nó thay thế lập luận gốc “liên quan đến một dạng song tuyến tính không suy biến và các phần bù trực giao”. Ông cũng chứng minh sự kiện về đường khép kín theo cách khác và tách riêng từng điểm một cách trực tiếp hơn.

Các mạng lưới khác được giải quyết cùng lúc

Câu trả lời vẫn là Z(n) nếu thay vì đếm giao điểm, ta đếm các cặp đường cong có cắt nhau, hoặc cắt nhau một số lẻ lần — miễn là các đường cong chung một điểm không bao giờ gặp nhau ở chỗ khác. Kết hợp với các phép quy giản trước đó, định lý còn cho số giao cắt chính xác của các đồ thị đầy đủ bị bỏ bớt một số cạnh, của các bản sao một đồ thị đầy đủ nối thành chuỗi dọc một đường đi hoặc quanh một chu trình chẵn, và của một họ mạng lưới dạng fractal gọi là đồ thị Sierpiński mở rộng (extended Sierpiński graphs).

Bỏ đi một đường cong duy nhất khỏi đồ thị đầy đủ trên 6 điểm, và mức tối thiểu của nó giảm từ 3 giao điểm xuống 2; trên 8 điểm, từ 18 xuống 15.