Grahamin luku

Grahamin luku on Ronald Grahamin päättelemä erittäin suuri luku, johon usein viitataan suurimpana matemaattisen todistuksen lukuna. Tämä tarkoittaa sitä, että Grahamin luku oli suurin luku, joka esiintyy matemaattisessa todistuksessa tietyn ongelman eksplisiittisenä rajana. Graham päätyi lukuun etsiessään todistusta Ramseyn lauseen erääseen ongelmaan.
Sittemmin on löydetty sitäkin isompia lukuja, mutta Grahamin luku on silti suurin omalla nimellä tunnettu luku.
Ongelma.
Ramseyn lauseessa kysytään muun muassa:
Oletetaan että piirrämme joitain pisteitä ja yhdistämme jokaisen pisteen toiseen viivalla, jonka väritämme punaiseksi tai siniseksi. Voimmeko löytää 3 pistettä, joiden 3 viivaa ovat kaikki samanvärisiä?
Tämän ongelman vastaus on "kyllä", jos pisteitä on 6 tai enemmän.
Grahamin luku tulee vastauksena kysymyksen variaatioon:
Meillä on "n"-ulottuvuuden hyperkuutio, jonka kaikki pisteet yhdistetään samoin punaisella tai sinisellä viivalla. Onko olemassa 4 samalla tasolla olevaa pistettä, joiden kaikki 6 linjaa ovat samanvärisiä? 
("Once again, say we have some points, but now they are the corners of an n-dimensional hypercube. They are still all connected by blue and red lines. For any 4 points, there are 6 lines connecting them. Can we find 4 points that all lie on one plane, and the 6 lines connecting them are all the same color?")
Ongelma voidaan esittää myös seuraavasti:
Laske kaikki tavat, joilla "n"-ulottuvuuden hyperkuution kaikki linjat voidaan värittää kahdella eri värillä. Tuloksena on Grahamin luku.
("Take an N-dimensional cube, and count the number of ways you can color all of it's lines using red and blue. Obviously there must be more ways to color the lines than there are lines, right?! Not so: Take a Graham's Dimensional hyper-cube and there are just as many lines as there are ways to color them! Graham's Number is the smallest number with this property.")
Vuonna 1971 Ronald Graham ja B. L. Rothschild löysivät osittaisen vastauksen tähän ongelmaan: "N*", jonka rajat ovat 6 ≤ "N*" ≤ "N", missä yläraja "N" on suuri, mutta äärellinen luku, Grahamin luku "G":
formula_1,
missä
formula_2 
Knuthin nuolinotaatiolla.
Yläraja saatiin alennettua 2013 Hales–Jewettin luvulla formula_3.
Alarajan sai Geoff Exoo vuonna 2003 parannettua 6:sta 11:een, ja Jerome Barkley vuonna 2008 13:een. Niinpä "N*":n raja-arvot ovat tällä hetkellä (2013) 13 ≤ "N*" ≤ "N"'.
Määritelmä.
Grahamin lukua ei voi esittää tavanomaisilla matemaattisilla operaattoreilla. Jopa sen esittäminen potenssikorotuksella (muodossa formula_4) on epäkäytännöllistä. Sen sijaan käytetään Knuthin nuolinotaatiota.
Määritellään
formula_5
formula_6
missä formula_7 vastaa formula_8 nuolta, joten Grahamin luku formula_9 on:
formula_10
Viimeinen numero.
Luvun 500 viimeistä numeroa ovat:
 …02425950695064738395657479136519351798334535362521
 43003540126026771622672160419810652263169355188780
 38814483140652526168785095552646051071172000997092
 91249544378887496062882911725063001303622934916080
 25459461494578871427832350829242102091825896753560
 43086993801689249889268099510169055919951195027887
 17830837018340236474548882222161573228010132974509
 27344594504343300901096928025352751833289884461508
 94042482650181938515625357963996189939679054966380
 03222348723967018485186439059104575627262464195387
Graham itse laski viimeisen numeron vuonna 1977 olevan juuri "7". Kukaan ei ole pystynyt laskemaan mikä on luvun ensimmäinen numero.
Jos Grahamin luku kirjoitettaisiin siten, että yksi numero veisi yhden Planckin tilavuuden eli 4,22 x 10-105 m3 (kvanttifysiikan mukaan pienin mahdollinen tilavuus), se ei mahtuisi havaittavaan maailmankaikkeuteen. Luvun suuruutta kuvaa se, että pelkästään "nuolten" määrä tasolla g1 (= 3↑↑↑↑3) on suurempi kuin Planckin tilavuuksien lukumäärä havaittavassa maailmankaikkeudessa (noin 10185).
Grahamin luku mainitaan Guinnessin ennätysten kirjassa suurimpana matemaattisessa todistuksessa käytettynä lukuna.