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.