Ramsey-theorie is een tak van de wiskunde die vragen stelt als de volgende:
Stel dat we een aantal punten tekenen, en elk paar punten verbinden door een lijn. Sommige lijnen zijn blauw en andere rood. Kunnen wij altijd 3 punten vinden waarvoor de 3 lijnen die hen verbinden allemaal dezelfde kleur hebben?
Het blijkt dat voor dit eenvoudige probleem het antwoord "ja" is wanneer we 6 of meer punten hebben, ongeacht de kleur van de lijnen. Maar als we 5 punten of minder hebben, kunnen we de lijnen zo kleuren dat het antwoord "nee" is.
Nogmaals, stel dat we een aantal punten hebben, maar nu zijn het de hoeken van een n-dimensionale hyperkubus. Ze zijn nog steeds verbonden door blauwe en rode lijnen. Voor elke 4 punten zijn er 6 lijnen die ze verbinden. Kunnen we 4 punten vinden die allemaal op één vlak liggen, en waarvan de 6 lijnen die ze verbinden allemaal dezelfde kleur hebben?
Door te vragen dat de 4 punten op een vlak liggen, hebben we het probleem veel moeilijker gemaakt. Wij zouden graag willen weten: voor welke waarden van n is het antwoord "nee" (voor sommige manieren om de lijnen te kleuren), en voor welke waarden van n is het "ja" (voor alle manieren om de lijnen te kleuren)? Maar dit probleem is nog niet helemaal opgelost.
In 1971 vonden Ronald Graham en B. L. Rothschild een gedeeltelijk antwoord op dit probleem. Zij toonden aan dat voor n=6 het antwoord "nee" is. Maar als n heel groot is, zo groot als Grahams getal of groter, is het antwoord "ja".
Een van de redenen waarom dit gedeeltelijke antwoord belangrijk is, is dat het betekent dat het antwoord uiteindelijk "ja" is voor ten minste enkele grote n. Vóór 1971 wisten we niet eens zoveel.
Er is een veel kleinere limiet voor hetzelfde probleem, genaamd N. Deze is gelijk aan f 64 ( 4 ) {{displaystyle f_{64}(4)}
, waarbij f ( n ) = 3 ↑ n 3 {{displaystyle f(n)=3}
. Deze zwakkere bovengrens voor het probleem, toegeschreven aan een ongepubliceerd werk van Graham, werd uiteindelijk gepubliceerd en benoemd door Martin Gardner in Scientific American in november 1977.
