GRAFI E IPERGRAFI

L'insegnamento si propone di far acquisire agli studenti i metodi e le tecniche più moderne, nell'ambito delle teorie combinatorie più recenti. Scopo del corso è anche fornire conoscenze sui temi di ricerca attualmente più studiati nell'ambito della teoria dei grafi, degli ipergrafi e dei block-designs. Nell'ambito del corso vengono affrontate molteplici problematiche di Matematica Discreta. Di tutti i temi studiati si danno ampi orientamenti di carattere applicativo.

Lezioni frontali in cui vengono svolti gli argomenti previsti dal programma, con segnalazioni di problematiche aperte e ancora irrisolte con l'intenzione di stimolare gli studenti verso lo studio e la risoluzione dei problemi.

Nozioni elementari di matematica combinatoria.

Obbligatoria

Teoria dei Grafi: Concetti introduttivi della teoria dei grafi, planarità, connessione, strutture particolari - Origine e sviluppo storico delle moderne teorie combinatorie - Colorazione dei vertici, colorazione degli spigoli - Problemtiche aperte - Relazioni tra numero cromatico e altri parametri - Algoritmi - Polinomio cromatico e applicazioni - Classificazione dei grafi - Problemi aperti.

Teoria degli Ipergrafi: Ipergrafi, concetti e parametri associati agli ipergrafi - Sistemi di Steiner, STS, SQS, S(2,4,v), caratterizzazione, blocking sets, costruzioni, parallelismo, metodo delle differenze - G-designs, G-desings bilanciati e fortemente bilanciati, casi vari di costruzione dei G-designs (graph-designs), metodo delle differenze per i G-designs - H-designs (hypergraph-designs), costruzione di H-designs, metodo della matrice delle differenze.

Problemi aperti e Congetture storiche della teoria dei Grafi e degli Ipergrafi, risultati ottenuti.

Esame finale. Nessuna verifica durante lo svolgimento delle lezioni.

Classificazione dei grafi. Numerocromatico nei grafi planari. Condizione di esistenza dei Sistemi di Steiner. G-designs bilanciati. Spettro negli H-designs.