La grande scienza. Combinatoria

La grande scienza. Combinatoria

Combinatoria

Secondo alcuni la combinatoria costituisce soltanto una parte della matematica, secondo altri essa non rappresenta una branca separata, ma pervade invece tutte le altre, poiché la maggior parte dei matematici si occupa almeno in parte di combinatoria. C'è chi non la considera come una parte della 'vera' matematica, ma soltanto una raccolta di giochi dilettevoli e banali. Jean Dieudonné (1982), portavoce del Bourbaki, con un misto di scetticismo e di imbarazzo afferma: "Non abbiamo ancora capito qual è il legame tra la combinatoria e la matematica concettuale".

Nella seguente esposizione cercheremo di individuare le ragioni che negli ultimi due secoli hanno determinato la crescita e l'accettazione della combinatoria nella matematica, di descriverne le tendenze più recenti e le possibili direzioni future. L'argomento è talmente vasto da rendere impossibile una rassegna completa, e abbiamo quindi scelto di procedere soprattutto per mezzo di esempi.

Dai rompicapo alla matematica

Nel XIX sec. non era chiaro quale posto occupasse la combinatoria all'interno della matematica. Anche chi si interessava di combinatoria sentiva spesso il bisogno di dissimulare il proprio lavoro definendolo una semplice soluzione di rompicapo. La prima escursione che Euler fece nella topologia fu la soluzione del problema se fosse possibile un cammino che attraversasse i ponti di Königsberg una volta sola (guerre e politica hanno poi modificato la città di Königsberg, non soltanto nel nome, ma anche per la configurazione dei ponti, per cui tale problema non si pone più).

Si deve a Euler anche l'origine dello studio dei quadrati latini con il problema degli ufficiali: "Dati 36 ufficiali di sei gradi diversi e di sei reggimenti diversi, uno per ogni grado e reggimento, è possibile sistemare i 36 ufficiali in un quadrato 6×6 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 prendeva 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 Tarry con un'analisi dettagliata di tutti i casi possibili, la seconda invece fu dimostrata falsa da Raj Chandra Bose, S.S. Shrikhande ed E.T. Parker nel 1960.

Nel XIX sec. Thomas P. Kirkman diede inizio alla teoria dei disegni con lo schoolgirls problem: "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 che sia congruo a 3 mod 6 vada bene richiamò l'attenzione di molti. I risultati furono riassunti nelle numerose edizioni del Mathematical recreations and essays di W.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 carte (il problema, sollevato da Francis Guthrie intorno al 1850 chiede di sapere se, data una qualunque carta disegnata nel piano, sia possibile colorarne le regioni con esattamente quattro colori in modo che regioni adiacenti abbiano colori diversi).

Nel corso del XX sec. la combinatoria comincia però a trovare un proprio posto nella matematica tradizionale. G.H. Hardy e J.E. Littlewood studiano 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 nascono indipendentemente in statistica, dove Ronald A. Fisher e Frank Yates sviluppano la teoria della progettazione degli esperimenti (design of experiments). A Calcutta, Bose (che aveva studiato la statistica con Fisher e i campi finiti con F.W. Levi) spinse tale idea molto avanti dando 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 (studiato da Dickson), e in 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 B. Segre, costituiscono oggi una parte fiorente della combinatoria.

Con l'avanzare del secolo si assiste a un'accelerazione di tale tendenza; sviluppi più recenti saranno presi in considerazione più avanti nella nostra esposizione. Diamo prima uno sguardo agli argomenti di cui si occupa la combinatoria.

L'oggetto della combinatoria

La combinatoria è notoriamente difficile da definire. Numerosi matematici, che non si definirebbero come studiosi di combinatoria, nelle loro ricerche fanno uso di idee e tecniche combinatorie. In termini molto generali il problema fondamentale della combinatoria è quello di stabilire se una data disposizione di oggetti secondo certe regole (come per gli ufficiali di Euler o le ragazze di Kirkman) sia possibile o meno. A una domanda di questo tipo si può rispondere sia esibendo una costruzione esplicita, sia con una dimostrazione di non esistenza; più raro è trovare una dimostrazione di esistenza non costruttiva (che può giovarsi, per es., di tecniche probabilistiche). Se la disposizione richiesta è possibile, ci si può chiedere in quanti modi si può ottenere (di solito a meno di una 'equivalenza' che deve essere specificata con precisione). Se il numero dei modi è grande, è possibile che non si sia in grado di trovare una formula esatta per esprimerlo, e che ci si debba accontentare di una formula approssimata. Un'altra tecnica utile è quella di un algoritmo per costruire le disposizioni (o anche di un algoritmo casuale che scelga una delle molte disposizioni esistenti).

tab. 1

Per fissare le idee consideriamo il problema fondamentale delle 'permutazioni e combinazioni'. Abbiamo un insieme di n oggetti, diciamo a₁,a₂,…,a_n; ne vogliamo scegliere k. In quanti modi si può fare? Occorre naturalmente essere più precisi nel formulare il problema. Conta l'ordine nel quale vengono fatte le scelte? Possiamo scegliere uno stesso oggetto più di una volta? Le risposte sono contenute nella tab. 1.

Qui ⁿP_k=n(n−1)∙∙∙(n−k+1) (il prodotto di k fattori a partire da n, ciascuno inferiore di uno a quello che lo precede), e ⁿC_k=ⁿP_k/k! (dove k! è il prodotto degli interi da 1 a k, cioè, in altre parole, il numero delle permutazioni, od ordinamenti, di k oggetti). Le lettere P e C significano rispettivamente 'permutazioni' (scelte ordinate) e 'combinazioni' (scelte non ordinate). ⁿC_k ci dice quanti sottoinsiemi di cardinalità k sono contenuti nell'insieme di cardinalità n; il numero ⁿC_k si scrive più comunemente come

Una funzione generatrice per questi numeri è

una forma del 'teorema del binomio' (per esponenti interi positivi).

Vediamo ora un problema più complicato. In quanti modi si possono ripartire i sottoinsiemi con k elementi dell'insieme {a₁,a₂,…,a_n} in modo che ciascuna parte consti di n/k sottoinsiemi che ricoprono tutti gli elementi dell'insieme di partenza (si suppone che k divida n)? Il fatto che una tale partizione sia possibile non è affatto ovvio, ed è stato dimostrato da Zsolt Baranyai nel 1975 con la teoria dei flussi nelle reti. Per k=2 l'esistenza è immediata (è il problema di stilare un calendario di n−1 partite per un torneo a n squadre in cui ogni coppia di squadre si incontra una sola volta). C'è una stima asintotica grossolana per il numero dei modi; ma per k>2 non si sa quasi nulla su questo numero.

