Grahamovo číslo je extrémně velké přirozené číslo, které definoval matematik Ronald Graham při řešení problému z oblasti Ramseyho teorie. Graham demonstroval, že odpověď na jeho konkrétní problém je menší než toto číslo, takže Grahamovo číslo slouží jako explicitní horní odhad pro danou úlohu.

Konkrétní Ramseyovský problém, kterému se Graham věnoval, se týká dvoubarevných obarvení hran n-rozměrného hyperkrychle (resp. souvisejícího úplného grafu na vrcholech hyperkrychle) a existence určitého typu monochromatického podgrafu (čtyřvrcholového úplného podgrafu ležícího v jedné rovině — „čtverce“). Graham ukázal, že pro dostatečně velké n musí takový podgraf existovat pro každé 2-barevné obarvení hran; Grahamovo číslo je extrémně velkým explicitním odhadem toho, jak velké to n může být. Přesná (nejmenší možná) hodnota n pro tuto úlohu zůstává neznámá a je zřejmě mnohem menší než Grahamovo číslo.

Grahamovo číslo je vytvořeno pomocí Knuthovy šipkové notace, která umožňuje kompaktně vyjádřit velmi rychle rostoucí funkce. Základní příklady této notace jsou:

  • a ↑ b = a^b (obyčejná mocnina),
  • a ↑↑ b = iterovaná mocnina (tetrace), tj. a^(a^(...^a)) s b výskyty a,
  • vyšší počty šipek značí dál exponenciální iteraci na stále vyšší úrovni růstu.

Definice Grahamova čísla (ve zjednodušeném popisu) se dává rekurentně takto: nejprve se vezme

g1 = 3 ↑↑↑↑ 3 (trojka se čtyřmi šipkami mezi trojkami). Poté pro každé n ≥ 1 platí

gn+1 = 3 se gn šipkami 3 (tedy mezi dvěma trojkami je počet šipek roven předchozí hodnotě gn). Nakonec se definuje Grahamovo číslo jako

G = g64.

Tato konstrukce vede k číslu, které je zcela mimo intuici: G je mnohonásobně větší než běžné „velké“ čísla jako googol nebo googolplex, mnohonásobně větší než počet atomů v pozorovatelném vesmíru; i kdybychom každou cifru zapsali nejmenším čitelným písmem, desetinné vyjádření by se stále nikdy nevešlo do pozorovatelného vesmíru. Přesto lze některé vlastnosti Grahamova čísla rozhodnout — například pomocí modularních výpočtů je možné spočítat několik posledních číslic jeho desetinného zápisu — celkové desítkové vyjádření je však nemožné uvést v běžné notaci.

Je důležité zdůraznit, že Grahamovo číslo nebylo navrženo jako tvrzení, že hledané n v původním problému má právě tuto hodnotu; jde o velmi konzervativní horní odhad. Pozdější práce a zlepšení metod výrazně snížily horní odhady pro podobné problémy, takže skutečné minimální n je pravděpodobně mnohem menší než G. Přesto Grahamovo číslo zůstává významným příkladem toho, jak rychle může růst matematicky definovaná funkce, a slouží jako ilustrace a výukový prostředek při vysvětlování velkých čísel a notací jako Knuthovy šipky.

Pro úplnost: existují i jiné matematicky definované objekty a postupy (například funkce typu Busy Beaver nebo některé hladce definované kombinatorické funkce jako TREE(3)), které vedou k číslům rostoucím ještě mnohem rychleji než Grahamovo číslo; to ukazuje, že „velikost“ čísel v matematice může překročit i velmi silnou intuici o tom, co je „velmi velké“.