teoria dei grafi 6 crediti (48 ore), laurea magistrale in Informatica DOCENTI: Nicolò Cesa-Bianchi Guest lecturers: Emmanuel Esposito e Marco Bressan

Avvisi

• Le dispense sono state aggiornate.

Obiettivi

I grafi sono strutture matematiche fondamentali usate per modellare relazioni fra coppie di oggetti. Questo insegnamento descriverà alcuni dei concetti fondamentali della teoria dei grafi, fra cui i cicli, la connettività, le colorature, le cricche. La seconda parte dell'insegnamento si occuperà di alcuni aspetti avanzati, come ad esempio i grafi casuali e la teoria spettrale dei grafi, che hanno recentemente avuto un impatto notevole sull'informatica.

Programma preliminare

1. Risultati di base
   • Concetti fondamentali
   • Cammini e cicli
   • Connettività
   • Grafi bipartiti
   • Cicli Euleriani e Hamiltoniani
2. Colorature, cricche, insiemi indipendenti e insiemi dominanti
   • Teorema di Turán
   • Relazione fra numero di dominazione e grado minimo
3. Grafi casuali ed il metodo probabilistico
   • Il grafo casuale di Erdős-Rényi
   • Teorema di Erdős sull'esistenza di grafi con alto calibro e numero cromatico
   • Proprietà che valgono asintoticamente per quasi tutti i grafi
   • Valori asintotici del numero di clique e del numero cromatico
4. Analisi spettrale
   • Sparsità normalizzata di un taglio
   • Matrice Laplaciana per grafi regolari
   • Diseguaglianze di Cheeger per grafi regolari e algoritmo di Fiedler
   • Estensione a grafi non regolari e Laplaciano normalizzato
   • Ricerca di una clique innestata in un grafo casuale
5. Cammini casuali su grafi
   • Spettro della matrice di adiacenza di un grafo
   • Teorema di Perron-Frobenius per matrici simmetriche e non negative
   • Camminata casuale su un grafo connesso, convergenza alla distribuzione stazionaria
   • Velocità di convergenza
   • Analisi del tempo di mixing per la camminata casuale pigra
   • Consenso distribuito e matrici di gossip
6. Teoria dei minori
   • Proprietà fondamentali
   • Congettura di Hadwiger
   • Minori proibiti
   • Il teorema di Robertson-Seymour
   • Decomposizioni ad albero e il teorema excluded grid

Dispense

Versioni preliminari in aggiornamento costante. Per favore segnalate eventuali errori.

1. Basics (versione dell'8 Marzo 2022)
2. Colorings, cliques, independent and dominating sets (versione del 20 Marzo 2022)
3. Random graphs and the probabilistic method (versione del 27 Marzo 2022)
4. Linear algebra background (versione del 5 Giugno 2022, aggiunto Teorema di Courant-Fischer)
5. Spectral clustering (versione del 13 Aprile 2022)
6. Finding a planted clique (versione del 27 Aprile 2022)
7. Random walks on graphs (versione dell'8 giugno 2022)
8. Graph Minors 1 (versione del 23 Maggio 2022)
9. Graph Minors 2 (versione del 25 Maggio 2022)
10. Graph Minors 3 (versione del 30 Maggio 2022)

• Reinhard Diestel, Graph Theory (5th edition), Springer, 2017.
• Noga Alon and Joel H. Spencer, The Probabilistic Method (3rd edition), John Wiley & Sons, 2008.
• Daniel A. Spielman, Spectral and Algebraic Graph Theory. Draft, 2019.
• Luca Trevisan, Lecture Notes on Graph Partitioning, Expanders and Spectral Methods, 2016.
• Luca Trevisan, Lecture 7 (Planted clique), Beyond Worst-Case Analysis. Autunno 2017.

Esami

L'esame consiste in una prova orale che comprende anche le dimostrazioni spiegate a lezione. La data viene fissata su appuntamento e il voto verrà verbalizzato nel primo appello utile.

Calendario lezioni

Sfogliate le pagine del calendario e cliccate sulle date per trovare i riassunti e le date delle prossime lezioni.