Follow us
Search

GRAPHS AND HYPERGRAPHS

Academic Year 2023/2024 - Teacher: ELENA MARIA GUARDO

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 Discrete Mathematics are addressed in the course. Of all the topics studied, broad application guidelines are given.


The couse has the following objectives:

Knowledge and understanding:

- Mathematic Instruments in graph theory such as theorems and algoritms will be provide in the course. They permit to develop mathematical abilities in reasoning and calculation. These abilities could permit to resolve known problems by mathematical model.

Applying and knowledge and understanding:

- At the end of course student will be able to get knowledge for a tightened use of new mathematical techniques and an understanding of treated arguments in such way to link them each other.

Making judgements:

- Course is based on logical-deductive method which wants to give to students authonomus judgement useful to understanding incorrect method of demonstration also, by logical reasoning, student will be able to face not difficult problems in graph theory with teacher's help.

Communication skills:

- In the final exam, student must show for learned different mathematical techniques an adapt maturity on oral communication using also multimedia tools.

Learning skills

- Autonomously student will be able to face application and theoretical arguments which could be studied in new classes or in different working fields; for example flow theory and connectivity have huge application on telecommunications field (Local Area Network and Metropolitan Area Network: LAN e MAN), on electrical and communication fields (Industrial design).


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.

Required Prerequisites

Basic notions of Combinatorics and Graph Theory

Attendance of Lessons

Strongly recommended

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
1Graphs, Hypergraphs, Steiner Systems, H-Designs1),2),3),4)

Learning Assessment

Learning Assessment Procedures

Oral exams on course contents.

Final grades will be assigned taking into account the following crieria:

Rejected: Basic knowledges have not been acquired. The student is not able to solve simple exercises.

18-23: Basic knowledges have been acquired. The student solves simple exercises and has sufficient communications skills and making judgements.

24-27: All the  knowledges have been acquired. The student solves all the proposed exercises making few errors and has good communications skills and making judgements.

28-30 cum laude: All the knowledges have been completely acquired. The student applies knowledge and has excellent communications skills, learning skills and making judgements.

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


Information for students with disabilities and / or SLD

To guarantee equal opportunities and in compliance with the laws in force, interested students can ask for a personal interview in order to plan any compensatory and / or dispensatory measures, based on the didactic objectives and specific needs. It is also possible to contact the referent teacher CInAP (Center for Active and Participated Integration - Services for Disabilities and / or SLD) of our Department, prof. Daniele.

Examples of frequently asked questions and / or exercises

1) Bose construction for Steiner Systems

2) Balanced G-Designs

3) Blocking sets for quadrule Steiner Systems

4) Classifications of graphs

5) Construction of S(2,k,v) Systems