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

Avvisi

• Le lezioni inizieranno il 4 marzo 2024.

• Orario: lunedì (aula 109) e martedì (aula 304) dalle 8:30 alle 10:30 (con possibilità di iniziare alle 9:00 a partire dalla seconda lezione se tutti sono d'accordo).

Obiettivi

I grafi sono strutture matematiche fondamentali usate per modellare relazioni fra coppie di oggetti. A seguito della diffusione delle reti digitali (per esempio le reti sociali, le reti di interazione fra utenti e prodotti, le reti ipertestuali, le reti biologiche, etc.) , i grafi sono diventati uno strumento chiave per l'analisi dei dati. 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 il clustering su grafi e i cammini casuali su grafi.

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. Stochastic block models

Dispense

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

1. Basics (versione dell'11 Marzo 2024)
2. Colorings, cliques, independent and dominating sets (versione del 12 Marzo 2024)
3. Random graphs and the probabilistic method (versione del 27 Marzo 2024)
4. Linear algebra background (versione del 8 Aprile 2024)
5. Spectral clustering (versione del 27 Aprile 2024)
6. Finding a planted clique (versione del 5 Maggio 2024)
7. Random walks on graphs (versione del 14 Maggio 2024)
8. Stochastic block models (versione del 26 Maggio 2024)

• 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.