La classificazione dell'American Mathematical Society suddivide la combinatoria in cinque sezioni: combinatoria enumerativa, disegni e configurazioni, teoria dei grafi, combinatoria estremale e combinatoria algebrica. Le ultime due sezioni sono state introdotte nel 2000, anche se gli argomenti che trattano sono molto più antichi.

Oltre a contare particolari oggetti (come, per es., famiglie di insiemi, grafi, insiemi ordinati, ecc.), la combinatoria enumerativa comprende anche tecniche di analisi per la determinazione di valori asintotici approssimati di funzioni che servono a contare. Un classico esempio è rappresentato dalla formula di Stirling che afferma che n! è uguale approssimativamente a

,

per grandi valori di n (il rapporto delle due quantità tende a 1).

Il primo e il quinto argomento sono abbastanza vicini, in quanto l'esatta enumerazione di oggetti combinatori si presta bene a essere trattata con tecniche algebriche, comprese serie formali, azioni di gruppi e lo studio delle algebre di incidenza di insiemi parzialmente ordinati. Tuttavia l'algebra compare in combinatoria in molti altri modi. Per esempio gli 'schemi di associazione' (una classe di oggetti combinatori scoperti indipendentemente in statistica, nei gruppi di permutazioni e negli algoritmi per l'isomorfismo dei grafi) sono essenzialmente la stessa cosa delle algebre di matrici reali simmetriche che ammettono una base di matrici a elementi 0 e 1, compresa la matrice identica, e la cui somma è la matrice con tutti 1. La teoria delle rappresentazioni di queste algebre ha un'importanza cruciale in combinatoria.

La teoria dei disegni riguarda disposizioni di sottoinsiemi di un insieme, o di lettere in uno schema di qualche tipo. Gli ufficiali di Euler e le collegiali di Kirkman sono prototipi dei problemi di questa area.

La combinatoria estremale si presenta generalemente in situazioni nelle quali una disposizione di un qualche tipo non è possibile. Per esempio, in un semplice problema considerato per primo da Kirkman si chiede se è possibile scegliere un insieme di sottoinsiemi con tre elementi dell'insieme {1,…,n} in modo che due elementi qualunque compaiano insieme in esattamente uno dei sottoinsiemi scelti (si tratta del problema delle collegiali senza la richiesta che le ragazze debbano camminare in fila per tre in cinque righe). Kirkman dimostrò che una soluzione è possibile se e soltanto se n è congruo a 1 o 3 mod 6; un insieme soluzione contiene esattamente n(n−1)/6 terne. Per i valori di n per i quali non vi sono soluzioni ci si possono porre le seguenti domande: qual è il massimo numero di terne tale che due elementi qualunque capitino insieme al più una volta? Qual è il minimo numero di terne tale che due qualunque elementi capitino insieme almeno una volta? La prima domanda pone un problema di packing (impacchettamento), la seconda un problema di covering (ricoprimento). Entrambe fanno parte della combinatoria estremale.

L'ultimo argomento, la teoria dei grafi, è un po' diverso. Anche se sono stati scritti più lavori sulla teoria dei grafi che su tutto il resto della combinatoria, un grafo resta comunque una struttura combinatoria molto particolare. Un grafo consta di un insieme di 'vertici', alcune coppie dei quali sono congiunte da 'spigoli'. Vi sono numerose varianti: gli spigoli possono essere orientati, uno spigolo può congiungere un vertice con sé stesso, la stessa coppia di vertici può essere congiunta da più spigoli, ecc. Tale flessibilità permette ai grafi di avere applicazioni a situazioni di tipo molto vario. Nella teoria dei grafi si possono distinguere due argomenti principali: la 'connessione', che comporta la considerazione di cammini a più passi che congiungono coppie di vertici, e le 'colorazioni': si colorano i vertici richiedendo che due vertici congiunti da un arco siano di colore diverso, oppure si colorano gli spigoli richiedendo che due spigoli incidenti a uno stesso vertice siano di colore diverso.

I problemi di connessione sono rilevanti ovviamente in questioni riguardanti flussi su reti, problemi su vertici o spigoli dominanti, ecc., mentre i problemi di colorazione nascono quando il grafo rappresenta situazioni di incompatibilità (per es., in una serie di radio trasmettitori, per via delle interferenze trasmettitori vicini devono usare frequenze diverse: quante frequenze sono richieste?). Il problema più famoso è quello dei quattro colori: si considerano le regioni come i vertici di un grafo, e due vertici sono congiunti da uno spigolo se hanno un confine comune.

Un tipo di oggetto combinatorio che supera queste divisioni è il 'matroide', inventato da Hassler Whitney per descrivere la nozione di indipendenza di un insieme di vettori di uno spazio vettoriale. Anche un grafo dà origine a un matroide: insiemi di spigoli aciclici (foreste) giocano il ruolo di insiemi indipendenti. Altri esempi provengono dalle trasversali di famiglie di insiemi. A un matroide è associato il suo 'polinomio di Tutte', che registra molte informazioni di carattere numerico sul matroide o sul grafo (compreso il numero delle colorazioni e dei flussi). I matroidi sono precisamente le strutture nelle quali l'algoritmo 'ingordo' (greedy) ha successo. Essi sono stati poi generalizzati nei 'matroidi di Coxeter', che sono collegati ai gruppi di Coxeter come i matroidi lo sono al gruppo simmetrico. Li incontreremo di nuovo in relazione alla teoria dei nodi.

Un altro principio unificante che supera le frontiere tra i diversi campi è la 'teoria di Ramsey', che Theodore Motzkin riassume nella frase "un completo disordine è impossibile". È caratteristico dei risultati di tale teoria affermare che un oggetto arbitrario contiene al proprio interno un oggetto molto più strutturato di quello di partenza. Per esempio, date sei persone a una festa, ve ne sono tre che si conoscono, oppure tre che sono estranee l'una all'altra. Più in generale, se i k-sottoinsiemi (sottoinsiemi contenenti k elementi) di un insieme con n elementi sono colorati con r colori, allora (purché n sia sufficientemente grande, per es., n≥R(k,l,r)), esiste un l-sottoinsieme con tutti i k-sottoinsiemi dello stesso colore. Più in generale ancora, gli insiemi si possono sostituire con strutture matematiche di vario tipo.

Il problema è in questo caso quello di determinare gli opportuni 'numeri di Ramsey', come il precedente numero R(k,l,r). Maggiorazioni per questo numero seguono di solito dalla dimostrazione del teorema; le minorazioni richiedono una costruzione (nel caso preso in esame, cinque persone non bastano: un pentagono rosso con un pentagono blu stellato inscritto non ha triangoli monocromatici).

Un'importante tecnica, ideata da Paul Erdös per questo problema, ma di applicabilità molto più ampia, è il 'metodo probabilistico'. Per trovare una minorazione per R(2,l,2) si prenda un insieme di n punti, e si colorino le coppie di questi di rosso e di blu a caso. Non è difficile calcolare il numero atteso degli l-sottoinsiemi monocromatici. Se n⟨2^l/2−1, questo numero è minore di 1, e quindi vi deve essere una colorazione senza l-sottoinsiemi monocromatici. Se ne conclude R(2,l,2)≥2^l/2−1. Si tratta di un buon esempio di una 'dimostrazione di esistenza non costruttiva': ci dice che la colorazione richiesta esiste, ma non dà alcun suggerimento su come costruirne una.

Teoria o tecnica?

Per molta parte della sua storia recente la matematica ha guardato alla combinatoria con sufficienza, in parte a causa della natura frivola dei problemi, e in parte per il fatto che le soluzioni richiedevano generalmente analisi lunghe e dettagliate di tutti i casi possibili e non l'applicazione di teoremi generali.

Si cita spesso il commento "la combinatoria costituisce i bassifondi della topologia", attribuito a Henry Whitehead. Anche 'veri' matematici sposarono questo punto di vista: Anthony Joseph descrisse i risultati presentati a un incontro della London Mathematical Society come "in parte di matematica combinatoria e in parte di vera matematica".

Nella biografia di Srinivasa Ramanujan, Robert Kanigel (1991) descrive Percy MacMahon in questi termini: "Era un esperto di combinatoria, una sorta di lancio di dadi nobilitato, e in questo campo aveva dato contributi abbastanza originali da essere nominato membro della Royal Society".

Non vi è alcun dubbio invece che molti matematici facciano uso di tecniche combinatorie e che il loro punto di vista sia diverso. Per esempio, Kenneth Appel dice di Roger Lyndon, uno studioso di teoria dei gruppi: "La matematica di Lyndon è elegante, le sue idee sono profonde e di largo respiro […] Una volta gli chiesi se vi fosse un filo comune nei suoi lavori, che sono così diversi e che spaziano in così tanti campi della matematica. Egli rispose di avere la sensazione che i problemi sui quali aveva lavorato erano tutti di natura combinatoria".

William T. Gowers può essere considerato il primo studioso di combinatoria vincitore di una medaglia Fields, il più alto riconoscimento per un matematico, al Congresso Internazionale dei Matematici nel 1998. Lavora in combinatoria pura e in analisi funzionale, e ha la capacità di unire le due aree (ha lavorato in teoria di Ramsey negli spazi di Banach). Nell'articolo The two cultures of mathematics (Gowers 1999; il titolo richiama deliberatamente le 'due culture', umanistica e scientifica, oggetto del classico studio di C.P. Snow), egli sostiene che i matematici tendono a dividersi in costruttori di teorie e risolutori di problemi:

È ovvio che la matematica abbia bisogno di entrambi […] È altrettanto ovvio che branche della matematica diverse richiedono doti diverse. In alcune, come nella teoria algebrica dei numeri, o in quel gruppo di teorie che va complessivamente sotto il nome di Geometria, sembra […] importante per varie ragioni acquisire una notevole conoscenza e competenza del lavoro di altri matematici: il progresso è infatti spesso il risultato di una intelligente combinazione di una vasta gamma di risultati esistenti. Inoltre, se si sceglie un problema, vi si lavora sopra per alcuni anni e infine lo si risolve, c'è il pericolo, se non si tratta di un problema molto famoso, che non venga più considerato un problema significativo.

All'altro estremo dello spettro vi è per esempio la teoria dei grafi, l'oggetto principale della quale, il grafo, si può capire immediatamente. Non si va da nessuna parte in teoria dei grafi stando seduti in poltrona e cercando di capire meglio i grafi. Né è particolarmente necessario consultare molta letteratura prima di affrontare un problema: se ovviamente è utile conoscere alcune delle tecniche più importanti, i problemi interessanti tendono a essere problemi aperti proprio perché le tecniche abituali non si applicano facilmente.

Gowers sostiene che la combinatoria eccelle in tecniche che si possono applicare a varie situazioni. Chi si occupa di combinatoria usa tali tecniche come una strumentazione, e sa in quali situazioni ciascuno strumento si può efficacemente utilizzare. Un esempio di tali strumenti è il metodo probabilistico, applicato su larga scala dalle geometrie finite all'informatica.

Naturalmente, come sottolinea lo stesso Gowers, nessun matematico e nessuna branca della matematica rientra interamente in una delle due culture da lui delineate. La combinatoria ha i propri costruttori di teorie. Tra questi è importante Gian Carlo Rota che ha scritto (assieme ad altri colleghi) una serie di monografie e di articoli dal titolo generale On the foundations of combinatorial theory (Rota 1964; Crapo e Rota 1970). Rota si interessava a quella che oggi sarebbe considerata solo una parte della combinatoria, e cioè la parte che riguarda l'enumerazione, l'algebra e gli insiemi ordinati (in particolare i numeri uno e cinque della Mathematical Subject Classification).

Tali contributi sono stati di enorme valore per la combinatoria e quasi certamente hanno migliorato lo status di questa disciplina nella comunità matematica. Rota però non definisce né precisa di cosa essa si occupi. Ciò si può vedere chiaramente da uno dei più importanti sviluppi della fine del XX sec., e cioè il lavori di Neil Robertson e Paul D. Seymour (e di altri) sui minori dei grafi. Un minore di un grafo è un sottografo ottenuto sopprimendo e contraendo spigoli. Si scrive H≤G per dire che H è un minore di G, e si vede così subito che ≤ è un ordine parziale nella classe dei tipi di isomorfismo dei grafi finiti. È chiaro che non vi sono catene discendenti infinite.

In un certo senso, la lunga serie di lavori (Robertson e Seymour 1983) è dedicata alla dimostrazione di un unico teorema: 'non vi sono anticatene di grafi finiti nella relazione di minore', ovvero, con altre parole, una classe di grafi chiusa rispetto ai minori è determinata da un numero finito di minori esclusi. Questi lavori contengono tuttavia una grande ricchezza di materiale che non si può riassumere facilmente. In parte tale materiale è descrittivo: si dà una rappresentazione di grafi mediante 'immersioni approssimate' in superfici (forse un possibile controesempio all'affermazione di Gowers che non si possono capire i grafi standosene seduti in poltrona). In parte è di tipo algoritmico: si dimostra che un certo numero di problemi di teoria dei grafi appartengono alla classe P dei problemi risolvibili in tempo polinomiale (ma la dimostrazione non è costruttiva, per cui nella maggior parte dei casi non viene fornito alcun algoritmo).

Tuttavia questo non è l'unico modo in cui un grafo può avere una struttura profonda che non si rivela a un'osservazione superficiale. Nel corso della dimostrazione della congettura di Erdös-Turán, secondo la quale ogni insieme di numeri naturali con densità inferiore positiva contiene progressioni aritmetiche arbitrariamente lunghe, Szemerédi dimostrò il cosiddetto 'lemma di regolarità'. Tale lemma afferma che ogni grafo consta, a parte un numero relativamente piccolo di vertici, di parti di dimensioni uniformi, e le interconnessioni tra queste parti hanno anch'esse una struttura uniforme. Non possiamo entrare qui nei particolari; si tratta però di un risultato che si è rivelato uno strumento cruciale nella teoria estremale dei grafi.

Rapporti con la scienza e la società

È nostra convinzione che uno dei fattori principali che hanno favorito la crescita e l'accettazione della combinatoria provenga dal di fuori della matematica.

Nel corso della storia, alcuni hanno pensato che il mondo fosse infinitamente divisibile, altri hanno aderito a qualche forma di teoria atomica. Nel rapido sviluppo della matematica nel XVIII e XIX sec., il punto di vista del continuo ha avuto il predominio. A seguito dello sviluppo del calcolo differenziale e integrale di Newton e Leibniz, sembrò che il mondo si potesse comprendere utilizzando tecniche analitiche come le equazioni differenziali. Le formulazioni di Lagrange e di Hamilton della meccanica, le equazioni di Maxwell per l'elettromagnetismo e l'equazione di Laplace, sembravano parlare di un mondo continuo che l'analisi poteva far comprendere nel modo migliore.

Uno dei primi segni di cambiamento si ebbe con il crescere di applicazioni della matematica nelle quali la rilevanza dell'analisi non era così evidente. Durante la Seconda guerra mondiale John von Neumann e Oskar Morgenstern svilupparono la teoria dei giochi, una descrizione di come si debba reagire in circostanze imprevedibili. Nella prefazione a Theory of games and economic behavior (von Neumann e Morgenstern 1944), essi scrivono: "L'importanza dei metodi matematici sembra spostarsi verso la combinatoria e la teoria degli insiemi, e allontanarsi dall'algoritmo delle equazioni differenziali che domina la fisica matematica".

Strettamente connesso a tutto ciò è lo sviluppo della ricerca operativa, una disciplina che ha sempre avuto stretti legami con la combinatoria.

Un altro elemento provenne, con la nascita della meccanica quantistica, proprio dalla roccaforte di quell''algoritmo delle equazioni differenziali'. Max Planck e Albert Einstein scoprirono che nei processi subatomici l'energia non può fluire con continuità; essa si può trasportare solo in pacchetti chiamati quanti. Così per esempio lo stato di un elettrone che orbita attorno a un nucleo atomico è descritto da quattro numeri quantistici discreti; il principio di esclusione di Pauli afferma che due elettroni non possono avere gli stessi quattro numeri quantistici; e una transizione tra stati descritti da numeri quantistici differenti assorbe o rilascia una quantità fissa di energia. Si spiegano in tal modo le linee spettrali discrete che caratterizzano gli atomi.

Più recentemente alcuni fisici, in particolare Lee Smolin e Rafael Sorkin, hanno suggerito che lo spazio-tempo è esso stesso discreto; se studiato nella scala più piccola, cioè alla 'lunghezza di Planck', assomiglia più a una rete discreta che a una varietà continua. La lunghezza di Planck è così piccola che, nella scala alla quale noi possiamo misurare, tale discretezza viene appianata, ed è per questo che le equazioni differenziali danno una buona descrizione dell'Universo. La geometria non commutativa, sviluppata da Alain Connes e da altri, è anch'essa legata alla quantizzazione dello spazio tempo.

Un terzo elemento è la consapevolezza, particolarmente in relazione alla teoria delle catastrofi sviluppata da René Thom e Christopher Zeeman, che cause continue possono avere effetti discreti. Ullica Segerstråle (2000), parlando di John Maynard Smith (un pioniere dell'applicazione della teoria dei giochi a problemi di teoria dell'evoluzione) riferisce che questi diceva: "oggi abbiamo una matematica che ci permette realmente di pensare a sistemi complessi e a cose che subiscono trasformazioni dalla quantità in qualità", cioè dal continuo al discreto, citando la biforcazione di Hopf come meccanismo di tali trasformazioni.

Dalla biologia proviene anche la consapevolezza che il linguaggio dei geni è discreto. Una molecola di DNA si può descrivere come una lunga sequenza di simboli su un alfabeto di quattro lettere (le quattro basi, adenina, citosina, guanina e timina). Una sequenza di tre lettere codifica uno dei venti amminoacidi, che sono assemblati in proteine che regolano tutti i processi che hanno luogo in un organismo vivente. Si veda il lavoro di Serafim Batzoglou e collaboratori (1998) per una descrizione di parte della matematica in uso nella genetica moderna.

Il linguaggio umano, apparentemente un flusso continuo di suoni, è stato analizzato in fonemi discreti. In un recente libro, Steven Pinker (1994) sostiene che la natura del linguaggio, natura discreta, ma infinitamente estendibile, riflette strutture discrete presenti nella mente umana. Egli riassume tale punto di vista nel seguente aforisma: "I giornalisti dicono che se un cane morde un uomo non fa notizia, ma un uomo che morde un cane sì […] Grazie alla matematica combinatoria le notizie non ci mancheranno mai".

Questa trasformazione dal continuo al discreto è alla base dell'elettronica. Il moto di particelle cariche in un campo elettromagnetico è tradizionalmente di competenza dell'equazione di Maxwell. Mediante un meccanismo come la biforcazione di Hopf è possibile, tuttavia, costruire un interruttore elettronico che ha solo due posizioni, o un transistor che può essere solamente carico o scarico. Possiamo quindi rappresentare dati discreti in un computer. Anzi, possiamo rappresentare soltanto dati discreti in un computer. Lo sviluppo della combinatoria nel XX sec. è strettamente legato alle necessità e ai problemi dell'informatica.

Non possiamo terminare questo paragrafo senza menzionare la straordinaria influenza del matematico ungherese Erdös (oggetto di due biografie recenti: Hoffman 1998; Schechter 1998). Gli interessi matematici di Erdös erano vastissimi. Egli iniziò con la teoria dei numeri, lavorando anche in analisi e in teoria degli insiemi, ma al centro dei suoi interessi vi era la combinatoria. Passò gran parte della vita senza avere una fissa dimora, viaggiando per il mondo e collaborando con centinaia di matematici. Negli anni precedenti all'invenzione delle e-mail egli contribuì notevolmente alla comunicazione tra i matematici dell'Est e dell'Ovest; ha anche ispirato un vasto corpus di ricerche (i suoi 1500 lavori oscurano la produzione di ogni altro matematico tra i moderni).

Jerrold Grossman (1997) ha dimostrato come siano aumentati gli articoli a più nomi nel XX sec., e come Erdös sia stato alla testa di tale tendenza (e quasi certamente vi contribuì). C'è un certo interesse nel 'grafo delle collaborazioni', i cui vertici sono scienziati e si ha uno spigolo tra due vertici se gli scienziati corrispondenti hanno scritto un lavoro insieme. Con la sua grande produzione, Erdös è un vertice essenziale di tale grafo, e molti matematici sanno qual è il loro 'numero di Erdös', cioè la loro distanza da Erdös nel grafo delle collaborazioni.

Erdös ha anche stimolato la ricerca divulgando la sua ampia raccolta di problemi; per la soluzione di molti di questi ha offerto un premio in denaro. Un esempio tra i più importanti dei suoi problemi è il seguente: sia A={a₁,a₂,…} un insieme di interi positivi con la proprietà che la somma degli inversi degli elementi diverge. È vero che A contiene progressioni aritmetiche arbitrariamente lunghe? Il caso particolare che motiva il problema (per il quale la risposta non è nota) è quello in cui A è l'insieme dei numeri primi. Si tratta di un problema di teoria dei numeri, ma la generalizzazione di Erdös a un insieme arbitrario lo trasforma in un problema di combinatoria.

Rapporti con la matematica

Nel 1974 si tenne a Nijenrode, in Olanda, un convegno dell'Advanced Study Institute dedicato alla combinatoria e organizzato da Marshall Hall e Jacobus van Lint. Si trattava di una delle prime presentazioni, rivolta a giovani ricercatori, della combinatoria come disciplina matematica matura. Vi erano cinque sezioni: teoria dei disegni, geometrie finite, teoria dei codici, teoria dei grafi e teoria combinatoria dei gruppi. Colpisce la presenza dei quattro lavori di teoria dei codici (Hall e van Lint 1975); pur trattandosi della sezione più giovane, iniziata con il lavoro di Richard W. Hamming e Marcel J.E. Golay alla fine degli anni 1940, nei metodi che utilizza fa intervenire la matematica più sofisticata: teoria degli invarianti, analisi armonica, somme di Gauss, equazioni diofantee. Si tratta di una tendenza destinata a proseguire. Negli anni Settanta la scuola russa (in particolare Goppa, Yuri I. Manin e Vladut) sviluppò legami tra teoria dei codici e geometria algebrica (più precisamente, con i divisori sulle curve algebriche) legami reciproci, ed entrambe le discipline ne trassero beneficio. Più di recente codici su anelli e codici quantistici hanno dato nuova vita a questi studi, con nuovi legami con la teoria degli anelli e la teoria dei gruppi.

Un altro esempio è quello del più esaltante sviluppo che si ebbe in matematica alla fine degli anni 1980 e che nacque dai lavori per i quali a Vaughan Jones fu conferita la medaglia Fields nel 1990. L'incontro tra le sue ricerche sulle tracce delle algebre di von Neumann e le rappresentazioni del gruppo delle trecce di Artin, permise di trovare un nuovo invariante dei nodi con conseguenze nella fisica matematica e in altre discipline (si veda l'elogio di Jones a opera di Joan Birman (1990) e la rassegna di quest'ultima (1991) per una descrizione di questo campo di ricerca). Più tardi si scoprì che il polinomio di Jones era un caso particolare del polinomio di Tutte, definito da William T. Tutte e Hassler Whitney per grafi arbitrari e generalizzato ai matroidi da Tutte. Resoconti della sua scoperta si trovano negli scritti di Tutte del 1998 e del 1999. Questi legami portarono a ulteriori lavori. Quelli di François Jaeger (1992) che trasse un modello di spin, e quindi un calcolo del polinomio di Kauffman, dal grafo fortemente regolare associato al gruppo semplice di Higman-Sims; quelli di Dominic James Anthony Welsh e dei suoi collaboratori (descritti in Welsh 1993) sulla complessità di calcolo dei nuovi invarianti dei nodi.

Per la loro natura, esempi di legami inattesi come questo non si possono prevedere, ma è probabile che in queste scoperte sia coinvolta la combinatoria: legami profondi in matematica sembrano spesso rivelarsi secondo schemi di carattere combinatorio.

Uno degli esempi più chiari è quello dell'ubiquità dei diagrammi di Coxeter-Dynkin A_n, D_n, E₆, E₇, E₈. Vladimir I. Arnold (si veda Browder 1976) ha proposto di interpretare questa ubiquità come un equivalente moderno di un problema di Hilbert per indirizzare lo sviluppo della matematica. Arnold osserva che tali diagrammi sono presenti in aree come le algebre di Lie (le algebre di Lie semplici su ℂ), in geometria euclidea (sistemi di radici), teoria dei gruppi (gruppi di Coxeter), teoria delle rappresentazioni (algebre di tipo a rappresentazione finita) e teoria delle singolarità (singolarità con forma di intersezione definita), e ricorda inoltre i loro legami con i poliedri regolari. A questo elenco si potrebbero aggiungere la fisica matematica (istantoni) e la combinatoria (grafi con minimo autovalore pari a −2). La teoria dei grafi fornisce inoltre la più notevole descrizione dei diagrammi: sono semplicemente i grafi connessi con tutti gli autovalori minori di 2.

Altri sviluppi riguardano i legami tra combinatoria e gruppi finiti. La classificazione dei gruppi semplici finiti (Gorenstein 1982) è il più grande sforzo di collaborazione mai compiuto in matematica, che si estende per oltre 15.000 pagine di riviste (il teorema fu annunciato nel 1980, ma la dimostrazione conteneva una lacuna che solo recentemente è stata colmata). Idee combinatorie (grafi, disegni, codici, geometrie) compaiono nella dimostrazione; forse la più notevole è la classificazione di Jacques Tits (1974) dei buildings sferici. A sua volta il risultato ha avuto un considerevole impatto in combinatoria, con conseguenze sia per oggetti simmetrici come grafi e disegni (si veda Praeger 1997) sia, più sorprendentemente, altrove, come nel lavoro di Eugene M. Luks (1982) in cui si dimostra che il problema dell'isomorfismo dei grafi di valenza limitata è in P.

Questa rassegna non sarebbe completa se non si menzionasse il lavoro di Richard Borcherds (1998) sul monstrous moonshine. Esso collega il codice di Golay, il reticolo di Leech, e il gruppo semplice detto il Mostro con le algebre di Kac-Moody generalizzate e gli operatori di vertici della fisica matematica: ne risultano anche numerose identità di prodotti del tipo reso familiare dai lavori classici di Carl Gustav Jacob Jacobi e altri.

La comunità combinatoria

La crescente collaborazione tra matematici va oltre l'esempio e l'influenza di Erdös, e la combinatoria sembra essere all'avanguardia in tale tendenza. Di seguito, elenchiamo alcuni tra gli aspetti che la caratterizzano.

a) Grandi convegni internazionali. La Southeastern Conference on Combinatorics, Graph Theory and Computing, che conta già 35 incontri, raccoglie ogni anno 500 persone. Tra gli altri importanti incontri ricordiamo gli incontri biennali inglese e italiano.

b) Riviste elettroniche. L'"Electronic journal of combinatorics", fondato nel 1994, è una delle prime riviste specialistiche di matematica in rete con referee. Le pubblicazioni elettroniche sono molto gradite agli studiosi di combinatoria: spesso le dimostrazioni richiedono una lunga casistica che le tradizionali riviste a stampa sono riluttanti a pubblicare per intero.

