I matematici scoprono un nuovo modo di prevedere la struttura nei grafici | Rivista Quanta

È stato un anno entusiasmante per la ricerca combinatoria. All'inizio del 2023, i matematici sono rimasti sbalorditi quando due di , il maggiori problemi sul campo sono stati risolti in altrettanti mesi. Ora, una terza domanda importante è caduta con una prova di 14 pagine "che ha assolutamente tutte le idee giuste", ha detto Mehtaab Sawhney del Massachusetts Institute of Technology, che ha aggiunto: "È completamente scioccante".

Questa domanda riguarda i cosiddetti numeri di Ramsey, quantità fondamentali che riflettono i limiti di un possibile disordine. Questi numeri misurano la dimensione che gli insiemi di vertici e bordi, chiamati grafici, possono raggiungere prima che inevitabilmente diano origine a pattern e struttura.

I matematici studiano i numeri di Ramsey, notoriamente difficili da definire, da quasi un secolo. In tal modo, hanno sviluppato tecniche che hanno portato a progressi in una varietà di discipline oltre la teoria dei grafi, tra cui la teoria dei numeri e la crittografia.

Ma la nuova prova, pubblicato online all'inizio di questo mese, segna un allontanamento da quelle tecniche. Non solo risolve un problema che ha resistito al progresso per più di 40 anni, ma presenta anche una nuova road map su come i matematici potrebbero affrontare i problemi di Ramsey in futuro.

La pianificazione delle feste incontra la teoria dei grafi

Per capire cos'è un numero di Ramsey, immagina di organizzare una festa.

Quante persone dovresti invitare per garantire che ci sarà un gruppo di persone che si conoscono tutte o un gruppo che sono tutti estranei? Puoi codificare questa domanda nel linguaggio dei grafici. Assegna un vertice a ogni persona. Per n persone, ottieni n vertici. Collega ogni coppia di vertici con un bordo. Colora il bordo di rosso se le persone in questione si conoscono e di blu se sono estranei.

Un gruppo di conoscenti comuni o estranei è rappresentato da una struttura chiamata cricca: un insieme di vertici collegati da spigoli dello stesso colore. Il numero di Ramsey r(s, t) è il numero minimo di persone che devi invitare affinché sia ​​impossibile evitare di includere un gruppo di s conoscenti o t estranei - nel linguaggio della teoria dei grafi, una cricca rossa di dimensioni s o una cricca blu di dimensioni t.

Ad esempio, sappiamo che r(4, 5) = 25. Quindi puoi organizzare una festa con 24 persone, alcune delle quali si conoscono, senza includere un gruppo di quattro conoscenti in comune o cinque sconosciuti. Ma aggiungi un'altra persona e non puoi evitare di creare almeno una di queste strutture.

Una delle prime scoperte di quest'anno nel calcolo combinatorio ha fornito un limite superiore più stretto per i numeri di Ramsey "simmetrici", dove le cricche rosse e blu hanno le stesse dimensioni. Con i numeri di Ramsey asimmetrici - oggetto del nuovo risultato - i matematici fissano la dimensione della cricca rossa e si chiedono cosa succede quando la dimensione della cricca blu diventa arbitrariamente grande.

I matematici sono stati in grado di calcolare esattamente solo una manciata dei numeri di Ramsey più piccoli. Lo hanno dimostrato r(4, 5) = 25 nel 1995. Ma nessuno conosce il valore di r(4, 6). Allo stesso modo, nei primi anni '1980, essi mostrarono che r(3, 9) = 36, ma r(3, 10) rimane un problema aperto. (Il caso simmetrico è altrettanto difficile: r(4) = 18, ma il valore di r(5) non è noto.)

E così i matematici cercano invece di stimare i numeri di Ramsey, arrivando con limiti superiori e inferiori sui loro valori.

Negli anni '1990, hanno utilizzato tecniche per la generazione casuale di grafici per dimostrare che se la cricca rossa è fissata a 3 e quella blu diventa sempre più grande, la dimensione del numero di Ramsey cresce come il quadrato della dimensione della cricca blu. In altre parole, r(3, t) è di circa t².

La nuova dimostrazione chiede cosa succede quando la dimensione della cricca rossa è fissata a 4, anziché a 3. Negli anni '1930 fu stabilito che r(4, t) non cresce più velocemente di intorno t³. Ma il miglior limite inferiore, trovato negli anni '1970, è circa t^5/2 - notevolmente più piccolo.

Gli sforzi per colmare il divario alzando il limite inferiore o abbassando quello superiore fallirono per decenni, fino a quando una coppia di matematici aggiunse un ingrediente chiave.

Nascosto in bella vista

