Diario delle lezioni

Alla fine di ogni lezione vengono indicati i riferimenti agli Appunti delle lezioni ([App]) e al libro "Invitation to Discrete Mathematics" di Matousek e Nesetril ([M-N])

MARZO APRILE MAGGIO

0) Lunedì  1 marzo, martedì  2 marzo, venerdì 5 marzo:
le lezioni sono state sospese per permettere ai docenti e ai ricercatori
di incontrare gli studenti per sensibilizzarli sulla protesta del mondo
accademico in atto contro il disegno di legge delega di "riforma"
dell'Università.
Si ringraziano gli studenti per aver aderito a queste iniziative.

1) Lunedì  8 marzo (2 ore).
Introduzione al corso: modalità  degli esami, ricevimento, libri di testo etc.
Prime definizioni: grafo, sottografo, grado di un vertice, grado del grafo.
Isomorfismo tra grafi. Esempi: grafi completi, cicli, cammini, bipartiti completi.
Relazione tra gradi dei vertici e numero di archi ("Hand-shaking Lemma").
[App] Capitolo 1.1
[M-N] Capitolo 3.1

2) Martedì  9 marzo (1 ora).
Definizione di passeggiata, cammino, cammino semplice, circuito, ciclo.
La relazione di equivalenza della raggiungibilità. Connessione. La distanza in un grafo.
Cominciare a svolgere gli esercizi della Scheda n. 1
[App] Capitolo 1.2
[M-N] Capitolo 3.2

3) Venerdì  12 marzo (2 ore).
Svolti gli esercizi dal n.1 al n.9 e n.12 della Scheda n. 1

4) Lunedì  15 marzo (2 ore).
Circuiti euleriani. Teorema di Euler. Connessione e numero di archi.
[App] Capitolo 1.3 e 1.4
[M-N] Capitolo 3.4

5) Martedì  16 marzo (1 ora).
Grafi aciclici. Definiziane di albero (grafo aciclico e connesso).
Caratterizzazione degli alberi: Un grafo G è un albero
se e solo se tra due qualunque vertici c'è un unico cammino
se e solo se il grafo è connesso e |E(G)|=|V(G)|-1.
Cominciare a svolgere gli esercizi della Scheda n. 2
[App] Capitolo 1.4
[M-N] Capitolo 4.1

6) Venerdì  19 marzo (2 ore).
Svolti gli esercizi n. 10 della Scheda n.2
e n. 1, 2, 5, 7, 8, 9, 13 della Scheda n. 2

7) Lunedì  22 marzo (2 ore).
Definizione di famiglie di insiemi massimali o minimali
(massimalità e minimalità rispetto a una proprietà).
Caratterizzazione degli alberi: un grafo è un albero
se e solo se è aciclico massimale
se e solo se è connesso minimale.
Caratterizzazione di una foresta in termini di numero di archi
rispetto al numero di vertici e di componenti connesse.
[App] Capitolo 1.3 e 1.4
[M-N] Capitolo 4.1

8) Martedì  23 marzo (1 ora).
Il teorema di Bondy.
[App] Capitolo 1.4

9) Venerdì  26 marzo (2 ore).
Terminata la scheda di Esercizi n.2.

10) Lunedì  29 marzo (2 ore).
Diversi approcci per la ricerca degli alberi di copertura di un connesso.
Grafi pesati. Alberi di copertura di costo minimo: l'algoritmo di Kruskal.
Grafi etichettati versus sottografi del completo.
Formula di Cayley per gli alberi di copertura del completo.
Il codice di Prufer.
[App] Capitolo 1.5 e 2.1
[M-N] Capitolo 4.3 e 4.4

11) Martedì  30 marzo (1 ora).
Il codice di Prufer: dimostrazione.
[App] Capitolo 2.2

12) Venerdì  2 aprile (2 ore).
Coefficienti binomiali. Interpretazioni combinatorie: stringhe binarie o sottoinsiemi.
Dimostrazioni combinatorie di formule che contengono il coefficiente binomiale.
Svolti gli esercizi n. della Scheda n. 3