c) Risorse in rete. La combinatoria è particolarmente ricca di risorse in rete. Ne vedremo alcuni esempi nel prossimo paragrafo.

Gli studiosi di combinatoria si sentono per la verità una comunità a sé stante all'interno della matematica, in parte forse per via delle opinioni espresse con sufficienza da alcuni matematici. A tale atteggiamento si oppone però la crescente centralità della combinatoria nella matematica moderna e nelle applicazioni.

Consideriamo ora i problemi e le tendenze attuali della combinatoria.

La combinatoria e il computer

Le relazioni tra combinatoria e computer sono molto strette, e ognuno dei due settori di ricerca influenza l'altro. Intanto, 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 (la storia è raccontata nel libro di Robin Wilson, 2002). La 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 fosse una vera dimostrazione. Thomas Tymoczko (1980) sostenne che non si trattava di una dimostrazione perché non era possibile per un essere umano esaminarla, mentre E.R. Swart (1980) sosteneva l'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 dimostrazione del teorema, dovuta a Robertson, Daniel P. Sanders, 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 (1991) 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 girava 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 (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. Il primo esempio di enunciato di carattere matematico non dimostrabile nell'aritmetica di Peano fu scoperto da J. Paris e L. Harrington (1977), e si tratta di un problema di combinatoria (è un teorema leggermente più forte del teorema di Ramsey: si richiede che l'insieme monocromatico contenga un numero di elementi maggiore del suo elemento più piccolo). Tale enunciato non è dimostrabile 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', ovvero che 'la classe è in P', se ognuno dei problemi della classe è 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. Il 24 maggio 2000 il Clay Mathematics Institute ha stilato un elenco di sette problemi irrisolti per ciascuno dei quali viene offerto un premio di un milione di dollari: Il problema P=NP è il primo della lista (Clay Mathematics Institute 2000). 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.

