COMBINATORIA
Corso di laurea in INFORMATICA
|
Docente |
Num. Telefono |
E-mail |
Orario Ricevimento |
Stanza |
|
Lezioni: Prof. János Körner |
06 4991 8353 |
Mercoledì ore 10.30-12.30 |
340 |
|
· 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.
· APPUNTI DEL
CORSO (Ultima modifica:
7 aprile 2008)
· 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).
·
http://mathworld.wolfram.com/topics/DiscreteMathematics.html
· On-line encyclopedia of Integer Sequences.
In caso di insuccesso non è possibile presentarsi in un altro appello della stessa sessione.