Nombor Graham

Nombor Graham (dinamakan sempena Ronald Graham) ialah satu nombor besar yang menjadi batas atas bagi satu permasalahan di dalam teori Ramsey.

Nombor ini mendapat perhatian yang meluas apabila Martin Gardner menyebut tentangnya di dalam Scientific American edisi November 1977 bahagian "Permainan Matematik". Dia telah menulis; "Di dalam satu bukti yang tidak diterbitkan, Graham telah mewujudkan ... satu batas yang sangat luas sehinggakan ia memegang rekod sebagai nombor yang paling besar yang pernah digunakan dalam satu pembuktian matematik serius". Guinness Book of World Records tahun 1980 menyokong dakwaan Gardner dan menambahkan lagi minat masyarakat terhadap nombor ini. Menurut ahli fizik John Baez, Graham telah mencipta satu nilai yang kini dikenali sebagai nombor Graham dalam perbualannya dengan Gardner sendiri. Apabila Graham mencuba untuk menjelaskan satu keputusan dalam teori Ramsey yang telah dia peroleh bersama rakan usaha samanya, B. L. Rothschild, Graham telah menemui bahawa nilai yang kini dikenali sebagai nombor Graham ini adalah lebih mudah untuk diterangkan daripada nombor yang sebenar yang muncul di dalam pembuktian itu. Oleh kerana nombor yang Graham terangkan kepada Gardner adalah lebih besar daripada nombor dalam kertas kerja itu sendiri, kedua-duanya adalah batas atas yang sah bagi penyelesaian masalah teori Ramsey yang dikaji oleh Graham dan Rothschild.

Nombor Graham ini tidak terkata besarnya. Ianya jauh lebih besar daripada nombor-nombor besar yang terkenal seperti googol dan googolpleks, malahan jauh lebih besar daripada nombor Skewes dan nombor Moser. Hakikatnya, jika nombor ini ditulis dalam bentuk angka dan setiap angka mengambil ruang sebanyak satu isipadu Planck, keseluruhan alam semesta yang boleh dilihat ini adalah terlalu kecil untuk menampungnya. Malahan menara kuasa dalam bentuk $\scriptstyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$ pun tidak boleh digunakan untuk menyatakannya. Dalam hal ini, notasi anak panah atas Knuth boleh digunakan untuk menyatakan nombor ini dengan mudah, seperti yang telah dilakukan oleh Graham. Sepuluh angka terakhir nombor Graham ialah ...2464195387.

Integer tertentu yang diketahui lebih besar daripada nombor Graham telah muncul di dalam pembuktian matematik serius sejak itu (contohnya, berkaitan dengan bentuk terhad pelbagai Friedman bagi teorem Kruskal).

Konteks

Nombor Graham berkaitan dengan masalah berikut dalam teori Ramsey:

Andaikan satu hiperkiub n-dimensi, dan sambungkan setiap pasang bucu untuk mendapatkan graf lengkap bagi 2ⁿ bucu. Kemudian, warnakan setiap sisi graf ini sama ada dengan warna merah atau biru.

Berapakah nilai terkecil n supaya setiap satu pewarnaan mengandungi sekurang-kurangnya satu subgraf lengkap satu warna di atas empat bucu koplanar?

Pada tahun 1971, Graham dan Rothschild membuktikan bahawa masalah ini ada penyelesaiannya, N*, dan menyatakannya dalam bentuk batas 6 ≤ N* ≤ N, di mana N ialah satu nombor yang sangat besar dan ditakrifkan sebagai $\scriptstyle N\;=\;F^{7}(12)\;=\;F(F(F(F(F(F(F(12)))))))\,\!$, di mana $\scriptstyle F(n)\;=\;2\uparrow ^{n}3\,\!$ di dalam notasi anak panah atas Knuth. Batas bawah 6 kemudiannya diperbaiki menjadi 11 oleh Geoff Exoo pada 2003 dan kepada 13 oleh Jerome Barkley pada 2008. Oleh itu, batas yang terbaik yang diketahui bagi N* ialah 13 ≤ N* ≤ N.

Nombor Graham, G, adalah lebih besar daripada N: $\scriptstyle f^{64}(4)$, di mana $\scriptstyle f(n)\;=\;3\uparrow ^{n}3$. Batas atas yang lebih lemah bagi masalah ini, yang dianggap berkaitan dengan satu kertas kerja oleh Graham, akhirnya diterbitkan dan dinamakan oleh Martin Gardner di dalam Scientific American pada November 1977.

Rujukan

Bibliografi

• Gardner, Martin (November 1977). "Mathematical Games" (PDF). Scientific American. 237: 18–28. doi:10.1038/scientificamerican1177-18.; reprinted (revised) in Gardner (2001), cited below.
• Gardner, Martin (1989). Penrose Tiles to Trapdoor Ciphers. Washington, D.C.: Mathematical Association of America. ISBN 0-88385-521-6.
• Gardner, Martin (2001). The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. New York, NY: Norton. ISBN 0-393-02023-1.
• Graham, R. L.; Rothschild, B. L. (1971). "Ramsey's Theorem for n-Parameter Sets" (PDF). Transactions of the American Mathematical Society. 159: 257–292. doi:10.2307/1996010. JSTOR 1996010. The explicit formula for N appears on p. 290. This is not the "Graham's number" G published by Martin Gardner.
• Graham, R. L.; Rothschild, B. L. (1978). "Ramsey Theory". Dalam Rota, G-C (penyunting). Studies in Combinatorics (MAA Studies in Mathematics). 17. Mathematical Association of America. m/s. 80–99. ISBN 0-88385-117-2. On p. 90, in stating "the best available estimate" for the solution, the explicit formula for N is repeated from the 1971 paper.

---

Jika anda melihat rencana yang menggunakan templat {{tunas}} ini, gantikanlah ia dengan templat tunas yang lebih spesifik.