Lo sviluppo dei computer e di Internet ha cambiato il modo di fare ricerca in ogni campo, e la combinatoria non è immune da tale tendenza. Vi sono però un paio di aspetti che riguardano la combinatoria in modo particolare. I programmi per i computer e i linguaggi di programmazione hanno subito una grande evoluzione, e ora un oggetto algebrico (per es., un gruppo) o uno combinatorio (per es., un grafo) si possono trattare con la stessa facilità con cui si trattano i numeri o i polinomi. Sia MAPLE che MATHEMATICA lo permettono (i linguaggi preferiti in combinatoria sono però probabilmente GAP e MAGMA). In particolare, GAP è gratuito e si può facilmente ampliare, con pacchetti condivisi che trattano grafi, codici, gruppi cristallografici e numerosi altri argomenti di interesse combinatorio.

Un'altra risorsa, essenziale per chiunque debba contare oggetti, è la On-line encyclopedia of integer sequences. Questa grande raccolta di successioni, sempre crescente, contiene ogni successione che qualcuno abbia considerato sufficientemente interessante da proporla; molto importante è il fatto che ciascuna successione è documentata con riferimenti alla letteratura. Pertanto, se avete appena contato il numero di 'ultradistribuzioni non associative' fino a 10 fareste bene a controllare nell'Encyclopedia: qualcuno può aver trovato lo stesso numero in altri contesti, e voi potreste scoprire qualcosa di interessante sul motivo per cui gli stessi numeri compaiano anche in tali altri contesti.

