Masalah Jarak Satuan Erdős Masih Menjadi Misteri dalam Matematika

Dalam geometri diskret, ada satu pertanyaan klasik yang sederhana untuk ditanyakan tetapi sangat sulit dijawab: berapa banyak pasangan titik yang bisa berjarak tepat 1 jika kita menempatkan n titik di bidang?

Pertanyaan ini dikenal sebagai Masalah Jarak Satuan Erdős (Erdős unit distance problem), pertama kali diajukan oleh matematikawan legendaris Paul Erdős pada tahun 1946.

Inti Masalahnya

Bayangkan Anda menaruh (n) titik di bidang Euclidean (bidang datar biasa seperti pada koordinat kartesius). Pertanyaannya adalah:

Berapa jumlah maksimum pasangan titik yang jaraknya tepat 1 unit?

Secara formal, kita ingin mengetahui nilai maksimum dari jumlah pasangan titik berjarak 1 di antara (n) titik pada bidang .

Masalah ini juga bisa dipandang melalui graf: setiap titik menjadi simpul, dan kita menggambar sisi jika dua titik berjarak 1.

Dugaan Erdős

Erdős memperkirakan bahwa jumlah maksimum pasangan tersebut tumbuh hampir linear terhadap jumlah titik. Secara matematis ia menduga:

n^(1+o(1))

Artinya jumlah pasangan jarak satu meningkat sedikit lebih cepat dari (n), tetapi jauh lebih kecil dari (n^{4/3}) atau bentuk polinomial yang lebih besar .

Dugaan ini didukung oleh contoh konstruksi menggunakan kisi persegi (square lattice). Jika titik-titik ditempatkan pada grid bilangan bulat, banyak pasangan titik yang berjarak tepat 1 secara horizontal atau vertikal. Konstruksi semacam ini menghasilkan jumlah pasangan jarak satu yang sedikit lebih besar dari linear terhadap (n) .