combinatòria

Termine con cui è anche chiamata l'algebra combinatoria, disciplina che studia, piuttosto che le strutture algebriche classiche (gruppo, anello, corpo, ecc.), le strutture algebriche di tipo più semplice, particolarmente importanti per i calcolatori elettronici, tra le quali i loop, i monoidi, i reticoli.

Combinatoria, Peter J. Cameron (da Enciclopedia della Scienza e della Tecnica)

Secondo alcuni la combinatoria costituisce soltanto una parte della matematica, secondo altri non rappresenta una branca separata dalle altre ma le pervade tutte, poiché la maggioranza dei matematici si occupa almeno in parte di essa. Anche chi se ne interessa sente spesso il bisogno di dissimulare il proprio lavoro, definendolo una semplice soluzione di rompicapi. Jean Dieudonné, portavoce del gruppo Bourbaki, con un misto di scetticismo e di imbarazzo affermava che non era ancora chiaro quale fosse il legame tra la combinatoria e la matematica concettuale.

Eppure, il primo approccio di Leonhard Euler alla topologia fu la risoluzione del problema dell’esistenza di un cammino che attraversasse i ponti della città di Königsberg una sola volta. A lui si deve anche l’origine dello studio dei quadrati latini, nella forma del cosiddetto problema degli ufficiali: «Dati trentasei ufficiali di sei gradi diversi e di sei reggimenti diversi, uno per ogni grado e reggimento, è possibile sistemare i trentasei ufficiali in un quadrato 636 in modo che in ogni riga e colonna vi sia uno e un solo ufficiale per ogni grado e reggimento?». Euler sospettava che la risposta fosse negativa, e che lo stesso dovesse accadere se invece di 6 si fosse preso un qualunque «numero non parimenti pari» (cioè un numero congruo a 2 mod 4), mentre sapeva che era positiva in tutti gli altri casi. La prima parte della congettura era vera, come fu stabilito da Gaston Tarry con un’analisi dettagliata di tutti i casi possibili, la seconda invece fu dimostrata falsa da Raj C. Bose, Sharad S. Shrikhande ed E.T. Parker nel 1960.

Nel 19° sec. Thomas P. Kirkman diede inizio alla teoria dei disegni con il problema delle collegiali: «Quindici collegiali escono tre alla volta per sette giorni di seguito. Si chiede di redigere un calendario in modo tale che due qualunque di esse non escano mai insieme due volte». Come per sottolinearne la natura frivola, il problema fu pubblicato nel “Lady’s and Gentleman’s Diary” nel 1850. Kirkman stesso risolse il problema, e il fatto che un qualunque numero di ragazze congruo a 3 mod 6 andasse bene richiamò l’attenzione di molti. I risultati furono riassunti nelle numerose edizioni dei Mathematical recreations and essays di Walter W. Rouse Ball, ma per la soluzione definitiva si dovette attendere l’opera di Dijen Ray-Chaudhuri e Richard Wilson pubblicata nel 1971.

Un altro esempio della confusione sulla natura e la destinazione dei risultati di combinatoria si ebbe quando Arthur Cayley pubblicò nel 1879 un articolo nel quale veniva ravvivato l’interesse per il problema dei quattro colori. L’articolo uscì nei “Proceedings of the Royal Geographical Society”, malgrado i geografi non avessero mai mostrato un particolare interesse per il numero minimo di colori da usare nelle loro mappe (il problema, sollevato da Francis Guthrie intorno al 1850, chiede di sapere se, data una qualunque carta geografica, sia possibile campire le regioni con quattro colori in modo tale che regioni adiacenti abbiano colori diversi).

Nel corso del 20° sec. la combinatoria cominciò però a trovare un proprio posto nella matematica tradizionale. Godfrey H. Hardy e John E. Littlewood studiarono il comportamento asintotico del numero p(n) di partizioni di un intero n (le partizioni di n sono i modi di scrivere n come somma di interi positivi, senza tenere conto dell’ordine). Il legame fondamentale tra problemi di conteggio di oggetti e l’analisi è dato dalle serie formali di potenze, i coefficienti delle quali sono appunto i numeri che contano gli oggetti in considerazione; le idee fondamentali risalgono, anche in questo caso, a Euler.