Tendenze e problemi

Per avere una misura delle connessioni tra la combinatoria e altre parti della matematica ci riferiamo di nuovo 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), ai gruppi topologici, gruppi di Lie (rappresentazioni), 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), topologia in basse dimensioni (nodi e concatenazioni in S³), statistica (progettazione di esperimenti), informatica (matematica discreta, algoritmi), ricerca operativa (programmazione matematica), 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. Rimandiamo il lettore alla rassegna di Peter W. Shor (1998).

È stato recentemente dimostrato da Freedman, Kitaev, Larsen, Solovay e Wang che la parte 'quantistica' di ogni computazione quantistica può essere sostituita da un singolo calcolo del polinomio di Jones di una certa treccia in una certa radice dell'unità. Come abbiamo visto, 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 Welsh (1993) e altri.

Abbiamo anche parlato del lavoro di Borcherds. Più in generale, molte identità combinatorie sono state interpretate (MacDonald et al. 1998) 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] λ:n=r₁+…+r_k, r₁≥…≥r_k>0,

vi sono due espressioni per il grado f_λ 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_λ è 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_λ è uguale al numero dei 'tableaux di Young' associati al diagramma, dove un tableau di Young è un'assegnazione dei numeri 1,…,n alle celle tale che i numeri sono 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 dei sottomoduli molto complicata. Ancora una volta vi sono regole combinatorie che danno informazioni, in generale riducendo gli elementi che entrano nei tableaux (James 1981).

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 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. È notevole che l'ultima interazione di cui abbiamo parlato sembra sia stata prevista dallo scrittore di fantascienza polacco Stanislav Lem nel romanzo La voce del padrone, del 1968. Nel racconto di Lem tuttavia la relazione tra combinatoria e teoria ergodica è molto più unilaterale. Le direzioni della ricerca all'interno della combinatoria sono forse un po' più facili da prevedere; 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 Robertson e Seymour! Vi sono anche alcuni nuovi e interessanti invarianti minori-monotoni, tra i quali uno scoperto da 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 ℝ³ senza che mai due circuiti siano intrecciati (Schrijver 1997).

