La combinatoria, ieri e oggi. Intervista a Pierre Duchet

Pierre Duchet è uno dei rari specialisti francesi di combinatoria. È un testimone privilegiato dei grandi sviluppi della matematica discreta, dalle scoperte di Erdős alle progressioni aritmetiche di numeri primi, passando per la dimostrazione del teorema dei quattro colori e della congettura di Berge (Claude Berge fu il suo relatore di tesi).

A quando risalgono gli inizi della combinatoria? La combinatoria, nel senso moderno del termine, è lo studio sistematico delle strutture. La si può far risalire agli anni Trenta. Se ne possono persino individuare le origini geografiche: l’Ungheria è il paese in cui la combinatoria è maggiormente riconosciuta e sviluppata! Per esempio, Erdős, Turán, Halmos, Szemerédi, Bollobás, Lovász, Frankl… Tutti questi celebri matematici sono nati in Ungheria. Sarebbe quasi più difficile citare specialisti di combinatoria che non siano ungheresi! Oggi, oltre all’Ungheria, esistono scuole di combinatoria in Nord America, nell’ex URSS, in alcuni paesi dell’Europa orientale e, in misura minore, in Francia; più di recente, in Giappone (da trent’anni) e in Cina (da una decina d’anni). Detto questo, si potrebbe far risalire la combinatoria al geniale Eulero, con il suo problema dei ponti di Königsberg [vedi FOCUS]. È combinatoria strutturale, ossia un «modo morbido di parlare dello spazio». Oppure a Laplace e alla sua visione atomistica dello spazio e dell’universo. O ancora a Leibniz che, per «predire il futuro», si trovò a dover «ritagliare» delle superfici [allusione al calcolo integrale]. Bisognerebbe parlare anche di Poincaré e della sua Analysis situs! Ma bisogna ammetterlo: la combinatoria decolla davvero solo con l’esplosione della ricerca operativa (RO) e con l’avvento dei grafi [vedi FOCUS] quali strutture matematiche a pieno titolo. Un esempio archetipico, nella RO, è il problema del commesso viaggiatore: immaginate un rappresentante in auto che debba visitare ciascuna delle N città di un paese per incontrarvi dei clienti. Il suo itinerario deve minimizzare il numero totale di chilometri percorsi, perché la benzina costa cara. Fra gli N! itinerari possibili, quale è ottimale? E quid se tutte le distanze valgono 1 e il viaggiatore deve passare una e una sola volta per ciascuna città (problema del circuito hamiltoniano)? Ecco il genere di problemi posti dalla ricerca operativa. Per piccoli valori di N, si conosce la soluzione, ma molto presto non si hanno, nel migliore dei casi, che euristiche per aiutare il commesso viaggiatore. Questo problema è estremamente difficile. [Si dice NP-difficile.] E oggi si torna ai problemi posti nel XVIII^º secolo. La combinatoria non è comparsa per caso: si inserisce in un continuum storico.

Problemi NP-difficili -----------------------

**Il XVIII^º secolo, Poincaré all’inizio del XX^º, gli anni Trenta e la teoria dei grafi, la nascita della RO durante la Seconda guerra mondiale… E che cosa accade in seguito?**

La RO ha prodotto moltissimi problemi di ottimizzazione discreta, come la colorazione dei grafi. La ricerca di un algoritmo è la finalità di questi problemi. Un’importante variante del problema della colorazione di un grafo è il problema del 5-flusso, enunciato da William Thomas Tutte nel 1954 [vedi FOCUS].

La RO, la teoria dei grafi, l’algoritmica, ma anche lo studio dei sistemi di insiemi (set systems), chiamati anche ipergrafi (hypergraphs), restano grandi fornitori di problemi per la combinatoria: problemi di packing (trovare impilamenti di oggetti quanto più densi possibile in uno spazio dato), problemi di covering (una struttura combinatoria copre un’altra?), congettura dei quattro colori (ormai teorema), congettura di Hadwiger… La teoria dei grafi ne costituiva la base, e questi grandi problemi alimentavano l’attività e tutte le ricerche del settore. Ma oggi non è più davvero così.

####