Problemi collegati con quello degli ufficiali o con quello di Kirkman nacquero indipendentemente in statistica, dove Ronald A. Fisher e Frank Yates svilupparono la teoria della progettazione degli esperimenti. A Calcutta, Bose diede notevole impulso allo sviluppo delle geometrie finite (l’analogo delle classiche geometria proiettiva e geometria polare su campi finiti). Sviluppi in altri campi, come quello della costruzione dei gruppi semplici finiti e quello della geometria algebrica, spingevano nella stessa direzione. Le geometrie finite, che da qui presero spunto per poi crescere velocemente grazie anche ai lavori pionieristici di Beniamino Segre, costituiscono oggi una parte fiorente della combinatoria. Con l’avanzare del secolo si assiste a un’accelerazione di tale tendenza.

Combinatoria e computer

Le relazioni tra combinatoria e computer sono molto strette, e ognuno dei due settori di ricerca influenza l’altro. In primo luogo, il computer ha avuto in combinatoria un impatto maggiore che in altre parti della matematica, perché è in grado di compiere lunghe analisi, caso per caso, evitando l’errore umano. Nel 1977 Kenneth Appel e Wolfgang Haken annunciarono la dimostrazione della congettura dei quattro colori con l’aiuto del computer. Tale dimostrazione è interattiva: i matematici e il computer si dividono il compito di generare e controllare le circa 2000 configurazioni da considerare. L’annuncio provocò una grande agitazione. Alcuni pensavano che una dimostrazione del genere non potesse essere considerata tale. Thomas Tymoczko sostenne questa tesi con l’argomento che non era possibile per un essere umano esaminarla, mentre Edward R. Swart si schierò sul fronte opposto. In ogni caso la controversia concentrò l’attenzione sul problema di cosa sia una dimostrazione. La storia ha un risvolto ironico: in una nuova prova del teorema dovuta a Neil Robertson, Daniel P. Sanders, Paul D. Seymour e Robin Thomas, gli autori sostituiscono il procedimento a mano con il computer perché più affidabile dell’uomo!

In seguito si assisterà a teoremi di combinatoria stabiliti mediante calcoli al computer ancora più lunghi. Clement W.H. Lam e i suoi collaboratori hanno dimostrato la non esistenza di un piano proiettivo di ordine 10 con un programma che ha girato per molti anni (suddiviso in vari casi: per quelli difficili un computer Cray lavorava in background, per i più facili si usava un microcomputer).

Nella direzione opposta, l’informatica è stata una ricca fonte di ispirazione e di problemi per la combinatoria. Anche prima della costruzione dei computer, questioni di carattere teorico hanno portato a risultati importanti. Kurt Gödel nel 1931 dimostrò che vi sono enunciati veri sui numeri naturali che non si possono dedurre dagli assiomi di un sistema standard come quello di Peano. Tale risultato ebbe un grande significato per i fondamenti della matematica, ma l’enunciato non dimostrabile di Gödel non aveva un significato matematico diretto. Il primo esempio di enunciato di carattere matematico non dimostrabile nell’aritmetica di Peano fu scoperto da Jeff Paris e Leo Harrington e si tratta di un problema di combinatoria. Tale enunciato non è dimostrabile a partire dagli assiomi in quanto la corrispondente funzione di Paris-Harrington cresce più rapidamente di ogni funzione calcolabile. Sono stati scoperti numerosi altri esempi di questo fenomeno, la maggior parte di natura combinatoria.

Più recentemente l’attenzione si è spostata dalla calcolabilità alla complessità di calcolo: se qualcosa è calcolabile, ci si chiede quali risorse (tempo, memoria, ecc.) sono necessarie per tale calcolo. Una classe di problemi si dice calcolabile in tempo polinomiale, o in P, se ognuno di essi è risolvibile in un numero di passi maggiorato da un polinomio nelle dimensioni dell’input. Una classe è in NP se si ha lo stesso risultato ammettendo un certo numero di tentativi di indovinare il risultato (o, ciò che è lo stesso, se una soluzione proposta si può controllare in un numero polinomiale di passi). Il grande problema irrisolto della teoria della complessità chiede di sapere se P è uguale a NP. Si tratta di un problema importante per la combinatoria perché è noto che molti problemi intrattabili (tra cui quello dell’esistenza di un ciclo hamiltoniano in un grafo) sono in NP. Nel caso – improbabile – di una soluzione positiva, vi sarebbero algoritmi veloci per tutti questi problemi.

Tendenze e problemi