Teoria dei disegni. In questo 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²+ +n+1). Esiste un piano proiettivo di ordine che non sia una potenza di un 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 n×n 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 ±1 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. Solo pochi valori sono noti. Una rassegna continuamente aggiornata si trova nell'"Electronic journal of combinatorics".

Bibliografia

Vi è una grande proliferazione di materiale in combinatoria. Ci limiteremo a citare soltanto alcune rassegne di carattere generale.

Lo Handbook of combinatorics (Graham et al. 1995) contiene rassegne eccellenti su tutta la materia (compresa la storia).

Con il titolo Surveys in combinatorics la British Combinatorial Conference pubblica dal 1977 le conferenze dei principali oratori (ai quali viene richiesta una rassegna dei risultati del loro campo di ricerca) tenute negli incontri biennali. Molte di queste si trovano nella London Mathematical Society Lecture Note Series.

Infine, l'"Electronic journal of combinatorics" presenta una sezione, Dynamic surveys, che comprende rassegne che si avvalgono del mezzo elettronico, aggiornate con regolarità dagli autori. È una raccolta ancora ridotta ma destinata a crescere.

Appel, Haken 1976: Appel, Kenneth - Haken, Wolfgang, Every planar map is four colorable, "Bulletin of the American mathematical society", 82, 1976, pp. 711-712.