Oggi i grandi problemi non sono più i primi motori della ricerca: molti sono stati largamente affrontati o risolti (la congettura di Berge, divenuta il teorema forte dei grafi perfetti, o il teorema dei quattro colori). Negli anni Settanta si sviluppò una teoria della complessità per trattare i problemi decisionali, quelli cui si può rispondere sì o no. Ci sono problemi «facili», di complessità polinomiale. Formano quella che viene chiamata classe P (per «polynomial»). Per risolverli, si sa trovare un algoritmo il cui tempo di calcolo è maggiorato da un polinomio della dimensione dell’input. Vi sono poi problemi «difficili, se non addirittura del tutto impossibili», che formano la cosiddetta classe NP. Sono quelli per i quali si conosce un modo «rapido» per verificare una soluzione. Infine, ci sono problemi per i quali non si sa se siano P, NP o altro, e problemi che per natura non rientrano nella teoria della complessità! Tutti i ricercatori sono convinti che NP non sia inclusa in P. Ma nessuno è in grado di dimostrarlo. Il problema del commesso viaggiatore è NP-difficile, cioè almeno altrettanto difficile di un problema NP-completo. [Un problema è NP-completo se risolverlo in tempo polinomiale comporta la risoluzione in tempo polinomiale di ogni problema NP.] Un problema NP-difficile è, in pratica, irrisolvibile. E nel corso degli anni ci si è accorti che molti dei grandi problemi che suscitavano ricerche in combinatoria erano NP-difficili. È il caso del problema del numero cromatico totale, abbastanza facile da spiegare: si congettura che il numero cromatico totale di un grafo G sia minore di D(G) + 2, dove D(G) è il grado massimo dei vertici di G. Vediamo che cosa significa. Colorare un grafo G con k colori (una k-colorazione di G) consiste nell’attribuire a ciascun vertice e a ciascun lato di G uno fra k colori, in modo che due oggetti adiacenti (lato–vertice, vertice–vertice o lato–lato) abbiano sempre colori diversi. Il numero cromatico totale di G è il più piccolo intero k per cui esiste una k-colorazione di G. Determinare questo numero è un problema NP-difficile. Talvolta, però, lo si può caratterizzare oppure delimitare. La congettura di Hadwiger è un altro problema di colorazione irrisolto. Supponiamo che il numero cromatico del grafo non orientato G sia maggiore di m (ossia che sia impossibile colorare i vertici di G con meno di m colori senza che due vertici collegati ricevano lo stesso colore). Allora G possiede m sottografi connessi disgiunti, collegati fra loro da almeno un lato.

Quali strumenti matematici hanno permesso di risolvere, o almeno di affrontare, i problemi della matematica discreta? La cassetta degli attrezzi dello specialista di combinatoria contiene pochissimi risultati fondamentali. Il primo, probabilmente il più importante, è il teorema dei matrimoni. [Siano dati un insieme di ragazzi, un insieme di ragazze e l’applicazione che associa a ogni ragazzo le ragazze che gli piacciono. Se, per ogni sottogruppo di ragazzi, il numero di ragazze che piacciono loro è maggiore del numero di ragazzi di quel sottogruppo, allora si può sposare ogni ragazzo con una ragazza non ancora sposata che gli piaccia.] Cercando di generalizzare questa problematica, si giunge a una «teoria degli accoppiamenti» piuttosto potente, nella quale la teoria dei matroidi svolge un ruolo importante.

Claude Berge (1926–2002).**

Esistono poi delle metodologie. Per esempio, Paul Seymour e il suo gruppo affrontano i problemi di teoria dei grafi sempre con lo stesso approccio di «decomposizione»: si tratta di riuscire a «spezzare» un grafo dato, in modo che i soli grafi «infrangibili» abbiano una struttura nota. Quando si vuole assemblare un grafo qualsiasi a partire da mattoni elementari noti, l’arte consiste nel trovare la «colla giusta». Devo ammettere che non credevo che questo approccio avrebbe un giorno permesso di risolvere la congettura di Berge, eppure… Per i problemi di ottimizzazione discreta, spesso si cerca di riformularli in forma lineare: i vincoli sono modellizzati da un sistema di disuguaglianze lineari sulle variabili in gioco, e il problema consiste allora nel massimizzare, o minimizzare, una certa funzione dei dati, anch’essa lineare. Ci si trova così nelle condizioni di applicazione del teorema fondamentale della programmazione lineare [vedi anche in questo numero], con l’importante differenza che gli ottimi del problema combinatorio devono corrispondere a valori interi delle variabili, e non a valori razionali, o reali, qualsiasi. Quando le strutture che modellizzano il problema sono «simpatiche», si può dimostrare che l’ottimo a valori interi coincide con l’ottimo frazionario. Altrimenti, esistono pochissimi risultati generali che permettano di analizzare le strutture. Si procede per analogia. Il gruppo di Seymour, ancora una volta, ebbe l’idea di paragonare i grafi a parole su una superficie. Così, generalizzando un teorema di Kuratowski (che era polacco!), elaborò una teoria dei minori di grafo. In una ventina di articoli, distribuiti su oltre venticinque anni, riuscì a dimostrare la celebre congettura di Wagner [secondo la quale, in ogni famiglia infinita di grafi, uno dei grafi è isomorfo a un minore di un altro]!

