WOLLAN PAUL JOSEPH
(programma)
Grafi
Concetti fondamentali di grafi.
Connessione, distanza.
Esistenza di circuiti euleriani.
Gradi e numero di archi: il metodo del doppio conteggio.
Teorema di Bondy.
Alberi, foreste, permutazioni.
Teorema di Cayley sul numero di alberi di copertura.
Il codice di Prüfer.
Vertebrati e dimostrazione della formula di Cayley tramite la rappresentazione grafica di funzioni f:[n]-[n].
La decomposizione ciclica di permutazioni.
Parità di permutazioni.
Colorazione e Teoria di Ramsey.
Grafi bipartiti.
Numero cromatico.
Limitazioni per il numero cromatico e il numero di stabilità in termini del grado massimo.
Il Teorema di esistenza di Erdös di grafi con "piccoli" numeri omega e alfa ma di "grande" numero cromatico.
Combinatoria estremale.
Teorema di Mantel-Turán.
Teorema di Sperner.
Teorema di Erdös-Ko-Rado.
Tecniche di conteggio.
Il principio di inclusione-esclusione.
Applicazione al numero di permutazioni senza punti fissi.
Applicazione alla funzione di Euler.
![](/images/icon-multipage.png)
J. Korner. Appunti di Combinatoria
|