13) Lunedì  5 aprile (2 ore).
Teorema di Cayley: il metodo di Joyal.
Alberi radicati, vertebrati, endofunzioni.
Biiezione tra vertebrati ed endofunzioni
[App] Capitolo 2.3
[M-N] Capitolo 7.4

14) Martedì  6 aprile (1 ora).
Grafi orientati. Il grafo di un'endofuznione.
Dimostrazione del teorema di Joyal.
[App] Capitolo 2.3
[M-N] Capitolo 7.4

15) Venerdì  16 aprile (2 ore).
Coefficienti multinomiali.
Svolti gli esercizi della Scheda n. 4
[App] Capitolo 2.4

16) Lunedì  19 aprile (2 ore).
Coefficienti multinomiali.
Svolti gli esercizi della Scheda n. 4
[App] Capitolo 2.4

17) Martedì  20 aprile (1 ora).
Terminata la dimostrazione del teorema di Joyal.
Permutazioni.
[App] Capitolo 2.6

18) Venerdì  23 aprile (2 ore).
Adesione allo sciopero nazionale contro il decreto di legge delega della Moratti.

19) Lunedì  26 aprile (2 ore).
Permutazioni. Permutazioni cicliche. Decomposizione ciclica di una permutazione.
Inversioni. La lunghezza di una permutazione in termini di numero minimo di scambi
di interi consecutivi necessari ottenere la permutazione data a partire dall'identità.
[App] Capitolo 2.6

20) Martedì  27 aprile (1 ora).
Parità di una permutazione. Parità in termini di numero totale dei cicli.
Teorema: la parità di una permutazione cambia moltiplicando per uno scambio.
[App] Capitolo 2.6

21) Venerdì  30aprile (2 ore).
Svolti gli esercizi della Scheda n. 5

22) Lunedì  3 maggio (2 ore).
Colorazioni di un grafo. Numero cromatico
Limitazioni del numero cromatico.
[App] Capitolo 3.1 e 3.3

23) Martedì  4 maggio (1 ora).
Grafi bipartiti. Teorema: un grafo è bipartito
se e solo se non ha cicli dispari.
[App] Capitolo 3.2

24) Venerdì  7 maggio (2 ore).
Svolti gli esercizi della Scheda n. 6 e 7

25) Lunedì  10 maggio (2 ore).
Teorema di Erdos.
[App] Capitolo 3.2

26) Martedì  11 maggio (1 ora).
Combinatoria estremale.
Massimo numero di archi per un grafo su n vertici che sia sconnesso.
Massimo numero di archi per un grafo su n vertici che sia bipartito.
Enunciato del Teorema di Mantel-Turán.
[App] Capitolo 4.1

27) Venerdì  14 maggio (2 ore).
Svolti gli esercizi della Scheda n. 7 e 8

28) Lunedì  17 maggio (2 ore).
Combinatoria estremale degli insiemi.
Famiglie di Sperner
Disuguaglianza LYM
[App] Capitolo 4.2

29) Martedì  18 maggio (1 ora).
Teorema di Sperner
[App] Capitolo 4.2

30) Venerdì  21 maggio (2 ore).
Svolti gli esercizi della Scheda n. 9

31) Lunedì  24 maggio (2 ore).
Il principio di inclusione ed esclusione (P.I.E.).
Applicazioni: la funzione di Eulero.
[App] Capitolo 5.1 e 5.2

32) Martedì  25 maggio (1 ora).
Le permutazioni senza punti fissi (derangements).
Due ricorsioni per D[n]= numero di derangements su n elementi:
D[n]=(n-1)(D[n-1] + D[n-2]) e D[n]=nD[n-1]+(-1)^n.
Applicazioni del P.I.E: calcolo esplicito di D[n].
[App] Capitolo 5.2

33) Venerdì  28 maggio (2 ore).
Svolti gli esercizi della Scheda n. 6 e 10

34) Lunedì  31 maggio (2 ore).
Applicazioni del P.I.E.: numero di suriezioni da un insieme a n
elementi in uno a m elementi
Forma equivalente per il P.I.E.
[App] Capitolo