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

Avvisi

• La validità dell'articolazione dell'esame a percorsi (vedi sezione Esami) è stata estesa fino a tutto il 2020.

• The next edition of this course will be offered in the second semester of 2021/22.

• Student hours are offered via Skype/Hangouts. Send an email to the instructor to make an appointment.

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, gli accoppiamenti, le colorature, la connettività e i grafi estremali. 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

1. Risultati di base
   • Concetti fondamentali
   • Cammini e cicli
   • Connettività
   • Alberi e foreste
   • Grafi bipartiti
   • Cicli Euleriani
   • Cicli Hamiltoniani
2. Accoppiamenti e teorema max-flow min-cut
   • Accoppiamenti in grafi bipartiti: teoremi di König e Hall
   • Accoppiamenti in grafi arbitrari: teorema di Tutte
   • Teorema di Dilworth sugli ordini parziali
   • Teorema di Menger
3. Colorature, cricche, insiemi indipendenti e insiemi dominanti
   • Teorema di Turán
   • Relazione fra numero di dominazione e grado minimo
4. 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
   • Il grafo di Rado: universalità e unicità
   • Relazione fra il grafo di Rado e il grafo di Erdős-Rényi
5. 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
6. 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
   • Ranking spettrale e geometrico

Dispense

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

1. Basics (versione dell'8 Luglio 2020)
2. Matchings and the max-flow min-cut theorem (versione dell'11 Aprile 2020)
3. Colorings, cliques, independent and dominating sets (versione del 12 Aprile 2020)
4. Random graphs and the probabilistic method (versione del 17 giugno 2020)
5. Linear algebra background (versione del 3 Giugno 2020)
6. Spectral clustering (versione del 13 Luglio 2020)
7. Finding a planted clique (versione del 5 Giugno 2020)
8. Random walks on graphs (versione dell'8 Giugno 2020)
9. Slides su ranking spettrale e geometrico (seminario di Sebastiano Vigna)

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

Fino al 31 dicembre 2020, l'esame verterà su un percorso scelto dallo studente fra questi quattro:

1. Basics + Matchings + Colorings
2. Basics + Random Graphs + Colorings
3. Linear Algebra + Spectral Clustering + Planted clique
4. Linear Algebra + Random Walks + Planted clique

Calendario lezioni

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