Colorare grafi per combattere l’invasione aliena

Immaginate di esservi riuniti, nella fredda sera dell’11 febbraio 2023, con cinque amici a vedere la finale di Sanremo. Ciascuno di voi sei ha un preferito fra i ventotto partecipanti alla competizione. Viene spontaneo chiedersi: quanti di voi condividono lo stesso preferito?

Colorare grafi

La domanda non è per nulla banale. Proviamo a descriverla con un modellino semplice, il più semplice possibile: un grafo. Ogni pallino, o vertice (in inglese vertex), rappresenta un membro del vostro gruppo di amici. Tracciamo una linea che collega ogni pallino con ogni altro pallino, un lato (in inglese edge). Ci ritroviamo con quello che i matematici chiamano K₆, l’unico grafo su sei vertici ad essere completo — ogni due vertici sono connessi da un lato.

Ora prendiamo questo grafo, due pennarelli, e procediamo nel modo seguente: coloriamo il lato che collega due nomi di rosso se le due persone hanno lo stesso cantante preferito; coloriamolo di blu se hanno un preferito diverso. Per esempio,

Questa operazione è detta, tecnicamente, una 2-colorazione (in inglese 2-coloring) di K₆. Di fatto, non è niente di più di prendere i lati del nostro grafo e assegnargli un colore a scelta fra rosso e blu.

Sottografi monocromatici

Se guardiamo attentamente questo grafo, notiamo che ci sono quattro persone che condividono lo stesso preferito. Se consideriamo solamente i quattro vertici in questione, ci ritroviamo con un cosiddetto K₃ (il grafo completo su tre vertici) monocromatico, colorato con lo stesso colore.

In effetti non è l’unico sottografo (cioè un grafo contenuto in un altro grafo) completo e monocromatico che troviamo. Ci sono anche diversi triangoli (cosiddetti K₃) blu. Per esempio,

Cosa abbiamo scoperto? Che ci sono tre persone che hanno lo stesso preferito (il K₃ monocromatico rosso) e che ci sono almeno tre persone che, prese due a due, hanno un preferito diverso. Per esempio, Amelia-Bruno-Elvira non è un triangolo monocromatico: due persone su tre hanno lo stesso preferito.

Lavorare su una colorazione specifica del grafo completo su sei vertici non è molto difficile. D’altra parte, però, uno potrebbe porsi una domanda più generale: data una colorazione qualsiasi di K₆, cosa succede ai triangoli monocromatici? Ce ne sono, non ce ne sono? E se sì, di che colore?

I numeri di Ramsey

Salta fuori che, per ogni scelta di 2-colorazioni simili (in altre parole, per ogni scelta di un partecipante a Sanremo), c’è sempre un triangolo monocromatico (di uno dei due colori). Nei termini della festicciola per la finale, almeno una di queste situazioni si presenta: o ci sono tre persone con lo stesso preferito (nel caso in cui il triangolo monocromatico sia rosso), o ci sono tre persone con tre artisti preferiti diversi (nel caso in cui il triangolo monocromatico sia blu). Dimostrare questo fatto richiede un momento di riflessione, dal momento che un grafo completo su sei vertici ammette 2¹⁵ = 32768 diverse possibili colorazioni con due colori, dunque di certo non possiamo controllarle a mano una per una.

Questo tipo di domande finisce sotto una branca della combinatoria nota come teoria di Ramsey (il teorema di Ramsey originale, fra le altre cose, ci dice che per ogni numero naturale m esiste una 2-colorazione di un qualche Kₙ, un grafo completo su magari tantissimi vertici, che ammette un Kₘ monocromatico). Si possono fare molte variazioni sul tema: ammettere più colori (per esempio rosso, blu e verde), o oggetti più complessi (ipergrafi), finanche grafi infiniti.

Nell’ambito dei grafi finiti, però, ci si può porre una domanda molto naturale: dato un numero m, qual è il grafo completo più piccolo che, se colorato con due colori, ammette un sottografo (completo) monocromatico su m vertici? Abbiamo appena visto che se coloriamo il grafo completo su sei vertici troviamo sempre triangoli monocromatici. In effetti, si può dimostrare che all’interno di colorazioni del grafo completo su cinque vertici non si possono trovare triangoli monocromatici: il numero di Ramsey di 3 è 6. Più in generale, se nè un numero naturale, allora il suo numero di Ramsey R(n) è il più piccolo numero di vertici di un grafo completo le cui 2-colorazioni ammettono Kₙ monocromatici.

In altre parole: quanti ospiti serve invitare alla visione della finale di Sanremo perché ce ne siano almeno n con lo stesso cantante preferito, o almeno n che a due a due abbiano un preferito diverso?

Calcolare numeri di Ramsey

Calcolare numeri di Ramsey è tutt’altro che banale. Il numero di Ramsey di 4 è 18. Per quanto riguarda il numero di Ramsey di 5, vale la pena citare Joel Spencer:

Erdős ci propone di immaginare una forza aliena, infinitamente più potente di noi, che atterri sul nostro pianeta e ci chieda il numero di Ramsey di 5, o ci annienteranno. In tal caso, […] dovremmo raccogliere tutti i computer e i matematici del mondo e tentare di calcolarlo. Se per caso, però, questa forza aliena ci chiedesse il numero di Ramsey di 6, allora […] dovremmo tentare di distruggere gli alieni.
(Joel Spencer, Ten lectures on the probabilistic method)

Vista la difficoltà nel calcolare esplicitamente queste quantità, ci si può invece chiedere se si possano trovare delle disuguaglianze che, quantomeno, ci diano una stima. Erdős e Szekeres, nel 1935, dimostrano che il numero di Ramsey di k è al più 4ᵏ.

Raffinare queste stime è, nelle parole di Timothy Gowers (medaglia Fields nel 1998),

…uno dei due o tre più importanti problemi aperti in extremal combinatorics.
(Twitter)

Un problema che, in effetti, non è più aperto: il 16 marzo 2023 Campos, Griffiths, Morris e Sahasrabudhe pubblicano un preprint in cui forniscono una stima migliore: per esempio, dimostrano che il numero di Ramsey di k è al più (3.9921875)ᵏ, per k “sufficientemente” grande. Seppure possa sembrare un miglioramento marginale, si tratta di un grosso passo avanti a livello teorico: crolla la barriera che, in precedenza, sembrava impedire a qualunque metodo per ottenere stime di scendere sotto la base 4. L’articolo mostra in effetti stime molto più complesse per diverse variazioni dei numeri di Ramsey (per esempio il numero di Ramsey di m ed l, dove si chiede di trovare un sottografo completo monocromatico su m vertici oppure un sottografo completo monocromatico su l vertici), attraverso un algoritmo che permette di individuare in maniera più efficiente le cosiddette cricche (in inglese cliques, un altro modo di parlare di sottografi completi) monocromatiche.

La speranza, dunque, è che i metodi sviluppati dai quattro possano essere rimaneggiati dall’imponente comunità dei combinatorici e potenziati per rendere le stime sempre più precise. Se non altro in virtù del rischio di improvvisa invasione aliena e di ritrovarsi a dover tirare a indovinare un possibile valore per il numero di Ramsey di 5 o di 6.