Nel 2019, Sam Matteo, allora uno studente laureato presso la Libera Università di Bruxelles (VUB) era alla ricerca di ispirazione. La sua competenza era in geometria finita, lo studio della disposizione di punti, linee e altre strutture in spazi appositamente definiti. Ma anche se trovava il lavoro interessante, si sentiva vincolato da quanto dovevano essere rigorose ed esatte queste costruzioni geometriche.

Poi vide un documento da due matematici, Dhruv Mubayi dell'Università dell'Illinois, Chicago e Jacques Verstraete dell'Università della California, San Diego. Stavano ripensando a come affrontare i problemi di Ramsey. Mentre le tecniche tradizionali implicano la generazione casuale di grafici per ottenere buone stime dei numeri di Ramsey, Mubayi e Verstraete hanno iniziato con costruzioni "pseudocasuali" che sembrano casuali, ma non lo sono.

Qualcosa è scattato in Mattheus. Forse, pensò, la sua prospettiva geometrica poteva essere d'aiuto. Per i due anni successivi, mentre terminava il suo lavoro di laurea, mantenne questa idea in fondo alla sua mente. Ha quindi fatto domanda per una borsa di studio Fulbright, che gli avrebbe permesso di perseguire un postdoc con Verstraete negli Stati Uniti

Nel 2022, poco dopo che Mattheus è stato insignito del Fulbright (insieme a un'altra compagnia), si è trasferito alla UCSD e ha iniziato a lavorare con Verstraete su r(4,t). I matematici volevano alzare il limite inferiore per incontrare il limite superiore noto. Per farlo, dovrebbero trovare un grafico con quasi t³ vertici che non avevano cricche rosse di dimensione 4 o cricche blu di dimensione t.

Per far funzionare la loro prova, hanno riformulato il problema. Immagina semplicemente di eliminare ogni bordo blu. L'obiettivo ora diventa trovare un grafico senza cricche rosse di dimensione 4 e senza insiemi di dimensioni indipendenti t (ovvero insiemi di t vertici senza spigoli).

Il lavoro di Mubayi e Verstraete del 2019 implicava che se puoi costruire un grafico pseudocasuale senza cricche rosse di dimensione 4, puoi prenderne pezzi casuali per ottenere grafici più piccoli senza grandi insiemi indipendenti. Questo era esattamente ciò che Mattheus e Verstraete volevano trovare. Iniziando con un grafico ancora più grande, speravano di trovare un grafico con quasi t³ vertici che hanno soddisfatto i loro criteri. "All'interno di questi grafici si nascondono migliori grafici Ramsey", ha detto Verstraete.

Il problema era capire la giusta costruzione pseudocasuale con cui cominciare.

I matematici dovevano arrivarci in un modo un po' indiretto. Non hanno iniziato con un grafico pseudocasuale. Non sono affatto iniziati con un grafico.

Invece, Mattheus ha ricordato uno strano oggetto chiamato unitale hermitiano, qualcosa con cui i geometri finiti tendono a conoscere molto bene, ma che un matematico che lavora in combinatoria difficilmente avrebbe mai incontrato.

Un'unità hermitiana è un insieme speciale di punti su una curva, insieme a linee che passano attraverso quei punti in configurazioni specifiche. Fondamentalmente, può anche essere rappresentato come un grafico costituito da molte cricche grandi ma appena sovrapposte.

Questo grafico è ben noto e molte delle sue proprietà sono state studiate. Ma non era mai stato considerato nel contesto dei problemi di Ramsey. "È molto specifico per questo business a geometria finita", ha detto Mattheus.

Il grafico potrebbe non sembrare utile a prima vista, dal momento che contiene così tante grandi cricche. Ma una caratteristica chiave dell'unità hermitiana è che contiene solo cricche di dimensione 4 i cui vertici sono raggruppati insieme in modo atipico. A causa di questa proprietà, era relativamente facile per i matematici distruggere quelle cricche indesiderate eliminando gli archi a caso.

Queste delezioni hanno dato loro un nuovo grafico senza cricche di dimensione 4, ma conteneva ancora grandi insiemi indipendenti. Mattheus e Verstraete ora dovevano dimostrare che questo grafico era pseudocasuale. In tal modo, sono stati finalmente in grado di utilizzare la prova del 2019 come avevano sperato. Hanno preso sottografi casuali con circa t³ vertici e potrebbe garantire che quei sottografi fossero privi di insiemi di dimensioni indipendenti t.

Questo ha completato la dimostrazione. "Questa costruzione è assolutamente meravigliosa", ha detto Sawhney.

Il lavoro annuncia un cambiamento nel modo in cui i matematici pensano ai problemi di Ramsey. "È molto, molto naturale cercare di usare la casualità per provare a far passare le cose e ottenere il miglior limite possibile", ha detto Davide Conlon del California Institute of Technology. "Ma ciò che questo dimostra davvero è che la casualità ti porta solo così lontano."