Programma del corso di
Matematica Discreta I: Combinatoria
A.A. 1998/99
Prof. Jānos Korner, Dott. Sergio De Agostino

L'obiettivo del corso č di illustrare alcune tecniche fondamentali di dimostrazione in combinatoria.

Grafi
Concetti fondamentali di grafi. Connessione, distanza. Esistenza di circuiti Euleriani. Gradi e numero di archi: il metodo del doppio conteggio.

Alberi, foreste e permutazioni
Teorema di Cayley sul numero degli alberi di copertura. Il codice di Prufer. Coefficienti multinomiali e la dimostrazione ricorsiva della formula di Cayley. Vertebrati e la dimostrazione della formula di Cayley tramite la rappresentazione grafica di funzioni f:  n - > n. La decomposizione ciclica di permutazioni. Paritā di permutazioni. Conteggio di permutazioni con determinati vincoli di precedenza. L'algoritmo di Kruskal per l'albero di copertura di costo minimo.

Colorazione e il teorema di Ramsey
Grafi bipartiti. Numero cromatico. Limitazioni per il numero cromatico e il numero di stabilitā in termini di grado massimo. Teorema di Brooks. Teorema Ramsey per grafi; il teorema di esistenza di Erdos di grafi con "piccoli" numeri w e a ma di "grande" numero cromatico.

Combinatoria estremale
Teorema di Mantel-Turan, di Sperner e di Erdos-Ko-Rado.

Tecniche di conteggio
Il principio di inclusione-esclusione. Il numero delle permutazioni "sconvolgenti" (derangement).

Testi di riferimento:
J. H. Van Lint - R. M. Wilson: "A course in combinatorics", Cambridge University Press (1992)

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

Indietro