Don't take life too seriously: it's just a temporary situation

Graham (numero di)

Teoria dei grafi  Vari 

Il numero di Graham è un intero talmente enorme che non può essere rappresentato neppure in notazione esponenziale, ma necessita di 64 livelli di una particolare notazione inventata da Donald Ervin Knuth (v. numeri di Ackermann) e anche così è ingombrante: si scrive, infatti, come:

3 ↑↑↑↑↑ ... 3, dove il numero di frecce è

3 ↑↑↑↑↑ ... 3, dove il numero di frecce è

3 ↑↑↑↑↑ ... 3, dove il numero di frecce è

... in tutto 63 righe uguali ...

3 ↑↑↑↑ 3, dove il numero di frecce è 4.

 

Come il numero di Skewes, questo è solo un limite superiore, entro il quale Ronald L.Graham e B.L Rothschild, dimostrarono nel 1971 che deve trovarsi la soluzione di un problema di teoria dei grafi, semplice da enunciare, ma arduo da risolvere.

 

In realtà il limite dimostrato da Graham e Rothschild è minore, ma nel descrivere la sua dimostrazione a Martin Gardner, Graham uso il valore riportato, perché più facile da descrivere e Gardner lo riportò così nel numero di Novembre 1977 di Scientific American (pubblicato nel numero di Marzo 1978 nell’edizione italiana). Il numero venne ripreso e citato da altri Autori e divenne famoso in questa forma, col nome “numero di Graham”. Anche il limite effettivamente dimostrato da Graham e Rothschild è comunque spaventosamente superiore a ogni altro numero utilizzato in precedenza in una dimostrazione matematica.

 

Il numero non può essere nemmeno rappresentato con una torre di esponenti come Rappresentazione di un numero mediante una torre di esponenti, almeno non nei limiti stimati per l’universo, neppure usando elettroni come cifre; possiamo però calcolarne un numero grande a piacere di cifre e sappiamo che termina con ...2464195387.

 

Il problema affrontato da Graham è un caso particolare della teoria di Ramsey, che include problemi come il seguente: quante persone devono esserci in una stanza, perché se ne possa sempre trovare un gruppo di 3, tali che ciascuna conosca tutte le altre o ciascuna non conosca nessuno degli altri?

Nella teoria dei grafi il problema consiste nel disegnare n punti sul piano e connettere ciascun punto a tutti gli altri con linee tracciate in uno o l’altro di due colori: quanti devono essere i punti, perché debba esistere per forza un grafo completo di 3 punti (ossia un triangolo) disegnato con lo stesso colore?

La risposta in questo caso è facile: 6. Se però il gruppo richiesto deve avere 4 membri, le cose si complicano: servono 18 persone e la dimostrazione non è semplice. Se richiediamo un gruppo di 5 persone, dobbiamo iniziare con un numero ancora sconosciuto, ma compreso tra 43 e 49, mentre per un gruppo di 6 la risposta sta tra 102 e 165.

Se vogliamo garantire la presenza di 4 conoscenti o 5 estranei, dobbiamo avere 25 persone, come fu dimostrato nel 1993 con l’aiuto di una schiera di calcolatori.

Solo pochissimi problemi di questo genere sono stati risolti e per pochi altri si conosce una ragionevole approssimazione della risposta, anche se la teoria di Ramsey ci assicura che esiste sempre una risposta.

 

Il caso considerato da Graham e Rothschild è leggermente diverso: supponiamo che un certo numero di persone formino comitati, in tutti i modi possibili; due differenti comitati possono riconoscersi a vicenda o meno: è possibile che esista per forza un gruppo di 4 comitati che si riconoscono tutti a vicenda o che non si riconoscono e tali che tutte le persone appartengano a un numero pari di comitati?

Espresso nella teoria dei grafi, il problema consiste nello stabilire se il grafo completo di un ipercubo a n dimensioni (ogni vertice connesso a ogni altro), con ogni linea colorata in uno di due colori, contiene un grafo completo di 4 punti, colorato tutto con lo stesso colore, che giaccia in un piano.

Graham e Rothschild dimostrarono che se n è abbastanza grande, il grafo risultante contiene per forza un sottografo planare di 4 punti, connessi tra loro da 6 linee tutte dello stesso colore. Resta il problema di determinare il minimo valore di n tale che il sottografo planare monocromatico debba esistere.

Il limite superiore indicato da Graham e Rothschild è però inimmaginabilmente grande e, come nel caso del numero di Skewes, gli esperti stanno cercando di ridurlo, anche perché l’opinione corrente è che la soluzione sia un numero molto più trattabile. Graham e Rothschild dimostrarono che il limite inferiore è 6 e per un certo periodo gli esperti credetto che questa fosse la soluzione del problema. Nel 2003 Geoff Exoo dimostrò però che la soluzione è almeno 11 e nel 2008 Jerome Barkley portò il limite inferiore a 13.

Come osservò Ulam: “Con l’infinito ce la sbrighiamo in fretta, il finito può richiedere un po’ più di tempo.”

 

Per 25 anni il numero di Graham è stato considerato il più grande numero mai utilizzato in una dimostrazione matematica; ha strappato questo primato al numero di Langevin nel 1977.

Nel 2002 ha perso il titolo, perché Harvey Friedman nel trattare alcuni problemi di enumerazione di alberi utilizzò numeri ancora maggiori, talmente grandi da avere bisogno di un’altra notazione per essere rappresentati.

Bibliografia

  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 115, marzo 1978, pag. 108 – 113.
  • Gardner, Martin;  The Colossal Book of Mathematics, New York, W.W. Norton & Company, 2001.
  • Gardner, Martin;  The Colossal Book of Short Puzzles and Problems, New York, W.W. Norton & Co., 2006.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.