Il disturbo persiste in grafici più grandi, nuovi reperti matematici
Dopo oltre 70 anni di intransigenza, uno dei numeri più ostinati in matematica è finalmente cambiato.
In una bozza di quattro pagine pubblicata alla fine di settembre, David Conlon e Asaf Ferber hanno fornito la stima più precisa finora per i "numeri Ramsey multicolori", che misurano quanto possono diventare grandi i grafici prima che mostrino inevitabilmente certi tipi di schemi.
"Non c'è assoluta casualità in questo universo", ha detto Maria Axenovich del Karlsruhe Institute of Technology in Germania. "Ci sono sempre gruppi di ordini e i numeri di Ramsey lo quantificano."
I grafici sono raccolte di punti (vertici) collegati da linee (bordi). I matematici sono particolarmente interessati a capire quanti vertici e spigoli possono contenere prima che diversi tipi di sottostrutture emergano al loro interno.
"Se si dispone di un grafico abbastanza grande, una gran parte di esso è ben ordinata", ha affermato Maria Chudnovsky della Princeton University. "È difficile spiegare perché qualcosa è bello, ma c'è un accordo universale sul fatto che questo è un bellissimo fenomeno."
I numeri di Ramsey riguardano un particolare motivo chiamato cricca monocromatica, che è un insieme di vertici che sono tutti collegati tra loro da bordi dello stesso colore dopo aver eseguito una procedura di colorazione specifica.
I numeri di Ramsey variano a seconda delle dimensioni della cricca che stai cercando e del numero di colori che usi per eseguire la colorazione. I matematici non possono calcolare la maggior parte dei numeri di Ramsey perché tutti i grafici tranne i più piccoli sono troppo complessi per essere analizzati direttamente.
Di solito, il miglior matematico che può fare è impostare un intervallo di valori possibili per i numeri di Ramsey. È come se volessi conoscere la posizione di un amico ma potessi solo determinare con certezza che si trova a nord di Miami ea sud di Philadelphia.
La nuova dimostrazione fa di più per concentrarsi sul valore esatto dei numeri di Ramsey di qualsiasi risultato da quando Paul Erdős li studiò per la prima volta negli anni '30 e '40. Conlon, del California Institute of Technology, e Ferber, dell'Università della California, Irvine, hanno trovato un nuovo "limite inferiore" per i numeri di Ramsey multicolore che è esponenzialmente più preciso della precedente migliore stima. Il loro risultato fornisce ai matematici una nuova comprensione dell'interazione tra ordine e casualità nei grafici, che sono di fondamentale interesse per la matematica.
"Questo è un risultato fantastico", ha detto Axenovich. "Lo adoro."
Collegamenti colorati
I numeri di Ramsey, che furono introdotti dal poliedrico britannico Frank Ramsey negli anni '20, sono meglio compresi con l'esempio. Inizia con un grafico con cinque vertici. Collega ciascuno di essi a tutti gli altri per formare quello che i matematici chiamano un grafico completo. Ora, puoi colorare ogni bordo rosso o blu senza creare un insieme di tre vertici che sono tutti collegati tra loro da bordi dello stesso colore? La risposta è: puoi.
Ma inizia con un grafo completo di sei vertici e ora non c'è modo di colorare i bordi con due colori senza creare una cricca monocromatica di almeno tre vertici. O, per dirla in un altro modo, per due colori e una cricca di dimensione 3, il numero di Ramsey è 6 (poiché richiede un grafo completo di sei vertici).
I numeri di Ramsey variano a seconda del numero di colori e delle dimensioni della cricca monocromatica che stai cercando. Ma in generale, sono difficili da calcolare esattamente ei matematici conoscono i valori esatti solo per un piccolo numero di situazioni. Anche per piccole cricche di taglia 5 (e due colori), il meglio che possono dire è che il numero di Ramsey è compreso tra 43 e 48.
"È davvero imbarazzante", ha detto Yuval Wigderson , uno studente laureato alla Stanford University. "Lavoriamo su questo problema da quasi 100 anni e non sappiamo nulla".
I numeri di Ramsey sono difficili da calcolare perché la complessità di un grafico aumenta notevolmente man mano che si aggiungono i vertici. Per un grafico con sei vertici e due colori, puoi eseguire manualmente tutte le possibilità. Ma per un grafo con 40 vertici, ci sono 2 780 modi per applicare due colori.
"C'è solo troppo da controllare", ha detto Axenovich.
Tra i matematici che studiano i numeri di Ramsey c'è una parabola, solitamente attribuita a Erdős, che cattura quanto velocemente questi calcoli diventano ostili. Un giorno, gli alieni ostili invadono. Si offrono di risparmiare il pianeta se riusciamo a produrre i numeri di Ramsey corretti. Secondo la parabola, se chiedono il numero Ramsey per cricche di due colori di taglia 5, dovremmo impiegare tutte le risorse della civiltà umana per trovarlo. Ma se chiedono una cricca di taglia 6, dovremmo prepararci per la battaglia.
"Se ci chiedono il numero 6 di Ramsey, dimenticatene, lanciamo un attacco", ha detto Axenovich.
Sfruttare la casualità
Poiché il calcolo dei numeri Ramsey esatti è in gran parte impossibile, i matematici invece si concentrano su di loro, dimostrando che sono maggiori di alcuni "limiti inferiori" e inferiori di alcuni "limiti superiori". Il nuovo lavoro migliora la precisione dei limiti inferiori ma non affronta i limiti superiori.
Nel 1935 Erdős e George Szekeres stabilirono il primo di questi legami. Hanno usato una breve dimostrazione per mostrare che i numeri Ramsey a due colori devono essere inferiori a un limite superiore di 4 t , dove t è la dimensione della cricca monocromatica a cui sei interessato. Hanno anche scoperto che i numeri Ramsey a tre colori devono essere inferiore a 27 t . Un decennio dopo, nel 1947, Erdős calcolò i primi limiti inferiori per questi numeri: per due colori è ($ latex sqrt {2} $) t vertici e per tre colori è ($ latex sqrt {3} $) t .
C'è una grande differenza tra ($ lattice sqrt {2} $) t e 4 t, in particolare per quanto t ottiene molto grande. Questo divario riflette la comprensione imprecisa dei numeri di Ramsey da parte dei matematici. Ma la forma dei limiti – il modo in cui la dimensione del grafo richiesto è espressa in termini di dimensione della cricca desiderata – suggerisce ciò che i matematici desiderano maggiormente sapere.
"Quello che vorremmo davvero capire è il comportamento di crescita di questi numeri man mano che la dimensione della cricca cresce", ha detto Lisa Sauermann , borsista postdoctoral presso l'Institute for Advanced Study di Princeton, nel New Jersey.
Per questo motivo, il contributo più duraturo di Erdős allo studio dei numeri di Ramsey non erano i limiti stessi, ma il metodo che usava per calcolarli. Ecco cosa ha fatto per il limite inferiore.
Immagina di avere un grafo completo con 10 vertici e 45 bordi. E immagina di voler sapere se è possibile applicare tre colori senza creare una cricca monocromatica di una dimensione specifica, diciamo cinque vertici (collegati da 10 bordi).
Puoi iniziare, come ha fatto Erdös, colorando i bordi a caso. Per ogni bordo, tira l'equivalente di un dado a tre facce e applica il colore che esce. Erdös sapeva che la probabilità che un particolare sottoinsieme di 10 bordi finisse con lo stesso colore è facile da calcolare. È solo la probabilità che un bordo sia, diciamo, rosso, moltiplicata per la probabilità che un altro bordo sia rosso, e così via per tutti e 10 i bordi (quindi 1/3 10 ). Successivamente, ha moltiplicato quel valore per 3 per tenere conto del fatto che ci sono tre diversi colori che potrebbero produrre la cricca monocromatica desiderata.
Erdős ha quindi esaminato il numero totale di diverse cricche di cinque vertici nel grafo. Ce ne sono 252. Infine, ha preso la probabilità che uno di loro produrrà una cricca monocromatica e l'ha aggiunta alle probabilità che uno qualsiasi degli altri 251 produrrà la cricca. Questo è un calcolo noto come prendere il "limite di unione" e stima la probabilità di produrre una cricca monocromatica quando si colorano i bordi in modo casuale.
Finché il limite di unione rimane inferiore a 1, sai che il metodo di colorazione casuale non è garantito per produrre la cricca monocromatica data. Nel nostro esempio, il limite di unione è 0,0128. Ciò significa che sei lungi dall'essere garantito una cricca monocromatica di 5 vertici, il che significa che il numero di Ramsey per questo esempio è maggiore di 10 vertici.
I matematici chiamano questo approccio il metodo probabilistico. È una soluzione ingegnosa per un problema altrimenti intrattabile. Invece di dover trovare esempi di colorazioni che non contengono cricche monocromatiche di dimensioni diverse, Erdős ha semplicemente dimostrato che queste colorazioni senza cricche devono esistere (perché il limite di unione è inferiore a 1), il che significa che il numero di Ramsey deve essere maggiore di il numero di vertici nel grafo che stai attualmente colorando in modo casuale.
"Siamo in grado di dimostrare che qualcosa esiste senza mostrare effettivamente cosa sia", ha detto Wigderson.
Nei successivi 70 anni, i matematici migliorarono il limite inferiore di Erdös per due e tre colori solo una volta: nel 1975, con un rafforzamento incrementale da parte di Joel Spencer. Molte persone hanno lavorato sul problema, ma nessuno è riuscito a trovare un modo migliore del metodo probabilistico per calcolare i numeri di Ramsey. "Il problema è stato quello di cercare di sconfiggere questo proveniente dal campionamento a caso", ha detto Conlon.
Ed è quello che hanno finalmente fatto Conlon e Ferber questo autunno.
Ordine incorporante
La nuova dimostrazione migliora il limite inferiore per i numeri Ramsey per tre o più colori.
Prima del lavoro di Conlon e Ferber, il limite inferiore per tre colori era ($ latex sqrt {3} $) t (circa 1,73 t ). Hanno migliorato il limite a 1.834 t . Per quattro colori, hanno alzato il limite inferiore da 2 t a 2.135 t. Entrambi sono balzi giganteschi. Aumentando il numero di base che viene elevato alla potenza t , Conlon e Ferber hanno dimostrato che esistono grafici a tre e quattro colori esponenzialmente più grandi che mancano delle cricche monocromatiche richieste. In altre parole, hanno dimostrato che il disturbo può persistere all'interno di grafici più grandi di quelli precedentemente noti.
L'obiettivo di Conlon e Ferber era colorare un grafico completo senza creare grandi cricche monocromatiche. Per fare ciò, hanno trovato un modo per distribuire in modo efficiente un colore (rosso) secondo una regola fissa prima di applicare i colori rimanenti a caso. Questo metodo ibrido offriva loro un controllo aggiuntivo sulla struttura del grafico che Erdös non aveva.
Per la parte fissa del piano, hanno posizionato i vertici in un tipo speciale di spazio geometrico, in modo che ogni vertice fosse definito da un insieme di coordinate. Quindi hanno deciso quali bordi colorare di rosso tramite un processo in due fasi.
Per prima cosa, hanno preso le coordinate di ciascun vertice, le hanno quadrate e sommate, un processo noto come prendere la somma dei quadrati. A causa della natura di questo particolare spazio geometrico, questa operazione di somma dei quadrati ha prodotto uno dei due valori: 0 o 1. Successivamente, concentrandosi solo sui vertici la cui somma dei quadrati era 0, hanno calcolato il "prodotto interno" tra le coppie di vertici – un'operazione standard in algebra lineare. Se un bordo collegava una coppia il cui prodotto interno era un certo valore, lo coloravano di rosso. Ciò rappresentava la metà dei bordi totali.
Dopo aver completato questa parte deterministica del loro approccio, Conlon e Ferber sono passati alla parte casuale. Per i bordi rimanenti lanciarono una moneta – proprio come avrebbe fatto Erdös – per determinare se colorare un dato bordo blu o verde.
Questo approccio si è rivelato un ottimo modo per evitare di formare cricche monocromatiche al crescere delle dimensioni di un grafico. Questo era di progettazione: la coppia ha progettato il passaggio deterministico per generare bordi rossi che sono stati distribuiti su tutto il grafico. A distanza sembrerebbero quasi sparpagliati a caso – e in effetti, Conlon e Ferber si riferiscono a questa disposizione di bordi rossi come "pseudo-casuale".
Questa distribuzione pseudocasuale dei bordi rossi raggiunge due cose desiderabili. Innanzitutto, allargando i bordi rossi, ti assicura di non ritrovarti con grosse cricche rosse (che è ciò che stai cercando di evitare se vuoi aumentare il limite inferiore). In secondo luogo, i bordi rossi diffusi spezzano il grafico, lasciando meno spazi aperti che potrebbero finire per essere riempiti casualmente da cricche monocromatiche di un altro colore.
"Volevamo assicurarci che il primo colore, che abbiamo utilizzato in modo deterministico, riducesse il numero di potenziali cricche", ha detto Ferber.
I matematici hanno reagito rapidamente alla nuova dimostrazione. A pochi giorni dal suo rilascio, Wigderson ha pubblicato un documento di follow-up che ha utilizzato i loro metodi per dimostrare un limite inferiore ancora leggermente migliore per i numeri Ramsey per quattro o più colori. Dopo decenni di stasi sui numeri di Ramsey, la diga si era finalmente rotta.
"Il nostro stato di conoscenza è rimasto bloccato da Erdös negli anni '40, quindi tutto ciò che fornisce un nuovo approccio a domande di questo tipo è eccitante", ha detto Wigderson.
Questa è la traduzione automatica di un articolo pubblicato su Quanta Magazine all’URL https://www.quantamagazine.org/new-math-proof-raises-lower-bounds-of-graph-randomness-20201104/ in data Wed, 04 Nov 2020 18:40:50 +0000.