Per avere una misura delle connessioni tra la combinatoria e altre parti della matematica ci riferiamo alla Mathematical Subject Classification. Essa mostra rinvii dalla combinatoria alla logica matematica e ai fondamenti (calcolabilità e teoria della ricorsività), a ordini, reticoli, strutture algebriche ordinate (aspetti algebrici degli insiemi parzialmente ordinati), alla teoria dei numeri (successioni e insiemi, geometria dei numeri, partizioni, campi finiti e anelli), alla teoria dei gruppi e sue generalizzazioni (rappresentazioni, teoria geometrica dei gruppi), alle funzioni speciali (funzioni ipergeometriche e funzioni ipergeometriche fondamentali), alla geometria (sistemi di chiusura geometrica, geometrie finite e particolari strutture di incidenza), alla geometria convessa e discreta (politopi e poliedri), alla topologia in basse dimensioni (nodi e concatenazioni in S³), alla statistica (progettazione di esperimenti), all’informatica (matematica discreta, algoritmi), alla ricerca operativa (programmazione matematica), a informazione e comunicazione (circuiti).

Molte delle tendenze più interessanti della moderna combinatoria sono strettamente legate ad altre parti della matematica, e non possono esserne separate facilmente. Per esempio, molti pensano che uno degli sviluppi tecnologici che avranno luogo in questo secolo interesserà la computazione quantistica. Al momento, la teoria è molto più avanti delle applicazioni. Si sa che, se sarà costruito, un computer quantistico potrà risolvere efficientemente problemi come la fattorizzazione di interi molto grandi e il problema del logaritmo discreto. Ciò è di grande interesse perché questi due problemi sono fondamentali per la sicurezza dei notissimi codici a chiave pubblica RSA e El-Gamal; la sicurezza di tali codici sarebbe notevolmente compromessa se i computer quantistici fossero effettivamente costruiti.

È stato recentemente dimostrato da Michael H. Freedman, Alexei Kitaev, Michael Larsen, Robert Solovay e Zhengang Wang che la parte quantistica di ogni computazione appunto quantistica può essere sostituita da un singolo calcolo del polinomio di Jones di una certa treccia in una particolare radice dell’unità. Il polinomio di Jones è un caso particolare del polinomio di Tutte di un matroide; la complessità di calcolo del polinomio di Tutte è stata studiata da Dominique Welsh e altri.

Più in generale – si pensi per esempio al lavoro di Richard E. Borcherds – molte identità combinatorie sono state interpretate come formule del denominatore o formule dei caratteri di Weyl per algebre di Lie o per oggetti algebrici a esse connessi (superalgebre di Lie, algebre di Kac-Moody).

Inoltre, in combinatoria algebrica una vecchia idea è ancora attivamente oggetto di studio. Le rappresentazioni irriducibili del gruppo simmetrico S_n sono etichettate dalle partizioni di n, e regole combinatorie danno informazioni sulle rappresentazioni. L’esempio più semplice è la dimensione. Data una partizione [3]

vi sono due espressioni per il grado f_l della corrispondente rappresentazione irriducibile. Ciascuna è definita in termini del diagramma della partizione, che ha k righe con r_i caselle nella i-esima riga (allineate a sinistra). La prima formula afferma che f_l è uguale a n! diviso il prodotto delle lunghezze dei ‘ganci’ delle celle nel diagramma, dove un gancio consta di una cella e di quelle che si trovano o sotto di essa nella stessa colonna o alla sua destra nella stessa riga. La seconda formula afferma che f_l è uguale al numero delle tavole di Young associate al diagramma, dove una tavola di Young è un’assegnazione dei numeri 1,…,n alle celle tale che i numeri siano decrescenti lungo ogni colonna e lungo ogni riga.

Molti altri parametri della teoria delle rappresentazioni si possono calcolare attraverso una simile combinatoria. Mediante l’impiego di metodi che risalgono a Hermann Weyl si possono anche ottenere informazioni sulle rappresentazioni dei gruppi di Lie classici.

Più interessante è la situazione per le rappresentazioni in caratteristica diversa da zero. Le rappresentazioni non sono ora sempre semisemplici, e una rappresentazione indecomponibile può avere una struttura di sottomoduli molto complicata. Ancora una volta vi sono regole combinatorie che danno informazioni, in generale riducendo gli elementi che entrano nelle tavole.

