Teoria Ramsey este un domeniu al matematicii care pune întrebări de genul următor:
Să presupunem că desenăm un anumit număr de puncte și că legăm fiecare pereche de puncte printr-o linie. Unele linii sunt albastre și altele roșii. Putem găsi întotdeauna 3 puncte pentru care cele 3 linii care le leagă sunt toate de aceeași culoare?
Se pare că, pentru această problemă simplă, răspunsul este "da" atunci când avem 6 sau mai multe puncte, indiferent de modul în care sunt colorate liniile. Dar atunci când avem 5 puncte sau mai puține, putem colora liniile astfel încât răspunsul să fie "nu".
Încă o dată, să spunem că avem niște puncte, dar acum acestea sunt colțurile unui hipercub n-dimensional. Toate sunt în continuare conectate prin linii albastre și roșii. Pentru orice 4 puncte, există 6 linii care le conectează. Putem găsi 4 puncte care se află toate pe un plan, iar cele 6 linii care le leagă sunt toate de aceeași culoare?
Cerând ca cele 4 puncte să se afle pe un plan, am îngreunat mult problema. Am dori să știm: pentru ce valori ale lui n răspunsul este "nu" (pentru un anumit mod de colorare a liniilor) și pentru ce valori ale lui n este "da" (pentru toate modurile de colorare a liniilor)? Dar această problemă nu a fost încă complet rezolvată.
În 1971, Ronald Graham și B. L. Rothschild au găsit un răspuns parțial la această problemă. Ei au arătat că pentru n=6, răspunsul este "nu". Dar când n este foarte mare, cât numărul lui Graham sau mai mare, răspunsul este "da".
Unul dintre motivele pentru care acest răspuns parțial este important este acela că înseamnă că răspunsul este în cele din urmă "da" pentru cel puțin un anumit număr mare de n. Înainte de 1971, nu știam nici măcar atât de multe.
Există o limită mult mai mică pentru aceeași problemă numită N. Aceasta este egală cu f 64 ( 4 ) {\displaystyle f_{64}(4)}
, unde f ( n ) = 3 ↑ n 3 {\displaystyle f(n)=3\uparrow ^{n}3}
. Această limită superioară mai slabă pentru această problemă, atribuită unei lucrări nepublicate a lui Graham, a fost în cele din urmă publicată și numită de Martin Gardner în Scientific American în noiembrie 1977.
