I have taught Discrete Mathematics (mostly graph theory) during Spring 2021 and Spring 2022. The course is given in Italian.
Please check the Moodle page of the course for more information.
If you are interested in doing a (bachelor or master) thesis under my supervision, please send me an email. Here are some possible research topics:
Graph theory
Graph coloring and the four colors theorem. This is probably the most popular theorem in discrete mathematics, as it is the first major theorem that was proven with massive help of computers. After the first proof by Appel and Haken in 1976, a simpler proof (still using computers) was given in 1996 by Robertson, Sanders, Seymour and Thomas. Please see here for an introduction on this proof. The thesis could explore the topic both from the mathematical and the historical point of view. There are many connections including Hadwiger's Conjecture, Snarks and Tutte's Conjecture, and chromatic polynomials.
Combinatorial optimization: algorithms and polyhedra
Maximum weight matchings
In his celebrated paper "Paths, Trees and Flowers", Jack Edmonds gave the first polynomial-time algorithm to find a maximum matching in a graph and defined the concept itself of polynomial-time algorithm (see here for a summary). Afterwards, he solved the general weighted matching problem by studying what is now called the Edmonds' matching polytope, giving birth to polyhedral combinatorics. This is a great topic for a thesis at the interface between discrete mathematics, polyhedral optimization and theoretical computer science.
Other discrete maths
Graeco-Latin squares A latin square is an n × n matrix filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Euler introduced this concept in 1782 in order to solve the 36 Officers problem, which can be formulated as finding two orthogonal latin squares (also called Graeco-Latin square ) of order 6. Euler failed, as no such squares of order 6 exist. However, Graeco-Latin squares of prime order can be constructed from finite projective planes, and a large literature now exists on the topic. The thesis could focus on sets of mutually orthogonal latin squares, computational aspects, generalizations like sudoku or the relationship with graph coloring.