Un altro legame del tutto inatteso è dato dalla nuova dimostrazione del teorema di Szemerédi (secondo cui ogni insieme di numeri naturali con densità superiore positiva contiene progressioni aritmetiche arbitrariamente lunghe) per la quale Harry Furstenberg ha utilizzato metodi di teoria ergodica. Ciò ha portato a un incontro molto ravvicinato tra combinatoria e teoria ergodica, nel quale una arricchisce l’altra. La teoria ergodica studia le iterazioni di trasformazioni di spazi di misura; un caso importante è quello in cui lo spazio consta di funzioni sui naturali o sugli interi e la trasformazione è indotta da uno shift. Le iterazioni dello shift descrivono efficacemente la combinatoria dei naturali.

Interazioni come queste, con linee di confine che si incrociano, sono per loro natura imprevedibili; tuttavia le direzioni della ricerca nell’ambito della combinatoria sono forse un po’ più facili da immaginare. Vediamone alcune.

Colorazioni di grafi

Vi sono due problemi principali, uno per la colorazione di vertici (congettura di Hadwiger), l’altro di spigoli (congettura della colorazione per liste). La congettura di Hadwiger: un grafo i cui vertici non si possono colorare con meno di n colori (in modo che vertici adiacenti abbiano colori diversi) contiene il grafo completo K_n come minore (si osservi che in caso positivo si avrebbe una generalizzazione del teorema dei quattro colori, perché è noto che un grafo planare non può avere K₅ come minore). La congettura della colorazione per liste: supponiamo che gli spigoli di un grafo si possano colorare con n colori in modo che due spigoli incidenti a uno stesso vertice non abbiano mai lo stesso colore. Allora, assegnata una lista L(s) di colori per ogni spigolo s (scelti da un insieme arbitrariamente grande di colori, ma contenente soltanto n colori), è possibile colorare ogni spigolo con un colore della lista in modo che la condizione sugli spigoli incidenti continui a valere (la congettura analoga per colorazioni dei vertici è falsa).

Minori

I minori dei grafi si generalizzano in modo naturale ai matroidi; c’è quindi molto lavoro da fare per generalizzare i risultati di Neil Robertson e Paul Seymour! Vi sono anche alcuni nuovi e interessanti invarianti minori-monotoni, tra i quali uno scoperto da Yves Colin de Verdière, che ha dato luogo a risultati e congetture interessanti, compreso un criterio che stabilisce condizioni in base alle quali un grafo si possa immergere in R³ senza che mai due circuiti siano intrecciati.

Teoria dei disegni

In tale campo di ricerca sono stati formulati problemi molto difficili. Generalizzando la definizione di Kirkman, un sistema di Steiner S(t,k,v) consta di un insieme di blocchi, o k-sottoinsiemi di un insieme di v punti, tali che t punti qualunque appartengano a un unico blocco. Per escludere casi banali supponiamo v>k>t>. I problemi elencati di seguito sono aperti. (a) Esiste un sistema di Steiner S(t,k,v) con t≥6? (b) Un piano proiettivo di ordine n è un sistema di Steiner S(2,n+1,n^2₊n+1). Esiste un piano proiettivo di ordine che non sia una potenza di un numero primo? (Un esempio di ordine n, se n è una potenza di un primo, si costruisce facilmente a partire dal campo finito di ordine n).

Jacques Hadamard aveva dimostrato che una matrice nxn, A=(a_ij), a elementi che soddisfano ∣a_ij∣≥1 per ogni i, j ha determinante al più n^n/2 in valore assoluto, con uguaglianza se e solo se tutti gli elementi sono uguali a 61 e AA^T=nI. Una matrice che verifichi queste due condizioni si chiama matrice di Hadamard. L’ordine n di una tale matrice, se è maggiore di 2, deve essere multiplo di 4. Una congettura afferma inoltre che esistono matrici di Hadamard per tutti gli ordini divisibili per 4.

Enumerazione

È noto che alcune classi di strutture sono difficili da contare. Alcuni esempi sono: quadrati latini, spazi lineari, poliomini, politopi, nodi. Inoltre, quanti elementi contiene il reticolo distributivo libero con n generatori? (È lo stesso numero delle famiglie di sottoinsiemi di un insieme di n elementi i cui membri sono a due a due non confrontabili rispetto all’inclusione).

Numeri di Ramsey

Il problema di trovare valori esatti per i numeri di Ramsey classici R(k,l,r) è uno dei più difficili della combinatoria e solo pochi valori sono noti.