Masalah Erdős–Graham

Dalam teori bilangan kombinatorial, masalah Erdős–Graham merupakan masalah untuk membuktikan bahwa, jika himpunan { 2 , 3.4 , … } 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 r > 0 , dan setiap pewarnaan- r dari bilangan bulat lebih besar dari satu, terdapat sebuah himpunan bagian monokromatik hingga S mengenai bilangan bulat ini sehingga Dalam detail lebih lanjut, Paul Erdős dan Ronald Graham menduga bahwa, untuk r cukup besar, anggota terbesar dari S dapat dibatasi oleh b r untuk suatu tetapan b bebas dari r . Ini diketahui bahwa, untuk ini menjadi benar, b harus setidaknya tetapan Euler e . 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 b adalah paling terbesar: ini paling banyak e 167000 . Hasil Croot berikut sebagai sebuah korolari mengenai sebuah lebih banyak teorema umum menyatakan keberadaan pecahan Mesir mewakili persatuan untuk himpunan C mengenai bilangan mulus dalam selang dari bentuk [ X , X 1 + δ ] , dimana C 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 6 r , oleh karena itu, jika bilangan bulat adalah r -berwarna, pasti ada sebuah himpunan bagian monokromatik C memenuhi syarat teorema Croot.