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.

J. Korner. Appunti di Combinatoria

J.H.van Lint, R.M.Wilson, A course in Combinatorics, 2nd edition. Cambridge University Press (2001).

P.J.Cameron, Combinatorics. Topics, techniques, algorithms. Cambridge University Press (1994).

R.L.Graham, D.E.Knuth, O.Patashnik, Matematica Discreta. Hoepli (1992).

J.Matousek, J.Nesetril, Invitation to Discrete Mathematics. Clarendon Press (1998).

S. Jukna
Extremal Combinatorics
With Applications in Computer Science