9795991 - GRAPHS AND HYPERGRAPHS

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.

E' possibile, su richiesta, effettuare le lezioni in lingua inglese.

Al fine di rispettare il programma previsto e riportato nel syllabus, qualora l'insegnamento dovesse essere effettuato in modalità "mista" o a "distanza", potranno essere introdotte le necessari variazioni rispetto a quanto descritto in precedenza.

Concetti introduttivi e nozioni elementari di matematica combinatoria e teoria dei grafi.

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 - Problematiche aperte e temi di iricerca - 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 noti.

Esame orale con esposizione degli argomenti richiesti.

Qualora le condizioni lo dovessero richiedere, la verifica dell'apprendimento potrà essere effettuata anche per via telematica.

1) Costruzione di Bose per i Sistemi di Terne di Steiner

2) Determinazione dello spettro dei G-designs bilanciati

3) Teorema sui blocking sets per i Sistemi di Quaterne di Steiner

4) Il problema della "classificazione dei grafi"

5) Costruzione di Sistemi S(2,k,v) con il "metodo delle differenze"