5 Calcolo combinatorio 5 A Trattati generali 5 AE Esposizioni elementari 5 M Monografie 5 P Proceedings 5 XA Problemi combinatori classici 5 XB Disegni e configurazioni 5 XC Teoria dei grafi M. CERASOLI/F. EUGENI/M. PROTASI: Elementi di matematica discreta. Zanichelli 1988. K. JACOBS: Einfhrung in die Kombinatorik. De Gruyter 1983. G. ROTA: On the foundations of combinatorial theory 1: Theory of Mbius functions. Zeitschr. Wahrsch. 2 (1964), 340-368. R. STANLEY: Enumerative combinatorics 1. Wadsworth 1986. Il Cerasoli/Eugeni/Protasi il miglior libro di calcolo combinatorio in assoluto. Riunisce praticamente tutti i campi del calcolo combinatorio in un unico testo, in capitoli distinti, chiarissimo, contiene molti esempi ed esercizi. Anche se in un trattato generale su tanti argomenti devono mancare le tecniche pi avanzate, ad esempio le matroidi o la teoria degli invarianti, i temi ci sono tutti. E' un testo moderno e aggiornato, leggibilissimo, un ottimo acquisto. Costa 32.000 Lire. I problemi del calcolo combinatorio moderno vengono formulti nel linguaggio insiemistico. Denotiamo con /n l'insieme {1,...,n}. I numeri binomiali vengono definiti calcolando il numero dei sottoinsiemi di /n che posseggono k elementi. I numeri di Fibonacci sono i membri Fn della successione 1,1,2,3,5,8,13,21,..., in cui ogni termine la somma dei due che lo precedono. Si dimostra che Fn+1 il numero dei sottoinsiemi di /n che non contengono due numeri consecutivi. I numeri di Fibonacci si ritrovano un p dappertutto, hanno legami con la sezione aurea, con la crescita di piante, appaiono in acustica e nella struttura dei cristalli. Se con (XY) denotiamo l'insieme di tutte le applicazioni dall'insieme X nell'insieme Y, allora valgono le formule card(/n/a)=an, e card(/n/a,biiettive)=n!, come si impara al primo anno. Si trova poi card(/n/a,iniettive)=(a)n:=a(a-1)(a-2)...(a-n+1), mentre card(/n/a,suriettive) un p pi complicato. Assumiamo di avere una libreria con a scaffali ed n libri. In quanti modi possiamo disporre i libri sulla libreria? Naturalmente ogni libro diverso dagli altri. Il numero cercato a(a+1)(a+2)...(a+n-1). 20 studenti hanno affittato una casa, in cui possono abitare esattamente 20 persone: 4 al pianoterra, 7 al primo piano, 4 al secondo piano, 5 al terzo. Allora gli studenti si possono distribuire sui vari piani in 20!/(4!7!4!5!) modi. Una ragazza dispone di 200 perle di vetro bucate, tutte diverse, e ne vuole fare 4 collane, una con 100 perle, una con 60, le altre due con 20 perle ciascuna. In quanti modi pu farlo? Questo problema pi difficile dei precedenti, ed molto importante, ad esempio per le applicazioni in fisica statistica. Il numero cercato 200!/(100.60.20.20.2). Mentre alcuni di questi problemi si trovano con metodi improvvisati, andando avanti bisogna introdurre tecniche pi adeguate. Un antico e potente metodo per lo studio di problemi combinatori l'uso di serie formali. Assumiamo che cerchiamo i termini ao,a1,a2,a3,... di una successione definita da un certo problema combinatorio. A questa successione associamo la serie formale ao+a1x+a2x2+a3x3+..., che viene anche chiamata funzione generatrice della successione. La x qui un'indeterminata; se la serie ha un raggio di convergenza positivo, talvolta si considera anche la funzione (nel senso dell'analisi) che la serie determina all'interno del suo cerchio di convergenza, ma molte propriet della successione possono essere studiate con manipolazioni puramente formali. Se ad esempio moltiplicate la serie con 1-x, otterrete una nuova serie, i cui coefficienti sono le differenze an-an-1, se la moltiplicate invece con 1+x+x2+x3+..., i coefficienti del prodotto sono le somme ao+a1+a2+a3+...an, e vediamo che tutto ci un analogo discreto del teorema fondamentale del calcolo integrale. Ricordiamo che 1+x+x2+x3+... l'inversa di 1-x nell'ambito delle serie formali. Un disegno a blocchi una coppia (X,B), dove X un insieme finito non vuoto e B un insieme di sottoinsiemi non vuoti di X, detti blocchi. La teoria dei disegni a blocchi ha molte applicazioni ed ha avuto un grande sviluppo negli ultimi anni. Uno strumento essenziale nella costruzione di disegni a blocchi la teoria dei gruppi finiti. Ma la teoria estremamente complicata. Il problema pi famoso per i disegni a blocchi fu posto nel 1851 da Thomas Kirkman: Variando leggermente l'originale, lo formuliamo cos: 15 ragazze di un collegio cenano ogni sera insieme. Ci sono 5 tavoli a 3. E' possibile formare i gruppi a 3 in modo, che ogni ragazza si trova esattamente una volta alla settimana a cenare insieme con ciascuna delle sue compagne? Nell'originale le ragazze vengono portate a spasso per sette domeniche di seguito in 5 righe a 3. La risposta s e la soluzione fu gi trovata da Kirkman stesso. Solo molto pi tardi stato dimostrato che il problema analogo per n ragazze (sempre con tavoli a 3) ha soluzione se e solo se n della forma n=6a+3. La dimostrazione, trovata da Ray-Chaudhuri/Wilson nel 1971, molto difficile. Il problema di Kirkman un problema per i disegni a blocchi, perch corrrisponde evidentemente al dover trovare un disegno a blocchi (/15,B), dove ogni blocco contiene esattamente 3 elementi, e tale che esiste una partizione di B in sottofamiglie tale che ogni sottofamiglia una partizione di /15. Un quadrato latino di ordine n uno schema quadratico di nxn caselle, riempite con i numeri 1,...,n in modo tale che ogni riga ed ogni colonna contengono ogni numero esattamente una volta. Due quadrati latini dello stesso ordine si dicono ortogonali, se per ogni coppia ordinata (i,j) di questi numeri esiste una casella, tale che i appare in quella casella nel primo quadrato, j nel secondo. Per n=1,2,6 non esistono quadrati latini ortogonali di ordine n, mentre ne esistono per ogni altro n. Assumiamo di avere tre insiemi A,B,C. Allora card(ABC)=cardA+cardB+cardB-card(AB) - card(AC) - card(BC) + card(ABC). Questa formula e la sua estensione a pi insiemi si chiama il principio di inclusione-esclusione. Una potente generalizzazione fornita dalla teoria dell'algebra di incidenza di un insieme parzialmente ordinato, propugnata come strumento intrinseco del calcolo combinatorio per la prima volta nell'articolo di Giancarlo Rota. Assumiamo che sull'insieme /n sia dato un ordine parziale e consideriamo la matrice nxn, che all'(i,j)-esimo posto ha 1, se ij, e 0 altrimenti. Questa matrice si chiama la matrice zeta dell'insieme parzialmente ordinato; essa in pratica la funzione caratteristica dell'ordine parziale, se viene considerato come sottoinsieme di /nx/n. Si dimostra che la matrice zeta invertibile, la sua inversa detta matrice di Mbius. Mediante essa si arriva a un calcolo "integro-differenziale" per ogni insieme parzialmente ordinato finito, o, pi in generale, localmente finito, cio tale che ogni intervallo finito. Questo argomento l'argomento principale del libro di Stanley, che contiene moltissimi esempi, talvolta in forma un p condensata. Il libro di Cerasoli/Eugeni/Protasi contiene anche capitoli sulla teoria dei codici, sulla teoria dei grafi, sulla complessit computazionale dei problemi, sugli algoritmi su grafi. In tedesco esiste il libro di Konrad Jacobs, un matematico tedesco molto noto, che un'esposizione semplice e molto bella del calcolo combinatorio classico. H. LNEBURG: Tools and fundamental constructions of combinatorial mathematics. Bibliographisches Institut 1989. Un bellissimo testo di calcolo combinatorio, che mette in risalto soprattutto i legami con l'algebra e con la teoria dei numeri. Il libro contiene tutti i dettagli e moltissimi algoritmi in Pascal. Il contenuto spesso alquanto diverso da quello dei libri citati sopra, e potrebbe essere riussunto nell'etichetta algebra combinatoria. L'esposizione molto chiara, il libro scritto in TEX dallo stesso autore. Il libro contiene alla fine una parte dedicata alla storia del calcolo combinatorio e della teoria di numeri, estremamente interessante, seguita da una bibliografia commentata. R. STANLEY: Combinatorics and commutative algebra. Birkhuser 1983. Ad ogni intervallo di un insieme parzialmente ordinato localmente finito si pu associare un complesso simpliciale, i cui simplessi sono le catene dell'intervallo. Cos' un complesso simpliciale, lo impareremo nel corso di topologia. Si dimostra che la funzione di Mbius dell'intervallo pu essere calcolata immediatamente dalla caratteristica di Euler del complesso simpliciale. La caratteristica di Euler rimane per invariata, se il complesso simpliciale viene sostituito da un complesso simpliciale omotopo, e ci permette di usare le tecniche della topologia algebrica in calcolo combinatorio, cio in un campo della matematica discreta. Questa uno degli esempi pi belli dei profondi legami tra le varie discipline matematiche. Questo secondo libro di Stanley espone questa teoria. Contiene anche un'altra interpretazione: Ad ogni complesso simpliciale si pu associare un anello commutativo. In questo modo diventa possibile da una parte studiare una certa classe di anelli, importante in geometria algebrica, con l'uso della topologia algebrica, e viceversa si possono ricondurre problemi della topologia algebrica o del calcolo combinatorio a problemi dell'algebra commutativa. P. DEMBOWSKI: Finite geometries. Springer 1989. D. HUGHES/F. PIPER: Projective planes. Springer 1982. C. LAM: The search for a finite projective plane of order 10. American Math. Monthly 98 (1991), 305-318. Un piano proiettivo finito un disegno a blocchi (X,B), in cui l'intersezione di due blocchi distinti consiste sempre di esattamente un punto, mentre per due punti distinti esiste esattamente un blocco che li contiene, e in cui infine esiste un quadrangolo non degenerato, cio esistono 4 punti tali che 3 di loro non appartengono mai allo stesso blocco. In un piano proiettivo i blocchi vengono detti anche rette del piano. Si vede abbastanza facilmente che per ogni piano proiettivo finito esiste un numero n, tale che ogni retta contiene esattamente n+1 punti. n si chiama l'ordine del piano. Solo nel 1988 si riusc a dimostrare, con uso massiccio di un supercomputer, che non esiste un piano proiettivo di ordine 10. La storia e l'affidabilit di questa dimostrazione discussa nel lavoro di Clement Lam. Siccome i calcoli necessari erano estremamente lunghi, garantito statisticamente che nel corso dei conti il computer deve avere commesso degli errori a causa degli inevitabili malfunzionamenti del hardware! Il caso n=12 sembra attualmente fuori portata anche del supercomputer. M. AIGNER: Combinatorial theory. Springer 1979. C. BERGE: Principles of combinatorics. Academic Press 1971. L. COMTET: Advanced combinatorics. Reidel 1974. I. GOULDEN/D. JACKSON: Combinatorial enumeration. Wiley 1983. D. STANTON/D. WHITE: Constructive combinatorics. Springer 1986. Questi sono trattati generali molto rinomati, non tutti presenti in biblioteca. L'Aigner una volta c'era, ma sparito da anni. E' un testo che espone soprattutto i principi astratti: morfismi, insiemi parzialmente ordinati e reticoli, funzioni di conteggio, algebre di incidenza, funzioni generatrici, matroidi, teoria delle trasversali. Nell'introduzione si definisce il calcolo combinatorio come il conteggio e l'ordinamento di morfismi. Il libro di Comtet contiene una miriade di formule, difficile la leggere, ma utile come manuale. G. ANDREWS: The theory of partitions. Cambridge UP 1981. Il libro di Andrews un testo importante che non esiste in biblioteca e che non ho mai visto. Le partizioni qui sono partizioni di un numero, ad esempio 23=10+4+4+3+2 una partizione di 23. Contare queste partizioni molto difficile, infatti la teoria delle partizioni, apparentemente innocua, immensa. Essa riappare sempre di nuovo nella profondit di discipline matematiche tutte diverse tra di loro, come teoria dei numeri, teoria degli invarianti, algebre di Lie, fisica statistica, rappresentazioni di gruppi, funzioni ellittiche. Sulla combinatoria delle partizioni si trova molto materiale anche nel libro di Comtet. J. RIORDAN: An introduction to combinatorial analysis. Wiley 1958. H. WILF: Generating functionology. Academic Press 1990. Il Riordan un classico di calcolo combinatorio, che utilizza soprattutto le funzioni generatrici. Il Wilf dovrebbe essere molto simile, ma non lo conosco. A. JOYAL: Une thorie combinatoire des sries formelles. Advances Math. 42 (1981), 1-82. M. MENDEZ/J. YANG: Mbius species. Advances Math. 85 (1991), 83-128. O. NAVA/G. ROTA: Plethysm, categories, and combinatorics. Advances Math. 58 (1985), 61-88. Date due serie formali f e g in una indeterminata x, si pu formare la loro somma, il loro prodotto, e, quando g(0)0, la composizione f(g(x)). La teoria delle specie, introdotta nel lavoro di Joyal, d interpretazioni di queste operazioni in termini insiemistici e categoriali. Questa nuova teoria brevemente spiegata all'inizio dell'articolo di Nava/Rota. Il recente lavoro di Mendez/Yang combina le specie con le matrici di Mbius. I. BARONCELLI: Ottimizzazione genetica. Tesi, Ferrara 1991. A. RECSKI: Matroid theory and its applications. Springer 1989. D. WELSH: Matroid theory. Academic Press 1976. Se per un sottoinsieme A di uno spazio vettoriale definiamo A^:=(sp.vett.^A), l'operatore ^ ha tutte le propriet dell'operatore di chiusura in uno spazio topologico tranne una: i.g. si avr (AB)^A^B^. Soddisfa invece un altro assioma: x(Ay)^ e non xA^ implica y(Ax)^. Da questo assioma si pu dedurre il teorema dello scambio di Steinitz, da cui segue soprattutto che se uno spazio vettoriale possiede una base finita, allora ogni altra base possiede lo stesso numero di elementi. Questa osservazione si trova per la prima volta nell'Algebra di Waerden, e Hassler Whitney introdusse nel 1935 le matroidi come strutture in cui essenzialmente dato un operatore ^ che soddisfa questi stessi assiomi. La teoria delle matroidi diventa a un certo punto piuttosto astratta, ha per parecchie applicazioni nella teoria dei grafi, nella teoria di grossi sistemi, nell'ottimizzazine combinatoria. Il trattato standard il Welsh, anche il libro di Aigner citato in precedenza contiene un grosso capitolo sulle matroidi. Secondo una recensione, il libro di Recski interessante e fornisce molte applicazioni e algoritmi, richiede per la conoscenza della teoria di base. Il secondo capitolo della tesi di Irene Baroncelli contiene un'introduzione alla teoria e qualche applicazione. K. BONGARTZ/W. BORHO/D. MERTENS/A. STEINS: Farbige Parkette. Birkhuser 1987. B. GRNBAUM/G. SHEPHARD: Tilings and patterns. Freeman 1987. Tiling significa piastrellamento, pattern disegno o ornamento (su una tovaglia per esempio). Si studiano piastrellamenti e ornamenti nel piano, usando gruppi di simmetria e metodi topologici. Il Grnbaum/Shephard contiene moltissime illustrazioni su 690 pagine. Guardare. La materia un trastullo degli specialisti dei gruppi di Lie, come mostra il volumetto di Bongartz ecc., che contiene anche molte illustrazioni in colore, tutto prodotto con programmi al computer fatti in casa. L. BEGNOZZI: Grafi e algoritmi sui grafi. Tesi, Ferrara 1991. D. FULKERSON (c.): Studies in graph theory. 2 volumi. MAA 1975. (La MAA la Mathematical Association of America, la seconda associazione matematica americana) C. NASH-WILLIAMS: Hamilton circuits. In Fulkerson, pag. 301-360. Tutti sanno o possono immaginare cosa sia un grafo: consiste di vertici connessi da spigoli. Se gli spigoli non hanno direzione, il grafo si dice simmetrico, altrimenti orientato. Un cammino su un grafo si dice di Hamilton, se senza ripetizione di vertici (tranne l'ultima volta se il cammino chiuso) e se tocca tutti i vertici. Il problema di un viaggiatore che nel suo viaggio vuole visitare un certo numero di luoghi, senza passare per uno di questi luoghi due volte, equivalente alla ricerca di un cammino di Hamilton su un grafo. Un altro esempio si ha nell'industria chimica, quando n materiali devono essere trattati chimicamente e si dispone di un unico recipiente in cui questi trattamenti possono avvenire. Il costo di ripulitura del recipiente sia costante e non dipenda dal materiale che si appena trattato. Assumiamo anche che esistano coppie di materiali p e q, per cui se prima viene trattato il materiale p, poi non sia necessaria la ripulitura del recipiente prima del trattamento di q. E' possibile determinare una successione di trattamento di materiali che non richieda alcuna pulitura del recipiente? Si vede subito che questo problema equivalente alla ricerca di un cammino di Hamilton in un grafo. E si pu fare addiritura in modo che dopo il trattamento dell'ultimo materiale si possa ricominciare dal primo? In questo caso bisogna cercare un cammino di Hamilton chiuso. C. BERGE: The theory of graphs and its applications. Wiley 1962. C. BERGE: Graphes et hypergraphes. Dunod 1970. F. HARARY: Graph theory. Addison-Wesley 1969. D. KNIG: Theorie der endlichen und unendlichen Graphen. Teubner, Leipzig 1986. O. ORE: Graphs and their uses. Random House 1963. O. ORE: Theory of graphs. American Math. Soc. 1962. La teoria dei grafi ha moltissime applicazioni: In fisica, chimica, ingegneria, informatica, genetica, psicologia, antropologia, sociologia, economia, linguistica, e naturalmente all'interno della matematica stessa. In ambito matematico, la teoria dei grafi ha legami con la teoria dei gruppi, la teoria delle matrici, l'analisi numerica, la probabilit, la topologia, il calcolo combinatorio. E' una teoria molto vasta, a pi che di una teoria si tratta di una grande collezione di risultati. Il testo di riferimento il libro di Harary, ma nei due libri di Berge si trovano molte informazioni in pi. In tedesco esiste la nuova edizione del vecchio trattato di Knig, in alcuni punti teorici ancora attuale. I libri di Ore contengono molti esempi concreti e sono piacevoli da leggere. Un grafo planare un grafo che pu essere rappresentato in modo tale che i vertici siano punti del piano e gli spigoli segmenti di rette, senza che gli spigoli si intersechino. Due grafi non planari sono K3,3 e K5. K5 il grafo che si ottiene, disegnando 5 punti distinti sul piano e congiungendoli tutti tra di loro. K3,3 invece il grafo che si ottiene, disegnando 2 file di 3 punti ciascuna una sotto l'altra e congiundo tutti i punti della prima fila con quelli della seconda. Si pu dimostrare che non c' nessun modo per disegnare i due grafi nel piano (usando solo spigoli che sono segmenti di rette o almeno poligoni), senza che gli spigoli si intersechino. La dimostrazione molto facile, quando si usa la caratteristica di Euler. Vedere a pag. 155-157 nella tesi di Lorena Begnozzi. Un famoso teorema di Kuratowski, abbastanza difficile da dimostrare, afferma che un grafo planare se e solo se non contiene nessun sottografo che sia una suddivisione di K3,3 o di K5. K. APPEL/W. HAKEN: The four colour problem. In Steen, Mathematics today, pag. 153-180. K. DEVLIN: Mathematics: The new golden age. Penguin Books 1988. P. HALMOS: Has progress in mathematics slowed down? American Math. Monthly 97 (1990), 561-588. La famosa congettura dei quattro colori era per molto tempo uno dei grandi problemi irrisolti della matematica. La dimostrazione stata dimostrata solo nel 1976 da Appel e Haken, con un impiego massiccio di dimostrazioni delegate al calcolatore. Tale congettura affermava che 4 il numero minimo di colori necessari a colorare una mappa disegnata su di un piano in modo tale che mai due regioni confinanti abbiano lo stesso colore. Naturalmente i bordi devono essere sufficentemente regolari. L'articolo di Halmos contiene tra l'altro alcuni chiarimenti su ci che si deve intendere con "bordo sufficientemente regolare". Pi lungo e esauriente il settimo capitolo del libro di Devlin, dove si trovano illustrazioni e indicazioni storiche e bibliografiche. J. GRAVER/M. WATKINS: Combinatorics with emphasis on the theory of graphs. Springer 1977. L. MIRSKY: Transversal theory. Academic Press 1971. Se (X,B) un disegno a blocchi, abbiamo la relazione naturale xB tra i punti x di X e gli elementi B di B, che sono per definizione sottoinsiemi di X. Assumiamo che adesso siano dati due insiemi qualsiasi X e B, e che sia data una relazione q tra X e B, che possiamo anche identificare con un'applicazione q:B--->P(X). La tripla (X,B,q) si chiama allora un piano su X. Si tratta evidentemente di un concetto che ancora pi generale di quello di disegno a blocchi e permette di formulare praticamente tutti i problemi del calcolo combinatorio, anche se non sempre con la stessa intuitivit delle presentazioni classiche. Anche i grafi possono essere considerati come piani. Il libro di Graver/Watkins espone il calcolo combinatorio come parte della teoria dei piani. La materia diventa cos molto algebrica, le tecniche sono spesso alquanto potenti, ma non sempre trasparenti. Una parte importante della teoria dei piani la combinatorica delle trasversali, che esposta nel libro di Mirsky e in quello di Aigner, citato all'inizio. R. GRAHAM/B. ROTHSCHILD/J. SPENCER: Ramsey theory. Wiley 1980. Una partita nel totocalcio pu finire con i risultati 1,x,2. Se risultato significa questo, allora su 4 partite ci devono essere 2 risultati uguali. Se 6 amici vanno in un ristorante, in cui vengono offerti 5 primi diversi, due di loro dovranno mangiare lo stesso primo. Questo si chiama il principio di Dirichlet: Se si mettono n+1 palline in n cassetti, almeno uno dei cassetti conterr 2 palline. E' importante per il proprietario di una gelateria sapere, che esiste un numero r, tale che per ogni insieme G di almeno r gusti (diversi tra di loro) per un qualsiasi cliente esiste un sottoinsieme X di G di 10 gusti tale che ogni combinazione di 3 gusti da X piaccia al cliente, oppure esiste un sottoinsieme Y di G di 14 gusti tale che nessuna combinazione di 3 gusti da Y piaccia al cliente. Il teorema vale pi in generale: Siano dati tre numeri r,a,b. Allora esiste un numero r=r(r,a,b), cio dipendente da r,a,b, tale che per ogni insieme G di almeno r gusti (diversi tra di loro) per un qualsiasi cliente esiste un sottoinsieme X di G di a gusti tale che ogni combinazione di r gusti da X piaccia al cliente, oppure esiste un sottoinsieme Y di G di b gusti tale che nessuna combinazione di r gusti da Y piaccia al cliente. Questo il teorema di Ramsey (1903-1930), che una generalizzazione del principio di Dirichlet. Perch? V. BERGELSON/H. FURSTENBERG/N. HINDMAN/Y. KATZNELSON: An algebraic proof of van der Waerden's theorem. L'Ens. Math. 35 (1989), 209-215. H. FURSTENBERG: Recurrence in ergodic theory and combinatorial number theory. Princeton UP 1981. K. HOFMANN/J. LAWSON/J. PYM (c.): The analytical and topological theory of semigroups. De Gruyter 1990. N. HINDMAN: The semigroup bN and its applications to number theory. In Hofmann/Lawson/Pym, 347-360. Una passeggiata un insieme finito di numeri naturali che sono equidistanti tra di loro. Una passeggiata quindi della forma {a,a+d,a+2d,...,a+(k-1)d} con a,d,kN, e k1. Un sottoinsieme di N si dice bello, se per ogni n contiene una passeggiata con n elementi. Nel 1926 Waerden dimostr che, se N unione di un numero finito di sottoinsiemi A1,...,Ak, allora almeno uno di questi sottoinsiemi bello. Ricordiamo che Waerden nato nel 1903, quindi allora aveva 23 anni. Come dice Jacobs nel suo libro di calcolo combinatorio, a pag. 102, questa proposizione del giovane Waerden rappresenta una delle prodezze matematiche pi prestigiose del 20-esimo secolo. Il lavoro di Bergelson/Furstenberg/Hindman/Katznelson (riportato quasi per intero nell'articolo di Hindman) contiene una dimostrazione topologica astratta di questo teorema, utilizzando la teoria dei semigruppi e la compattificazione di Stone/Cech bN dei numeri naturali. bN l'insieme di tutti gli ultrafiltri su N con la topologia che si ottiene prendendo come base per gli aperti gli insiemi della forma {D|DultrafiltrosuNconAD}, dove A percorre tutti i sottoinsiemi di N. Per chi familiare con queste tecniche, la dimostrazione topologica del teorema di van der Waerden molto breve e trasparente e dimostra la potenza dei metodi astratti. In questo caso si tratta di strumenti che appartengono alla dinamica topologica, una disciplina che fa parte dell'analisi armonica. I legami tra queste discipline e la teoria dei numeri sono esposti nel libro di Furstenberg, considerato il maggiore esperto nel campo della dinamica topologica. Il teorema di Waerden appartiene a sua volta alla teoria di Ramsey, di cui si parlava prima. Seguiamo la spiegazione all'inizio del lavoro di Hindman. Un tipico problema della teoria di Ramsey il seguente: Sia dato un insieme X e una collezione di sottoinsiemi di X, che chiamiamo sottoinsiemi "belli". Si pu dire che, ogni volta che X rappresentato come unione di un numero finito di insiemi, almeno uno di questi deve essere "bello"? Qui si vede da dove deriva il legame con gli ultrafiltri; impareremo infatti in topologia che un filtro un ultrafiltro se e solo se ogni volta che l'unione di un numero finito di insiemi appartiene a questo filtro, almeno uno di questi insiemi gli appartiene.