I ricercatori Jacques Verstraete, dell’Università della California, San Diego, e Sam Mattheus, della Libera Università di Bruxelles, hanno risolto il problema matematico di Ramsey o r(4,t) che ha lasciato perplessi i matematici di tutto il mondo dagli anni ’70.
Festa con gli ospiti
Il problema di Ramsey più noto e più semplice è il cosiddetto “teorema di amici e sconosciuti”. Per capirlo dobbiamo immaginare una festa in cui consideriamo quante persone invitare con una determinata condizione. Questo può essere scritto come ‘r(s,t)’; dove ‘r’ è il numero minimo di persone necessarie alla festa in modo che le ‘persone’ si conoscano o ‘t’ non siano completamente estranee tra loro.
La risposta a r(3,3) è molto semplice, poiché è uguale a 6. ‘È un fatto naturale, una verità assoluta’, dice Verstraete. ‘Non importa quale sia la situazione o quali sei persone sceglierai: troverai tre persone che si conoscono o tre persone che non si conoscono. Potresti trovarne di più, ma ti garantiamo che ce ne saranno almeno tre in una cricca o nell’altra’, aggiunge il matematico.
Teoria applicata alla grafica
Nel linguaggio matematico, ai grafici si applica il teorema di Ramsey, r(s,t): dove ‘s’ sono i punti uniti da linee e ‘t’ sono i punti non collegati da linee che possiamo trovare all’interno di qualsiasi grafico. La teoria di Ramsey afferma che è sicuro trovare una sorta di ordine all’interno di un grafico sufficientemente grande, sia che si tratti di un insieme di punti (cricche) senza linee tra loro o di un’altra cricca unita da tutte le possibili linee tra loro.
La soluzione di r(4,4) è 18 ed è dimostrata utilizzando un teorema creato dai matematici Paul Erdös e George Szekeres nel 1930. I problemi di Ramsey con più elementi sono semplici da enunciare, ma le possibili soluzioni sono quasi infinite. Attualmente la soluzione di r(5,5) è ancora sconosciuta. Gli esperti suggeriscono che, se supponiamo che la risposta sia 45 punti, dovremmo considerare un numero di grafici praticamente assurdo, equivalente a un 1 seguito da 234 zeri.
‘Poiché questi numeri sono molto difficili da trovare, i matematici cercano delle stime’, ha spiegato Verstraete. ‘Questo è ciò che Sam e io abbiamo realizzato nel nostro recente lavoro. Come possiamo trovare non la risposta esatta, ma le migliori stime di quali potrebbero essere questi numeri di Ramsey?’
Premio a chi risolve
Il problema r(4,t) è una congettura di Erdös, che offrì 250 dollari alla prima persona che fosse riuscita a risolverlo. Verstraete vide per la prima volta il problema in un libro scritto da due professori dell’UC San Diego, Fan Chung e il compianto Ron Graham. ‘Molte persone hanno pensato a r(4,t); è un problema aperto da più di 90 anni’, ha osservato Verstraete. Per risolvere un annoso problema di Ramsey era necessario un grafico pseudocasuale di geometria finita, chiamato ‘configurazione di O’Nan’.
Se vuoi una festa in cui ci saranno sempre quattro persone che si conoscono o ‘t’ persone che non si conoscono, avrai bisogno di un numero di persone presenti approssimativamente pari a ‘t’ al cubo. L’articolo è attualmente in fase di revisione in Annals of Mathematics e il suo archivio di prestampa è su arXiv.
Perseverare
‘Ci sono voluti davvero anni per capirlo’, ha detto Verstraete. ‘E ci sono state molte volte in cui siamo rimasti bloccati e ci chiedevamo se saremmo riusciti a trovare una soluzione. Ma non bisogna mai arrendersi, non importa quanto tempo ci vorrà’, ha sottolineato. ‘Se trovi che il problema è difficile e sei bloccato, significa che è un buon problema. Fan Chung ha detto che un buon problema si difende. Non puoi aspettarti che si manifesti semplicemente’, ha sottolineato. ‘Ho ricevuto una chiamata da Fan dicendomi che mi deve $ 250’, ha aggiunto il matematico.