Graham's getal

Het getal van Graham is de bovenlimiet voor de Ramsey-theorie. De probleemstelling is als volgt: Stel je een n-dimensionale hyperkubus voor en verbind de knooppunten zodat er een complete graaf ontstaat. Een graaf is een verbinding van punten, een complete graaf is een graaf waarbij alle punten met alle andere punten zijn verbonden.

Beschilder vervolgens elke kant in deze graaf in één van twee kleuren. Wat is de kleinste waarde van n waarvoor elk van de mogelijke beschilderingen ten minste één complete planaire subgraaf van vier knooppunten bevat met alle kanten van dezelfde kleur? Het getal is gedefinieerd door Ronald Graham in 1977. Het getal is het grootste getal dat in een serieus wiskundig bewijs is gebruikt en het staat zo vermeld in het Guinness Book of Records.

Definitie van het getal

G(0) = 4

G(1) = $3\uparrow ^{G(0)}3$ = $3\uparrow^43$

G(n) = $3\uparrow ^{G(n-1)}3$

G(64) = het getal van Graham

Ramsey-theorie

De oplossing van de ramsey-theorie is nog steeds niet bekend, de beste grenzen tot nu toe zijn: $13\leq n\leq 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 9$ waar n de oplossing van de ramsey-theorie is.

Bronnen

Sbiis Saibian's artikel over het Getal van Graham