Quando il Lotto ispira un problema irrisolto ------------------------------------------------

La «struttura» sembra fondamentale nella combinatoria. Che cos’è una «struttura»? Bisogna diffidare della parola «struttura»! Un albero, un grafo, un ipergrafo, un sistema di insiemi… tutto ciò definisce strumenti di modellizzazione che un matematico può manipolare, qualitativamente e quantitativamente. Al contrario, un grafo bipartito [un grafo colorabile usando soltanto due colori] fornisce sì uno strumento di modellizzazione, ma che non è manipolabile. La combinatoria strutturale si interessa a tutto ciò che è immediatamente modellizzabile come un insieme di insiemi finiti: è vasto! In realtà, occorre sviluppare l’intuizione di ciò che sia una «buona struttura», e per farlo servono strumenti di rappresentazione. I diagrammi di Venn, o «patatoidi», sono uno strumento di rappresentazione. Così come la geometria o la topologia sono strumenti di rappresentazione dello spazio. Altri ambiti che studiano le strutture sono l’algebra e la combinatoria algebrica. Ma in algebra si definisce sempre almeno un’operazione sulla struttura in questione. Noi non abbiamo nemmeno questo! Ci interessiamo alla connettività fra gli elementi, ossia a sapere se sono collegati, connessi.

Quali sono le grandi teorie elaborate per studiare le strutture? La teoria dei grafi pone moltissimi problemi interessanti, più di quanti ne risolva. E non è tutto: passando dai grafi non orientati a quelli orientati, si compie un salto di complessità fenomenale! È la giungla! Abbiamo parlato anche di combinatoria strutturale. Va inoltre menzionata la combinatoria enumerativa, legata al conteggio, cioè al contare con una metodologia data. Il conteggio riguarda l’aspetto quantitativo delle strutture: sono numerose, rare? Quante ce ne sono esattamente, asintoticamente? I problemi di conteggio abbondano. Fare combinatoria sui numeri, per esempio, significa rivelare particolari strutture aritmetiche. Un altro ambito importante è la teoria di Ramsey, secondo la quale in una struttura c’è sempre ordine, purché sia «abbastanza grande». Una domanda tipica di questa teoria è: «Qual è il numero minimo di elementi da riunire per essere sicuro che una certa proprietà sia verificata?» In realtà, questa teoria proviene da problemi estremali molto generali. Un semplice esempio è il problema del Lotto: quante schedine diverse bisogna giocare come minimo per essere certi di avere, poniamo, quattro numeri vincenti? Questo problema, nonostante molte ricerche, è tuttora irrisolto! Un problema estremale, in senso generale, consiste nel minimizzare una funzione di tre parametri, k, n e t. L’intero n è la dimensione dell’insieme di riferimento (n = 49 numeri nel caso del Lotto), k è il numero di elementi dei sottoinsiemi considerati (per una schedina del Lotto si selezionano sempre k = 6 numeri). Infine, t è il numero minimo di elementi dei sottoinsiemi che ci si impone di coprire (nel Lotto, si richiede di garantire t = 4 numeri esatti). Questo è un problema estremale: minimizzare la cardinalità della famiglia T di sottoinsiemi con k elementi tale che, per ogni sottoinsieme E con t elementi, si sia certi di trovare un insieme F, nella famiglia T, che contenga E. A parte alcuni casi banali, non si sa risolvere questi problemi. Per proseguire con i grandi ambiti della combinatoria, bisogna parlare della teoria delle configurazioni (design theory). È una teoria delle strutture regolari. Eccone un esempio: in un dodecaedro, si tratta della disposizione di tutti i cubi formati da otto vertici del dodecaedro. I poliedri regolari, i codici correttori d’errore e le reti sono configurazioni. Uno dei grandi problemi di questa teoria è la classificazione dei piani proiettivi [vedi FOCUS]. È un problema molto antico. Più in generale, ci si pone la questione dell’esistenza di t-configurazioni. Di recente si è riusciti a dimostrare che non esiste alcun piano proiettivo di ordine 10. Ma oltre 10, e oltre i piani proiettivi, non si sa molto… Anche la teoria dei nodi e delle trecce rientra nella combinatoria: il diagramma di un nodo è la combinatoria di una curva! Come riconoscere se un nodo è banale? Come sciogliere un nodo che si sa essere banale? Queste domande sono di una difficoltà formidabile.

