I matematici stabiliscono la congettura della colorazione di Erdös
Cinquant’anni fa, Paul Erdős e altri due matematici hanno escogitato un problema di teoria dei grafi che pensavano di poter risolvere immediatamente. Un team di matematici ha finalmente risolto il problema.
Il post Mathematicians Settle Erdős Coloring Conjecture è apparso per la prima volta su Quanta Magazine .
Il post Mathematicians Settle Erdős Coloring Conjecture è apparso per la prima volta su Quanta Magazine
“>
Nell'autunno del 1972, Vance Faber era un nuovo professore all'Università del Colorado. Quando due influenti matematici, Paul Erdős e László Lovász, vennero in visita, Faber decise di organizzare un tea party. Erdős in particolare aveva una reputazione internazionale come ricercatore eccentrico ed energico, ei colleghi di Faber erano ansiosi di incontrarlo.
"Mentre eravamo lì, come in tanti di questi tea party, Erdős si sedeva in un angolo, circondato dai suoi fan", ha detto Faber. "Teneva discussioni simultanee, spesso in diverse lingue su cose diverse."
Erdős, Faber e Lovász concentrarono la loro conversazione sugli ipergrafi, una nuova idea promettente nella teoria dei grafi all'epoca. Dopo un po 'di dibattito arrivarono a un'unica domanda, in seguito nota come congettura di Erdős-Faber-Lovász. Riguarda il numero minimo di colori necessari per colorare i bordi degli ipergrafi entro determinati vincoli.
"Era la cosa più semplice possibile che potessimo inventare", ha detto Faber, ora matematico presso il Center for Computing Sciences dell'Institute for Defense Analyzes. “Ci abbiamo lavorato un po 'durante la festa e abbiamo detto:' Oh beh, finiremo domani. ' Non è mai successo. "
Il problema si è rivelato molto più difficile del previsto. Erdős la pubblicizzò spesso come una delle sue tre congetture preferite e offrì una ricompensa per la soluzione, che aumentò a $ 500 quando i matematici si resero conto della difficoltà. Il problema era ben noto nei circoli della teoria dei grafi e ha attirato molti tentativi per risolverlo, nessuno dei quali ha avuto successo.
Ma ora, quasi 50 anni dopo, un team di cinque matematici ha finalmente dimostrato che la riflessione del tea party è vera. In un preprint pubblicato a gennaio , pongono un limite al numero di colori che potrebbero essere necessari per ombreggiare i bordi di alcuni ipergrafi in modo che nessun bordo sovrapposto abbia lo stesso colore. Dimostrano che il numero di colori non è mai maggiore del numero di vertici nell'ipigrafo.
L'approccio prevede l'accurata messa da parte di alcuni bordi di un grafico e la colorazione casuale di altri, una combinazione di idee che i ricercatori hanno utilizzato negli ultimi anni per risolvere una serie di problemi aperti di lunga data. Non era a disposizione di Erdős, Faber e Lovász quando hanno escogitato il problema. Ma ora, fissando la sua risoluzione, i due matematici sopravvissuti del trio originale possono trarre piacere dalle innovazioni matematiche che la loro curiosità ha provocato.
"È un lavoro bellissimo", ha detto Lovász , della Eötvös Loránd University. "Sono stato davvero contento di vedere questi progressi."
Solo abbastanza colori
Mentre Erdős, Faber e Lovász sorseggiavano il tè e parlavano di matematica, avevano in mente una nuova struttura simile a un grafico. I grafici ordinari sono costruiti da punti, chiamati vertici, collegati da linee, chiamati bordi. Ogni bordo unisce esattamente due vertici. Ma gli ipergrafi considerati da Erdős, Faber e Lovász sono meno restrittivi: i loro bordi possono corralizzare qualsiasi numero di vertici.
Questa nozione più ampia di un bordo rende gli ipergrafi più versatili dei loro cugini hub-and-spoke. I grafici standard possono esprimere solo relazioni tra coppie di cose, come due amici in un social network (dove ogni persona è rappresentata da un vertice). Ma per esprimere una relazione tra più di due persone, come l'appartenenza condivisa a un gruppo, ogni bordo deve comprendere più di due persone, cosa che gli ipergrafi consentono.
Tuttavia, questa versatilità ha un prezzo: è più difficile dimostrare le caratteristiche universali per gli ipergrafi che per i grafici ordinari.
"Molti dei miracoli svaniscono o le cose diventano molto più difficili quando si passa agli ipergrafi", ha detto Gil Kalai dell'IDC Herzliya e dell'Università ebraica di Gerusalemme.
Ad esempio, i problemi di colorazione dei bordi diventano più difficili con gli ipergrafi. In questi scenari, l'obiettivo è colorare tutti i bordi di un grafico (o ipergrafo) in modo che non ci siano due bordi che si incontrano in un vertice hanno lo stesso colore. Il numero minimo di colori necessari per eseguire questa operazione è noto come indice cromatico del grafico.
La congettura di Erdős-Faber-Lovász è una domanda colorita su un tipo specifico di ipergrafo in cui i bordi si sovrappongono minimamente. In queste strutture, note come ipergrafi lineari, non è consentito che due bordi si sovrappongano a più di un vertice. La congettura prevede che l'indice cromatico di un ipergrafo lineare non sia mai superiore al suo numero di vertici. In altre parole, se un ipergrafo lineare ha nove vertici, i suoi bordi possono essere colorati con non più di nove colori, indipendentemente da come li disegni.
L'estrema generalità della congettura di Erdős-Faber-Lovász rende difficile dimostrarla. Man mano che ci si sposta sugli ipergrafi con sempre più vertici, si moltiplicano anche i modi di disporre i loro bordi di loop. Con tutte queste possibilità, potrebbe sembrare probabile che ci sia una configurazione di bordi che richiede più colori di quanti ne abbia i vertici.
"Ci sono così tanti diversi tipi di ipergrafi che hanno gusti completamente diversi", ha detto Abhishek Methuku , uno degli autori della nuova dimostrazione, insieme a Dong-yeap Kang , Tom Kelly , Daniela Kühn e Deryk Osthus , tutti dell'Università di Birmingham. "È sorprendente che sia vero."
Dimostrare questa previsione sorprendente ha significato confrontarsi con diversi tipi di ipergrafi particolarmente difficili da colorare e stabilire che non ci sono altri esempi ancora più difficili.
Tre ipergrafi estremi
Se scarabocchi su una pagina e disegni un ipergrafo lineare, il suo indice cromatico sarà probabilmente molto inferiore al numero di vertici. Ma ci sono tre tipi di ipergrafi estremi che spingono al limite.
Nel primo, ogni bordo collega solo due vertici. Di solito è chiamato grafo completo, perché ogni coppia di vertici è collegata da un bordo. I grafi completi con un numero dispari di vertici hanno l'indice cromatico massimo consentito dalla congettura di Erdős-Faber-Lovász.
Il secondo esempio estremo è, in un certo senso, l'opposto di un grafico completo. Dove gli archi in un grafo completo connettono solo un piccolo numero di vertici (due), tutti gli archi in questo tipo di grafo connettono un gran numero di vertici (man mano che il numero di vertici totali cresce, così fa il numero compreso da ogni spigolo). Si chiama piano proiettivo finito e, come il grafo completo, ha il massimo indice cromatico.
Il terzo estremo cade nel mezzo dello spettro – con piccoli bordi che uniscono solo due vertici e grandi bordi che uniscono molti vertici. In questo tipo di grafico hai spesso un vertice speciale collegato a ciascuno degli altri da bordi solitari, quindi un unico grande bordo che raccoglie tutti gli altri.
Se modifichi leggermente uno dei tre ipergrafi estremi, il risultato avrà in genere anche l'indice cromatico massimo. Quindi ciascuno dei tre esempi rappresenta una famiglia più ampia di ipergrafi impegnativi, che per anni hanno frenato gli sforzi dei matematici per dimostrare la congettura di Erdős-Faber-Lovász.
Quando un matematico incontra per la prima volta la congettura, può tentare di dimostrarla generando un semplice algoritmo o una procedura facile che specifica un colore da assegnare a ciascun bordo. Un tale algoritmo dovrebbe funzionare per tutti gli ipergrafi e utilizzare solo tanti colori quanti sono i vertici.
Ma le tre famiglie di ipergrafi estremi hanno forme molto diverse. Quindi qualsiasi tecnica per dimostrare che è possibile colorare una delle famiglie in genere fallisce per gli ipergrafi nelle altre due famiglie.
"È abbastanza difficile avere un teorema comune per incorporare tutti i casi estremi", ha detto Kang.
Mentre Erdős, Faber e Lovász conoscevano questi tre ipergrafi estremi, non sapevano se ce ne fossero altri che hanno anche il massimo indice cromatico. La nuova dimostrazione fa questo passo successivo. Dimostra che qualsiasi ipergrafo che è significativamente diverso da questi tre esempi richiede meno colori rispetto al suo numero di vertici. In altre parole, stabilisce che gli ipergrafi che assomigliano a questi tre sono difficili come sembra.
"Se escludi queste tre famiglie, dimostriamo che non ci sono più cattivi esempi", ha detto Osthus. "Se non sei troppo vicino a nessuno di questi, puoi usare molti meno colori."
Ordinamento dei bordi
La nuova dimostrazione si basa sui progressi di Jeff Kahn della Rutgers University che ha dimostrato una versione approssimativa della congettura di Erdős-Faber-Lovász nel 1992. Lo scorso novembre, Kühn e Osthus (entrambi matematici senior) e il loro team di tre dottorandi: Kang, Kelly e Methuku – si proponeva di migliorare il risultato di Kahn, anche se non risolvevano completamente la congettura.
Ma le loro idee erano più potenti di quanto si aspettassero. Quando si sono messi al lavoro, hanno iniziato a rendersi conto che potrebbero essere in grado di dimostrare esattamente la congettura.
"Era tutto tipo di magia", ha detto Osthus. "È stata una fortuna che in qualche modo la squadra che avevamo si adattasse esattamente".
Hanno iniziato ordinando i bordi di un dato ipergrafo in diverse categorie in base alla dimensione del bordo (il numero di vertici che un bordo collega).
Dopo questo ordinamento sono passati prima ai bordi più difficili da colorare: bordi con molti vertici. La loro strategia per colorare i bordi larghi si basava su una semplificazione. Hanno riconfigurato questi bordi come vertici di un grafo ordinario (dove ogni bordo collega solo due vertici). Li hanno colorati usando i risultati stabiliti dalla teoria dei grafi standard e poi hanno riportato quella colorazione all'ipigrafo originale.
"Stanno tirando dentro tutti i tipi di cose che loro e altre persone hanno sviluppato nel corso dei decenni", ha detto Kahn.
Dopo aver colorato i bordi più grandi, hanno proceduto verso il basso, salvando i bordi più piccoli di un grafico per ultimi. Poiché i bordi piccoli toccano meno vertici, sono più facili da colorare. Ma salvarli per ultimi rende anche la colorazione più difficile in un modo: quando gli autori sono arrivati ai bordi piccoli, molti dei colori disponibili erano già stati usati su altri bordi adiacenti.
Per risolvere questo problema, gli autori hanno approfittato di una nuova tecnica in combinatoria chiamata assorbimento che loro e altri hanno utilizzato di recente per risolvere una serie di domande.
“Daniela e Deryk hanno molti risultati guardando altre famose domande che lo usano. Ora il loro gruppo è riuscito a dimostrare il teorema usando questo metodo ", ha detto Kalai.
Colori assorbenti
Gli autori usano l'assorbimento come un modo per aggiungere gradualmente i bordi a una colorazione, assicurandosi nel contempo che la colorazione mantenga sempre le giuste proprietà. È particolarmente utile per colorare i punti in cui molti piccoli bordi convergono su un unico vertice, come il vertice speciale collegato a tutti gli altri nel terzo ipergrafo estremo. I cluster come questi utilizzano quasi tutti i colori disponibili e devono essere colorati con attenzione.
Per fare ciò, gli autori hanno creato un serbatoio di piccoli bordi, estratti da questi insidiosi ammassi. Quindi hanno applicato una procedura di colorazione casuale a molti dei piccoli bordi rimasti (fondamentalmente, tirando un dado per decidere quale colore applicare a un dato bordo). Man mano che la colorazione procedeva, gli autori hanno scelto strategicamente tra i colori inutilizzati e li hanno applicati in modo scelto con cura ai bordi riservati, “assorbendoli” nei coloranti.
L'assorbimento migliora l'efficienza della procedura di colorazione casuale. Colorare i bordi in modo casuale è una buona base per una procedura molto generale, ma è anche uno spreco: se applicato a tutti i bordi, è improbabile che produca la configurazione ottimale dei colori. Ma la prova recente tempera la flessibilità dei coloranti casuali integrandola con l'assorbimento, che è un metodo più esatto.
Alla fine – avendo colorato i bordi più grandi di un grafico con una tecnica e poi i bordi più piccoli usando l'assorbimento e altri metodi – gli autori sono stati in grado di dimostrare che il numero di colori richiesti per colorare i bordi di qualsiasi ipergrafo lineare non è mai superiore a il numero di vertici. Ciò dimostra che la congettura di Erdős-Faber-Lovász è vera.
A causa degli elementi probabilistici, la loro dimostrazione funziona solo per ipergrafi sufficientemente grandi, quelli con più di un numero specifico di vertici. Questo approccio è comune in calcolo combinatorio ei matematici lo considerano una dimostrazione quasi completa poiché omette solo un numero finito di ipergrafi.
"C'è ancora l'ipotesi nel documento che il numero di nodi debba essere molto grande, ma probabilmente è solo un lavoro aggiuntivo", ha detto Lovász. "In sostanza, la congettura è ora dimostrata."
La congettura di Erdős-Faber-Lovász è iniziata come una domanda che sembrava potesse essere posta e risolta nell'arco di una singola parte. Negli anni che seguirono, i matematici si resero conto che la congettura non era così semplice come sembrava, che è forse ciò che i tre matematici avrebbero voluto comunque. Una delle uniche cose migliori che risolvere un problema di matematica davanti al tè è inventarne uno che finisce per ispirare decenni di innovazione matematica sulla strada per la sua risoluzione finale.
"Gli sforzi per dimostrarlo hanno costretto alla scoperta di tecniche che hanno un'applicazione più generale", ha detto Kahn. "Questo è un po 'il modo in cui Erdős ha ottenuto in matematica."
Il post Mathematicians Settle Erdős Coloring Conjecture è apparso per la prima volta su Quanta Magazine .
Questa è la traduzione automatica di un articolo pubblicato su Quanta Magazine all’URL https://www.quantamagazine.org/mathematicians-settle-erdos-coloring-conjecture-20210405/ in data Mon, 05 Apr 2021 13:53:25 +0000.