Batzoglou 1998: Batzoglou, Serafim - Berger, Bonnie - Kleitman, Daniel J. - Lander, Eric S. - Pachter, Lior, Recent developments in computational gene recognition, in: Proceedings of the international congress of mathematicians, Berlin, 1998, "Documenta Mathematica" Extra Volume ICM 1998 (disponibile in http://www.mathematik.uni-bielefeld.de/documenta/xvol-icm/99/99.html).

Birman 1990: Birman, Joan S., The work of Vaughan F.R. Jones, in: Proceedings of the international congress of mathematicians, Kyoto, 1990, Tokyo, Mathematical Society of Japan/Springer, 1991, pp. 9-18.

Birman 1991: Birman, Joan S., Recent developments in braid and link theory, "Mathematical intelligencer", 13, 1991, pp. 52-60.

Borcherds 1998: Borcherds, Richard, What is moonshine?, in: Proceedings of the international congress of mathematicians, Berlin, 1998, "Documenta Mathematica" Extra Volume ICM 1998, (disponibile in http://www.mathematik.uni-bielefeld.de/documenta/xvol-icm/Fields/Fields.html).

Bose 1960: Bose, Raj Chandra - Shrikhande, S.S. - Parker, E.T., Further results on the construction of mutually orthogonal latin squares and the falsity of Euler's conjecture, "Canadian journal of mathematics", 12, 1960, pp. 189-203.

Browder 1976: Browder, Felix E., Problems of present day mathematics, in: Mathematical developments arising from Hilbert problems, "Proceedings of symposia in pure mathematics", 28, 1976, pp. 35-79.

Crapo, Rota 1970: Crapo, Henry - Rota, Gian Carlo, On the foundations of combinatorial theory: combinatorial geometries, Cambridge (Mass.), Mathematical Institute of Technology Press, 1970.

Dieudonné 1982: Dieudonné, Jean, A panorama of pure mathematics: as seen by N. Bourbaki, New York, Academic Press, 1982 (1. ed.: Panorama des mathématiques pures: le choix bourbachique, Paris, Gauthier-Villars 1977).

Gödel 1931: Gödel, Kurt, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, "Monatshefte für Mathematik und Physik", 38, 1931, pp. 173-198 (disponibile in http://www.sm.luth.se/ ˜ torkel/eget/godel.html).

Gorenstein 1982: Gorenstein, Daniel, Finite simple groups: an introduction to their classification, New York, Plenum Press, 1982.

Gowers 1999: Gowers, William Timothy, The two cultures of mathematics, in: Mathematics: frontiers and perspectives, edited by V. Arnold, M. Atiyah, P. Lax and B. Mazur, Providence (R.I.), American Mathematical Society, 1999, pp. 65-78.

Graham 1995: Handbook of combinatorics, edited by Ronald L. Graham, Martin Grötschel, László Lovász, Amsterdam-Oxford, Elsevier, 1995.

Grossman 1997: Grossman, Jerrold W., Paul Erdös: the master of collaboration, in: The mathematics of Paul Erdös, edited by Ronald L. Graham, Jeroslav Nesetril, Berlin, Springer, 1997, pp. 467-475 (vedi Erdös number project website in http://www.oakland.edu/ ˜ grossman/erdoshp.html).

Hall, Lint 1975: Hall, Marshall jr - Lint, Jacobus H. van, Combinatorics ("NATO ASI series C. Mathematical and physical sciences", 16), Dordrecht, Reidel, 1975.

Hoffman 1998: Hoffman, Paul, The man who loved only numbers, New York, Hyperion, 1998 (disponibile in http://www.paulerdos.com/).

Hollingdale 1989: Hollingdale, Stuart, Makers of mathematics, London, Penguin, 1989.

Jaeger 1992: Jaeger, François, Strongly regular graphs and spin models for the Kauffman polynomial, "Geometriae dedicata", 44, 1992, pp. 23-52.

James 1981: James, Gordon D., The representation theory of the symmetric group, Reading (Mass.), Addison-Wesley, 1981.

Kanigel 1991: Kanigel, Robert, The man who knew infinity: a life of the genius ramanujan, New York, Charles Scribner's Sons, 1991.

Lam 1989: Lam, Clement W.H. - Swiercz, S. - Thiel, Larry, The nonexistence of finite projective planes of order 10, "Canadian journal of mathematics", 41, 1989, pp. 1117-1123.

Lam 1991: Lam, Clement W.H., The search for a finite projective plane of order 10, "American mathematical monthly", 98, 1991, pp. 305-318.

Lem 1968: Lem, Stanislaw, His master's voice, London, Secker-Warburg, 1968.

Luks 1982: Luks, Eugene M., Isomorphism of graphs of bounded valence can be tested in polynomial time, "Journal of computation and systems science", 25, 1982, pp. 42-65.

MacDonald 1998: MacDonald, Ian Grant, Symmetric functions and hall polynomials, Oxford, Oxford University Press, 1998 (1. ed. Oxford, Clarendon Press, 1979).

Neumann, Morgenstern 1944: Neumann, John von - Morgenstern, Oskar, Theory of games and economic behavior, Princeton, Princeton University Press, 1944.

Paris, Harrington 1977: Paris, J. - Harrington, L., A natural incompleteness in Peano arithmetic, in: Handbook of mathematical logic, edited by Jon Barwise, Amsterdam, North-Holland, 1977, pp. 1133-1142.

Pinker 1994: Pinker, Steven, The language instinct, London, Penguin, 1994.

Praeger 1997: Praeger, Cheryl E., Finite transitive permutation groups and finite vertextransitive graphs, in: Graph symmetry, edited by Gena Hahn and Gert Sabidussi, Dordrecht-London, Kluwer Academic, 1997, pp. 277-318.

Ray-Chaudhuri,Wilson 1971: Ray-Chaudhuri, Dijen K. - Wilson, R. M., Solution of Kirkman's schoolgirl problem, "Proceedings of symposia in pure mathematics", 19, 1971, pp. 187-203.

Robertson, Seymour 1983: Robertson, Neil - Seymour, Paul D., Graph minors, I: Excluding a forest, "Journal of combinatorial theory (B)", 35, 1983, pp. 39-61.

Rota 1964: Rota, Gian Carlo, On the foundations of combinatorial theory. I: Theory of Möbius functions, "Zeitschrift für Wahrscheinlichkeitstheorie", 2, 1964, pp. 340-368.

Rota, Crapo 1970: Rota, Gian Carlo - Crapo, Henry, Combinatorial geometries, "Studies in applied mathematics", 49, 1970, pp. 109-133.

Rota, Mullin 1970: Rota, Gian Carlo - Mullin, Roland, Theory of binomial enumeration, in: Graph theory and its applications, Proceedings of an advanced seminar, University of Wisconsin Madison, 1969, edited by Bernard Harris, New York-London, Academic Press, 1970, pp. 167-213.

Rota 1970: Rota, Gian Carlo, Finite vector spaces and Eulerian generating functions, "Studies in applied mathematics", 49, 1970, pp. 239-258.

Rota 1972: Rota, Gian Carlo - Doubilet, Peter - Stanley, Richard,The idea of generating function, in Proceeding of the 6th Berkeley symposium on mathematical statistics and probability, University of California, 1970, 3 v., Berkeley, University of California Press, 1972, I, pp. 267-318.

Rota 1973: Rota, Gian Carlo - Kahaner, David - Odlyzko, Andrew M., Finite operator calculus, "Journal of mathematical analysis and applications", 42, 1973, pp. 684-760.

Rota 1974: Rota, Gian Carlo - Doubilet, Peter - Stein, Jeffrey L., Combinatorial methods in invariant theory, "Studies in applied mathematics", 53, 1974, pp. 185-216.

Schechter 1998: Schechter, Bruce, My brain is open: the mathematical journeys of Paul Erdös, New York, Simon & Schuster, 1998.

Schrijver 1997: Schrijver, Alexander, Minor-monotone graph invariants, in: Surveys in combinatorics, 1997, edited by R.A. Bailey (London Mathematical Society lecture note series), Cambridge, Cambridge University Press, 1997, pp. 163-196.

Segerstråle 2000: Segerstråle, Ullica, Defenders of the truth: the battle for science in the sociobiology debate and beyond, Oxford, Oxford University Press, 2000.

Shor 1998: Shor, Peter W., Quantum computing, in: Proceedings of the international congress of mathematicians, Berlin 1998, "Documenta Mathematica" Extra Volume ICM 1998, 3 v., I, pp. 476-486 (disponibile in http://www.mathematik.uni-bielefeld.de/DMV-J/xvol-icm/00/Shor.MAN.dvi).

Swart 1980: Swart, Edward R., The philosophical implications of the four-color problem, "American mathematical monthly", 87, 1980, pp. 697-707.

Tits 1974: Tits, Jacques, Buildings of spherical type and finite BN-pairs (Lecture notes in mathematics, 386), Berlin-New York, Springer, 1974.

Tutte 1998: Tutte, William Thomas, Graph theory as I have known it, Oxford, Clarendon Press, 1998.

Tutte 1999: Tutte,William Thomas, The coming of the matroids, in: Surveys in combinatorics, 1999, edited by John Douglas Lamb and Donald Arthur Preece (London Mathematical Society lecture notes series, 267), Cambridge, Cambridge University Press, 1999, pp. 3-20.

Tymoczko 1980: Tymoczko,Thomas, Computers, proofs and mathematicians: a philosophical investigation of the four-color proof, "Mathematics Magazine", 53, 1980, pp. 131-138.

Welsh 1993: Welsh, Dominic James Anthony, Complexity: knots, colourings and counting (London Mathematical Society lecture notes series, 186), Cambridge, Cambridge University Press, 1993.

Wilson 2002: Wilson, Robin James, Four colours suffice: how the map problem was solved, London, Allen Lane, 2002.

Siti Internet

2000 Mathematics subject classification (http://www.ams.org/msc/).

Clay Mathematics Institute, press release 24 May 2000 (http://www.claymath.org/prize problems/PressStatement.htm).

Electronic journal of combinatorics (http://www.combinatorics.org/)

GAP homepage (http://www-gap.dcs.st-and.ac.uk/ ˜ gap/).

The on-line encyclopedia of integer sequences, ed. N.J.A. Sloane (http://www.research.att.com/ ˜ njas/sequences/).