I matematici risolvono la congettura colorante di Erdös

In autunno del 1972, Vance Faber era un nuovo professore presso l’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 l’Institute for Defense Analyzes ‘Center for Computing Sciences. “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 lo 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 attirò molti tentativi per risolverlo, nessuno dei quali ebbe 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 la messa da parte con attenzione di alcuni bordi di un grafico e la colorazione casuale di altri, una combinazione di idee che i ricercatori hanno esercitato negli ultimi anni per risolvere una serie di problemi aperti di lunga data. Non era disponibile per Erdős, Faber e Lovász quando hanno immaginato 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 Sposo, dell’Università Eötvös Loránd. “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 corrallizzare 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 confine 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 [of graph theory] o svaniscono o le cose diventano molto più difficili quando si passa agli ipergrafi “, ha detto Gil Kalai di 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 colorante 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.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *