GRAFI E IPERGRAFI

Anno accademico 2020/2021 - 1° anno - Curriculum APPLICATIVO
Docente: Mario GIONFRIDDO
Crediti: 6
SSD: MAT/03 - Geometria
Organizzazione didattica: 150 ore d'impegno totale, 103 di studio individuale, 35 di lezione frontale, 12 di esercitazione
Semestre:

Obiettivi formativi

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.


Modalità di svolgimento dell'insegnamento

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.



Prerequisiti richiesti

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


Frequenza lezioni

Obbligatoria


Contenuti del corso

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.


Testi di riferimento

1) C. Berge: ''Hypergraphs'', North-Holland (1989)

2) C.C.Lindner-C.Rodger: ''Design Theory'', CRC Boca Raton (2007)

3) M.Gionfriddo, L.Milazzo, V.Voloshin: Hypergraphs and Designs, Nova Science, New York (2015)

 

 



Programmazione del corso

 ArgomentiRiferimenti testi
1Grafi - Ipergrafi - Sistemi d Steiner - H-designs 

Verifica dell'apprendimento

Modalità di verifica dell'apprendimento

Esame orale con esposizione degli argomenti richiesti.

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


Esempi di domande e/o esercizi frequenti

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"