“Capirai”.
“Eh, è nella loro natura. Si sono posti quindi questa domanda: se su un grafo formato dai lati e dalle diagonali di un esagono si trova sempre un triangolo monocromatico, che succede con un pentagono? Un quadrilatero? Qual è il numero minimo di vertici che deve avere un grafo completo affinché, colorando i suoi spigoli con due colori, si possa essere certi di formare sempre un triangolo monocromatico?”.
“Beh, certamente non più di 6, no?”.
“Infatti. Se riusciamo a trovare un triangolo che ci piace in un grafo con 6 vertici, aumentando i vertici aumentano anche gli spigoli, e quindi aumentano le possibilità di trovare triangoli monocromatici”.
“Quindi la domanda diventa: potrebbe essere 5, o meno ancora?”.
“Ed ecco la risposta:”.
“Uhm. Un pentagono”.
“Un pentagono con 5 spigoli colorati di rosso e 5 colorati di blu. Osservalo bene: ci sono triangoli monocromatici?”.
“Eh, no”.
“Quindi esiste almeno una colorazione di questo grafo che non produce triangoli monocromatici”.
“E quindi la nostra ricerca è finita: il numero minimo di vertici per avere i triangoli monocromatici è 6. Ottimo, fine della generalizzazione”.
“Non c’è mai fine alle generalizzazioni”.
“Capirai”.
“Per esempio: troverò triangoli anche se uso tre colori? Quattro? Di più?”.
“Ah. Non sembra facile”.
“Non lo è. Ma si può generalizzare anche in un altro modo: posso colorare con 2 colori in modo da trovare triangoli del primo o quadrati del secondo?”.
“Uh, che delirio”.
“E trovare le risposte a queste domande è difficilissimo. Anzi, alcune di queste risposte non le conosciamo ancora”.
“Davvero?”.
“Eh, sì. Il numero che abbiamo calcolato poco fa, il minimo numero di vertici che deve avere un grafo perché si possa sempre trovare al suo interno un triangolo blu o un triangolo rosso, si chiama numero di Ramsey per tre rosso e tre blu, e si indica con R(3,3). Erdős ha detto, una volta: supponete che gli alieni invadano la Terra e che minaccino di annientarla se entro un anno gli uomini non riusciranno a trovare il numero di Ramsey per cinque rosso e cinque blu. Potremmo far scendere in campo le menti migliori e i calcolatori più veloci del pianeta e probabilmente entro un anno riusciremmo a calcolare quel valore. Se tuttavia gli alieni volessero il numero di Ramsey per sei rosso e sei blu. non avremmo altra scelta se non un attacco preventivo.”.
“Eh eh, non credevo fosse così difficile”.
“Lo è, eccome se lo è. I matematici sono riusciti a dimostrare che un numero di Ramsey esiste sempre, qualunque sia il numero di colori e il numero di lati da colorare. Il problema è che non sappiamo quali siano, questi numeri, se non in pochi casi”.
“Ma pensa”.
“Già: per quanto riguarda il famoso R(5,5) di Erdős, nel 1989 si è scoperto che questo numero deve essere almeno 43. Mentre nel 2017, l'anno scorso, si è capito che non può essere più grande di 48”.
“Una scoperta recentissima!”.
“Eh, sì. E, dato che fregiarsi del titolo di potenziale salvatore dagli alieni dovrebbe essere uno stimolo enorme per un Vero Matematico, puoi renderti conto della difficoltà del problema”.
“Quindi di pensare a risolvere R(6,6) non se ne parla proprio, suppongo. Meglio sviluppare la tecnologia per combattere gli alieni?”.
“Le ultime stime per R(6,6) sono del 1965. Da allora, nessuno è riuscito a fare meglio. Sappiamo solo che R(6,6) è un numero compreso tra 102 e 165”.
“Eppure non sono numeri così grandi, come è possibile che non si riescano a migliorare le stime?”.
“Ricordati che i numeri di cui stiamo parlando sono i vertici. Sai quanti spigoli ha un grafo completo con 100 vertici?”.
“Eh, al momento no...”.
“Prova a pensare: quanti spigoli partono da ogni vertice?”.
“Eh, direi 99, uno per ogni vertice, tranne quello da cui parto”.
“E dato che ci sono 100 vertici...”.
“Ho 100×99 spigoli?”.
“Non esattamente. In questo modo, ogni spigolo verrebbe contato due volte, una per il vertice di partenza e una per quello di arrivo”.
“Ah, allora devo dividere per due il risultato!”.
“Già. Quindi un grafo con 100 vertici ha 50×99 spigoli, cioè 4950”.
“Anche questo non è un numero così esagerato, magari con un computer si può fare qualche stima, no?”.
“Eh, sai quante possibili colorazioni si possono fare, anche soltanto con due colori?”.
“Uhm, non saprei come calcolarle”.
“Non è difficile: per ogni spigolo hai due scelte, o lo colori di blu o di rosso. Quindi due scelte per il primo spigolo, moltiplicate per altre due scelte per il secondo, e così via”.
“Gulp, devo moltiplicare 2 per sé stesso 4950 volte”.
“Esatto. Un numero composto da 1491 cifre. Se passi a un grafo con 120 vertici ti risulta un numero di configurazioni da provare composto da 2150 cifre”.
“Comincia a diventare lunghetta”.
“E non è finita: in ognuna delle configurazioni devi cercare degli esagoni”.
“Argh”.
“In un grafo completo sei vertici scelti a caso sono sempre collegati da sei spigoli, quindi per calcolare il numero di esagoni ti basta calcolare il numero di possibili scelte di sei vertici”.
“E come faccio?”.
“Beh, il primo vertice lo puoi scegliere in 100 modi diversi, il secondo in 99, il terzo in 98, e così via, fino al sesto vertice, che puoi scegliere in 95 modi. In realtà queste scelte non sono tutte diverse, puoi mescolare i sei lati in 6! modi, come se fossero le lettere di un anagramma”.
“Totale: 100×99×98×97×96×95. Poi divido per il fattoriale di 6, vediamo… fa 1 miliardo e rotti. E dovrei controllarli tutti per ognuno dei grafi? Roba da matti”.
“Come vedi, non esiste ancora la potenza di calcolo necessaria per poter affrontare questo problema con la forza bruta. Meglio attaccare gli alieni”.
“Ma allora come hanno fatto a fare quelle stime di cui parlavi? ”.
“Erdős è stato il primo a farle, e ha escogitato un metodo che, a prima vista, è spiazzante. I Veri Matematici lo chiamano metodo probabilistico”.
“Uhm, usa la probabilità? Si può dimostrare un teorema con considerazioni di probabilità? Mi pareva che i teoremi dessero certezze”.
“Eh, è proprio per questo che il metodo è spiazzante: Erdős ha usato la probabilità per arrivare a una vera dimostrazione”.
“Uh”.
“Erdős partiva da questa idea: supponiamo di colorare gli spigoli di un grafo in maniera casuale, tirando una moneta. Se viene testa coloro lo spigolo di rosso, se viene croce lo coloro di blu”.
“Va bene”.
“Ora, supponiamo di voler fare una stima dal basso di R(34,34)”.
“Un numero impossibile da calcolare, se già R(6,6) è intrattabile”.
“Esattamente: questo esempio serve per capire la potenza del metodo probabilistico. Ci chiediamo, ad esempio, se un grafo con un milione di vertici potrebbe essere sufficiente per garantire la presenza di poligoni di 34 lati monocromatici”.
“Mi immagino il disegno”.
“Eh eh. Ora, un grafo completo con 34 vertici ha 561 spigoli”.
“Vediamo se ho capito: per ogni spigolo posso scegliere il primo vertice in 34 modi, e il secondo in 33, però così facendo conto gli spigoli due volte, quindi dopo aver moltiplicato 34 per 33 devo dividere per 2. Sì, risulta 561”.
“Esattamente. Ora la probabilità che questi 561 vertici siano tutti dello stesso colore”.
“Ho probabilità un mezzo per ogni lato, quindi dovrebbe essere (1/2)561”.
“Bene, però i colori sono due”.
“Quindi moltiplico per due, e mi viene (1/2)560”.
“Ok. Quanti poligoni di 34 lati abbiamo in un grafo di un milione di vertici?”.
“Oh, tanti. Avevamo visto che già il calcolo con 100 dava un numero molto grande”.
“Eh, sì. Procedendo allo stesso modo, risulta che il numero di combinazioni è circa 3×10165. A questo punto, possiamo chiederci quanto vale la probabilità di trovare un poligono di 34 lati monocromatico”.
“Devo moltiplicare la probabilità che un singolo poligono sia monocromatico con il numero dei poligoni, no?”.
“Vero”.
“Quindi devo moltiplicare (1/2)560 per 3×10165”.
“Quanto viene?”.
“Poco meno di un millesimo”.
“Non importa il valore esatto, ciò che conta è che il risultato sia minore di 1”.
“Perché?”.
“Perché se tutte le possibili colorazioni di spigoli contenessero poligoni di 34 lati monocromatici, allora questa probabilità dovrebbe essere uguale a 1”.
“Ah, vero: avremmo la certezza di trovare un poligono monocromatico”.
“Dunque, se la probabilità è minore di uno, ciò significa che esiste almeno una colorazione che non ci dà poligoni monocromatici”.
“E quindi?”.
“E quindi un milione di vertici sono troppo pochi: abbiamo trovato una limitazione inferiore per R(34,34)”.
“Ah. Non è stato così difficile”.
“Per questo il metodo è potente: permette di capire qualcosa in un universo di calcoli proibitivi”.
“Ordine nel caos”.
“Proprio così. Come disse il matematico Theodore Motzkin descrivendo la teoria di Ramsey: complete disorder is impossible”.
Questa è la seconda parte di un articolo uscito sulla rivista Archimede, numero 4, del 2017. La prima parte è qua.
Nessun commento:
Posta un commento