Si fa combinatoria senza saperlo -----------------------------------------

A sentirla, la combinatoria sembra onnipresente! Qual è il suo posto all’interno della matematica? Molti matematici fanno combinatoria senza saperlo. Eppure, nel 2010, la matematica discreta non è ancora riconosciuta come ambito autonomo. Assente dai grandi congressi internazionali, è ancora vista come uno strumento e non come un oggetto di studio. Anzi, come considerazioni da informatici! È profondamente ingiusto: se i problemi sembrano a priori più facili nel mondo continuo che in quello discreto, dove sono spesso inattaccabili, forse è perché il continuo è un’approssimazione della realtà. Vedo i reali come una comodità di modellizzazione che nasconde la foresta della realtà. Il discreto ha molte applicazioni nella chimica molecolare e nella fisica atomica! Esiste un’autentica visione combinatoria del mondo. Resta tuttavia difficile attirare gli studenti verso la combinatoria. Il motivo? La matematica discreta non è oggetto di una teoria ben gerarchizzata. Non vi si trova vera profondità teorica, e i problemi sono difficilmente collegabili [sic.] gli uni agli altri. Ma è un difetto di gioventù: questa teoria non aspetta altro che maturare. Il mio collega americano Jack Edmonds sa invece porre buoni problemi di ottimizzazione. *\Nella stessa stanza, Edmonds sta decifrando [Tangente 131, dedicato alla matematica negli Stati Uniti.\]* Un «buon problema» è un problema che appartiene a NP e a co-NP.

Quali sono dunque le grandi problematiche generali affrontate oggi dagli specialisti di combinatoria? Ebbene, ogni teorema min-max è considerato importante, perché rivela l’esistenza di una struttura. Così, una generalizzazione della problematica dei matrimoni consiste nel cercare il numero massimo di insiemi disgiunti in una famiglia di insiemi data. È questo il problema dell’impacchettamento, o packing problem. Il problema di ottimizzazione duale consiste nel coprire tutti gli elementi con il minimo numero possibile di insiemi: è il problema di copertura, o covering problem. I grafi perfetti sono un esempio di teorema min–max: il numero minimo di colori necessari per colorare un grafo perfetto, il suo numero cromatico, coincide con il massimo numero di vertici collegati a due a due, la sua cricca massima. Questa proprietà caratterizza i grafi perfetti. Per cambiare completamente registro e parlare di oggetti più semplici, ci sono poi tutti i problemi riguardanti i polimini, oggetti geometrici elementari costituiti da piccoli quadrati unitari incollati gli uni agli altri. Assemblando due quadrati si ottiene… un domino. Ebbene, non si sa contare il numero di polimini costituiti da n quadrati, nemmeno asintoticamente: si congettura che siano meno di una costante moltiplicata per 4ⁿ. Un altro problema sintomatico dell’inferno che queste bestioline ci fanno vedere: consideriamo un polimino qualsiasi. Cerchiamo di tassellarlo con barre orizzontali di lunghezza 3, ossia trimini orizzontali, e con domino verticali, in modo che tutto il polimino sia coperto e che né i trimini né i domino si sovrappongano. Stabilire se sia possibile tassellare così il proprio polimino è un problema NP-completo! È sconfortante… Detto questo, congetturo che, limitandosi ai polimini semplicemente connessi, ossia senza buchi, il problema torni trattabile…

#### **

Endre Szemerédi (nato nel 1940).**

Infine, la teoria dei numeri pullula di problemi aperti, in particolare grazie a Erdős: le congetture di Erdős–Szemerédi e di Erdős–Turan, il problema della discrepanza di Erdős, oggetto attualmente di intense ricerche… Ma qui i matematici hanno colpito duro: Ben Green e Terence Tao hanno dimostrato nel 2005 che nell’insieme dei numeri primi esistono progressioni aritmetiche di lunghezza arbitraria. Usano strumenti di combinatoria additiva e una teoria nuova, oggi chiamata teoria ergodica. A volte, dunque, i successi ci sono!