GRAPHS AND HYPERGRAPHS

Academic Year 2023/2024 - Teacher: Mario GIONFRIDDO

Expected Learning Outcomes

Teaching aims to get students to acquire the most modern methods and techniques, within the most recent combinatorial theories. The aim of the course is also to provide knowledge on the research topics currently being studied in the field of graph theory, hypergraphs and block-designs. Multiple issues of Discreet Mathematics are addressed in the course. Of all the topics studied, broad application guidelines are given.

Course Structure

Frontal lessons in which the topics provided by the program are carried out, with reports of open and still unresolved problems with the intention of stimulating students towards study and problem solving.

It is possible, on request, to take lessons in English.

In line with the programme planned and outlined in the syllabus, if the teaching were to be carried out in 'mixed mode' or 'remotely' mode, t may be necessary to introduce changes with respect to previous statements.

Learning assessment may also be carried out on line, should the conditions require it.

Detailed Course Content

Graph Theory: Introductory concepts of graph theory, flatness, connection, particular structures - Origin and historical development of modern combinatorial theories - Coloring of the vertices, coloring of edges - Open problems and research themes - Relationships between chromatic number and other parameters - Algorithms - Chromatic Polynomial and Applications - Graph Classification - Open Problems.

Hypergraph theory: Hypergraphs, concepts and parameters associated with hypergraphs - Steiner, STS, SQS, S(2,4,v), characterization, blocking sets, construction, parallelism, method of differences - G-designs, balanced and highly balanced G-desings, various cases of G-designs (graph-), method of differences for G-designs - H-designs (hypergraph-designs), construction of H-designs, method of differences.

Open problems and historical conjectures of Graph and Hypergraph theory. Results.

Textbook Information

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  4) M.Gionfriddo: "Grafi, Ipergrafi, Designs", Lezioni del corso di Grafi e Ipergrafi, A.A. 2020-2021 (notes distributed by email to students requesting them)

Course Planning

SubjectsText References
1Grafi - Ipergrafi - Sistemi d Steiner - H-designs