Algebraic Combinatorics

A.Y. 2020/2021
6
Max ECTS
42
Overall hours
SSD
MAT/02
Language
Italian
Learning objectives
The course aims to give an introduction of graph theory and its applications.
Expected learning outcomes
Knowledge of the basic notions of graph theory and of some applications.
Course syllabus and organization

Single session

Responsible
Lesson period
First semester
Classes will be held remotely, using Zoom or a similar platform.
If in-persons exams are not possible, they will also be held remotely, using Zoom or a similar platform.
Course syllabus
Definitions and examples, equivalence of graphs, labelled graphs, subgraphs.
Eulerian graphs. The Konigsberg Bridges problem. The Chinese postman's problem
Hamiltonian graphs. The travelling salesperson problem.
Tournaments. Trees: elementary properties, enumeration of trees.
Planar graphs and colouring of graphs.
Networks and flows.
Matching. Hall's marriage theorem, Menger's theorem and their applications.
Latin squares in relation with algebraic structures.
Combinatorial circuits.
Prerequisites for admission
Basic knowledge of set theory and group theory.
Teaching methods
Traditional lectures.
Teaching Resources
F. Harary, "Graph theory", 1969
R. Wilson, "Introduction to graph theory", 1985
R. Johnsonbaugh, "Discrete mathematics", 2001
Assessment methods and Criteria
Some exercises will be assigned and published on the course webpage on the Ariel portal. Solving these exercises is a necessary condition to have access to the oral exam. In the oral exam, the student will be required to illustrate results presented during the course and will be required to solve problems regarding their applications in order to evaluate her/his knowledge and comprehension of the arguments covered as well as the capacity to apply them.

Final marks are given using the numerical range 0-30, and will be communicated immediately after the oral examination.
MAT/02 - ALGEBRA - University credits: 6
Lessons: 42 hours
Professor: Montoli Andrea
Educational website(s)
Professor(s)