Masalah Erdős–Graham

Dalam teori nombor gabungan, masalah Erdős–Graham ialah masalah untuk membuktikan bahawa, jika set  daripada integer yang lebih besar daripada satu dibahagikan kepada subset banyak terhingga, maka salah satu daripada subset boleh digunakan untuk membentuk perwakilan pecahan Mesir bagi perpaduan. Iaitu, untuk setiap , dan setiap  -pewarnaan integer lebih daripada satu, terdapat subset monokromatik terhingga  daripada integer ini supaya

Secara lebih terperinci, Paul Erdős dan Ronald Graham menjangkakan bahawa, untuk saiz yang cukup besar , ahli terbesar  boleh dibatasi oleh  untuk beberapa tetap  bebas daripada . Telah diketahui bahawa, untuk ini benar,  mestilah sekurang-kurangnya pemalar Euler .

Ernie Croot membuktikan sangkaan itu sebagai sebahagian daripada tesis Ph.D beliau dan kemudian (semasa penyelidik pasca kedoktoran di UC Berkeley) menerbitkan bukti dalam Annals of Mathematics. Nilai yang diberikan oleh Croot  ialah sangat besar: ia merupakan  paling banyak. Keputusan Croot berikut sebagai akibat daripada teorem yang lebih umum yang menyatakan kewujudan perwakilan pecahan Mesir bagi kesatuan untuk set  nombor licin dalam selang bentuk , di mana  mengandungi nombor yang cukup banyak sehingga jumlah salingannya ialah sekurang-kurangnya enam. Konjektur Erdős–Graham mengikuti daripada keputusan ini dengan menunjukkan bahawa seseorang boleh mencari selang bentuk ini di mana jumlah kebalikan semua nombor licin ialah sekurang-kurangnya  ; oleh itu, jika integer ialah  -berwarna mesti ada subset monokromatik  memenuhi syarat teorem Croot.

Bentuk keputusan yang lebih kukuh, bahawa mana-mana set integer dengan ketumpatan atas positif termasuk penyebut bagi perwakilan pecahan Mesir bagi satu, telah diumumkan pada 2021 oleh Thomas Bloom, seorang penyelidik pasca doktoral di Universiti Oxford.

Rujukan

Pautan luar 
 Halaman Web Ernie Croot

Kombinatorik