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: