Masalah Erdős–Graham

Dalam teori bilangan kombinatorial, masalah Erdős–Graham membuktikan bahwa, jika himpunan  dari bilangan bulat lebih besar dari satu dipartisi ke dalam terhingga banyaknya subhimpunan, maka salah satu subhimpunan itu dapat digunakan untuk membentuk sebuah representasi pecahan Mesir dari kesatuan. Artinya, untuk setiap , dan setiap -coloring dari bilangan bulat lebih besar dari satu, terdapat suatu subhimpunan monokromatik terhingga  dari bilangan bulat tersebut sehingga

Dalam penjelasan lebih lanjut, Paul Erdős dan Ronald Graham menduga bahwa, untuk nilai  yang cukup besar, anggota terbesar dari  dapat dibatasi oleh  untuk suatu konstanta  yang independen dari . Andaikata bahwa dugaan tersebut benar,  harus setidaknya berupa konstanta .

Ernie Croot membuktikan konjekturnya sebagai bagian dari tesis doktor filsafatnya, dan kemudian menerbitkan pembuktiannya di Annals of Mathematics sembari menjadi peneliti  di Universitas California, Berkeley. Nilai yang diberikan Croot untuk  sangat besar, paling banyak . Hasil Croot merupakan korolari suatu teorema yang lebih umum, yang menyatakan keberadaan representasi pecahan Mesir dari kesatuan untuk himpunan  dari bilangan mulus di dalam selang ; disini  mengandung banyak bilangan yang cukup sehingga jumlah dari timbal balik setidaknya enam. Konjektur Erdős–Graham mengikuti hasil tersebut dengan menunjukkan bahwa seseorang dapat mencari suatu selang tersebut, yang penjumlahan dari timbal-balik dari semua bilangan mulus setidaknya . Oleh karena itu, jika bilangan bulat adalah -colored, pasti ada suatu subhimpunan monokromatik  yang memenuhi syarat teorema Croot.

Bentuk hasil yang lebih kuat mengatakan bahwa sebarang himpunan dari bilangan bulat dengan densitas atas positif mencakup penyebut representasi pecahan Mesir dari satu. Hasil tersebut diumumkan pada tahun 2021 oleh Thomas Bloom, seorang peneliti postdoctoral di Universitas Oxford.

 Lihat pula 

 Konjektur oleh Erdős

 Referensi 

 Pranala luar 

 Ernie Croot's Webpage

Kategori:Kombinatorika
Kategori:Paul Erdős
Kategori:Teorema dalam teori bilangan
Kategori:Konjektur yang telah dibuktikan