Grahamov broj je najveći broj sa imenom koji ima primenu i najveći broj ikada korišćen za rešavanje nekog matematičkog problema. Taj broj, nazvan po američkom matematičaru Ronaldu Grejamu (Ronald Graham, 1935–2020), nije transcendentan i, iako je nezamislivo velik, ima konačnu vrednost. Nije ga moguće zapisati (prostor potreban za zapisivanje Grahamovog broja prevazilazi kapacitet vidljivog svemira), njegovo direktno izračunavanje je nemoguće, a čak je nemoguće i zapisati kako bi proračun tog broja trebalo da izgleda. Međutim, korišćenjem konvergentnih svojstava power towers moguće je izračunavanje cifara Grahamovog broja unazad. Na primer, poslednjih deset cifara tog broja su 2464195387.
Grahamov broj se koristi u oblasti kombinatorike poznatoj kao Remzijeva teorija (proučavanje uslova pod kojim se pojavljuje neki red), nazvanoj po britanskom matematičaru Frenku P. Remziju (1903–1930). Osnovno pitanje Remzijeve teorije jeste: koji je najmanji skup koji mora sadržati dati podskup? Najjednostavniji primer bio bi: koliko ljudi je neophodno da bi najmanje dvoje od njih bilo istog pola? Odgovor je da će u grupi od troje ljudi najmanje dvoje biti istog pola.
Grahamov broj predstavlja gornju granicu rešenja matematičkog problema koji se odnosi na dvobojne n-dimenzionalne hiperkocke. Konkretno, sva geometrijska temena n-dimenzionalne hiperkocke međusobno treba spojiti tako da se dobije kompletan graf (u matematičkoj oblasti teorije grafova, kompletan graf predstavlja jednostavan grafikon u kojem je svaka tačka spojena sa drugom tačkom pomoću linije (ivice); ako je broj tačaka m, tada je broj ivica m · (m − 1) / 2). Svaku ivicu tog grafa treba obojiti ili crvenom ili plavom bojom. Kolika je najmanja vrednost n za koju svako takvo bojenje sadrži najmanje jedan jednobojni kompletan podgraf sa četiri temena u istoj ravni? Drugačije rečeno, koliko mora biti n da se mogu naći četiri tačke koje leže u jednoj ravni, a da je svih šest linija koje ih spajaju iste boje?
Donja granica koju je Grejam postavio jeste 6 dimenzija, dok je gornja granica Grahamov broj. Niko, uključujući i Grejama, ne veruje da je odgovor i približno toliko velik. Grejam je taj problem rešio 1971. godine, a Grahamov broj privukao je pažnju javnosti u novembru 1977. godine, kad je o njemu pisano u američkom naučnom časopisu Scientific American. Godine 2008. dokazano je da je donja granica 13, uz sugestije da je možda i veća.
Primer određivanja donje granice
Na slici ispod prikazana je dvobojna trodimenzionalna kocka koja sadrži jedan jednobojni kompletan podgraf sa četiri temena u jednoj ravni koje spajaju plave linije. Taj podgraf je prikazan ispod kocke. Ovde se može videti da ta kocka ne bi sadržala nijedan takav podgraf ako bi se, na primer, donja desna plava ivica u datom podgrafu zamenila crvenom ivicom. To dokazuje da je donja granica za n sigurno veća od 3.
Zapisivanje Grahamovog broja
Grahamov broj je neshvatljivo velik i čak ga je nemoguće opisati pomoću konvencionalnih numeričkih tehnika. Međutim, postoji jedan relativno lak način za njegovo predstavljanje, a to je pomoću rekurzivne formule koja koristi Knutovu notaciju (način zapisivanja velikih brojeva pomoću strelica). Da bi se taj broj opisao i zapisao potrebna je specijalna notacija koju je, 1976. godine, smislio američki matematičar i profesor Donald Knut. Grahamov broj se pomoću Knutove strelične notacije izražava na sledeći način:
1. korak: 3 ↑ 3 = 33 = 27
2. korak: 3 ↑↑ 3 = 3 ↑ (3 ↑ 3) = 327 = 7625597484987
3. korak: 3 ↑↑↑ 3 = 3 ↑↑ (3 ↑↑ 3) = 3 ↑↑ 7625597484987 = 3 ↑ (7625597484987 ↑ 7625597484987) (već je taj broj veći od ukupnog broja atoma u svemiru)
4. korak: 3 ↑↑↑↑ 3 = 3 ↑↑↑ (3 ↑↑↑ 3)
Odavde počinje postupak izračunavanja Grahamovog broja (ukupno 64 koraka):
g1: 3 ↑↑↑↑ 3
g2: 3 (g1 strelica) 3
g3: 3 (g2 strelica) 3
…
…
…
g64: 3 (g63 strelica) 3 = G
I to je Grahamov broj.
Ili, zapisano pomoću Conway chained arrow notation:
3 → 3 → 64 → 2 < G < 3 → 3 → 65 → 2