Bài toán khoảng cách đơn vị của Erdős và giới hạn của các điểm trên mặt phẳng

Bài toán đặt ra là gì?

Trong hình học rời rạc, bài toán khoảng cách đơn vị của Erdős hỏi một câu tưởng chừng rất đơn giản:

Nếu ta đặt (n) điểm khác nhau trên mặt phẳng Euclid, tối đa có thể có bao nhiêu cặp điểm cách nhau chính xác 1 đơn vị?

Ta ký hiệu số lượng tối đa đó là (U(n)).

Nói cách khác, nếu coi mỗi cặp điểm cách nhau 1 đơn vị là một cạnh, thì ta đang hỏi: một đồ thị khoảng cách đơn vị với (n) đỉnh trên mặt phẳng có thể có tối đa bao nhiêu cạnh.

Giả thuyết của Erdős

Nhà toán học Paul Erdős đã đưa ra giả thuyết rằng số cặp khoảng cách đơn vị tối đa tăng gần tuyến tính theo (n). Cụ thể, ông dự đoán rằng:

[
U(n) = n^{1+o(1)}
]

Giả thuyết này dựa trên các cấu hình dạng lưới điểm nguyên. Khi các điểm được đặt trên một lưới vuông kích thước khoảng (\sqrt{n} \times \sqrt{n}), ta có thể tạo ra nhiều cặp điểm cách nhau đúng 1 đơn vị theo các hướng ngang và dọc, cho số lượng khoảng cách đơn vị lớn hơn tuyến tính một chút.

Các kết quả tốt nhất hiện nay

Cho đến nay, các nhà toán học mới chỉ xác định được các giới hạn trên và dưới cho bài toán.

• Giới hạn dưới:

 n^(1 + Ω(1 / log log n))

• Giới hạn trên tốt nhất đã biết:

Giới hạn trên này được chứng minh vào năm 1984 bởi Spencer, Szemerédi và Trotter, sử dụng các kỹ thuật trong lý thuyết giao điểm hình học (incidence geometry).

Tình trạng hiện tại của bài toán

Tóm lại, hiện nay chúng ta có:

lower bound:  n^(1 + O(1 / log log n))
upper bound:  O(n^(4/3))
conjecture:   n^(1 + o(1))

Khoảng cách giữa hai giới hạn vẫn còn khá lớn. Vì vậy, giả thuyết ban đầu của Erdős vẫn chưa được chứng minh hoặc bác bỏ.

Vì sao bài toán này quan trọng?

Bài toán khoảng cách đơn vị liên quan chặt chẽ đến nhiều lĩnh vực của toán học hiện đại, đặc biệt là:

• hình học rời rạc
• lý thuyết đồ thị hình học
• lý thuyết giao điểm (incidence theory)

Nhiều phương pháp mạnh mẽ trong toán học tổ hợp và hình học đã được phát triển một phần để giải quyết những câu hỏi kiểu này.

Sau gần 80 năm kể từ khi Erdős nêu ra (năm 1946), bài toán vẫn là một trong những câu hỏi nổi tiếng chưa có lời giải trong hình học rời rạc.