Masalah Erdős–Graham

Dalam teori bilangan kombinatorial, masalah Erdős–Graham merupakan masalah untuk membuktikan bahwa, jika himpunan  dari bilangan bulat lebih besar dari satu terpartisi ke dalam himpunan bagian sangat banyak, maka salah satu dari himpunan bagian dapat digunakan untuk membentuk sebuah pecahan Mesir mewakilan persatuan. Yakni, untuk setiap , dan setiap pewarnaan- dari bilangan bulat lebih besar dari satu, terdapat sebuah himpunan bagian monokromatik hingga  mengenai bilangan bulat ini sehingga

Dalam detail lebih lanjut, Paul Erdős dan Ronald Graham menduga bahwa, untuk  cukup besar, anggota terbesar dari  dapat dibatasi oleh  untuk suatu tetapan  bebas dari . Ini diketahui bahwa, untuk ini menjadi benar,  harus setidaknya tetapan Euler .

Ernie Croot membuktikan konjekturnya sebagai bagian dari tesis Ph.Dnya, dan kemudian (sementara sebuah mahasiswa pasca-doktoral di Annals of Mathematics. Nilai Croot memberikan untuk  adalah paling terbesar: ini paling banyak . Hasil Croot berikut sebagai sebuah korolari mengenai sebuah lebih banyak teorema umum menyatakan keberadaan pecahan Mesir mewakili persatuan untuk himpunan  mengenai bilangan mulus dalam selang dari bentuk , dimana  berisi banyak bilangan yang cukup sehingga jumlah dari timbal-balik setidaknya enam. Konjektur Erdős–Graham mengikuti dari hasil ini dengan menunjukkan bahwa salah satunya dapat mencari sebuah selang dari bentuk ini yang mana jumlah dari timbal-baliknya mengenai semua bilangan mulus setidaknya , oleh karena itu, jika bilangan bulat adalah -berwarna, pasti ada sebuah himpunan bagian monokromatik  memenuhi syarat teorema Croot.

Lihat pula 

 Konjektur oleh Erdős

Referensi

Pranala luar 

 Ernie Croot's Webpage

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