Advanced geometry (2018/2019)

Course code
Name of lecturer
Giuseppe Mazzuoccolo
Giuseppe Mazzuoccolo
Number of ECTS credits allocated
Academic sector
Language of instruction
II semestre dal Mar 4, 2019 al Jun 14, 2019.

Lesson timetable

Go to lesson schedule

Learning outcomes

This course provides students with the basic concepts of Graph Theory and the basics of Discrete and Computational Geometry. At the end of the course, the student will know the main classical theorems of graph theory, in particular about structural properties, colorings, matchings, embeddings and flow problems. He/she will also be familiar with basic Discrete Geometry results and with some classical algorithms of Computational Geometry. He/she will have the perception of links with some problems in non mathematical contexts. he/she will be able to produce rigorous proofs on all these topics and he/she will be able to read articles and texts of Graph Theory and Discrete Geometry.


-Definitions and basic properties.
-Matching in bipartite graphs: Konig Theorem and Hall Theorem. Matching in general graphs: Tutte Theorem. Petersen Theorem.
-Connectivity: Menger's theorems.
-Planar Graphs: Euler's Formula, Kuratowski's Theorem.
-Colorings Maps: Four Colours Theorem, Five Colours Theorem, Brooks Theorem, Vizing Theorem.

-Convexity, convex sets convex combinations, separation. Radon's lemma. Helly's Theorem.
-Lattices, Minkowski's Theorem, General Lattices.
-Convex independent subsets, Erdos-Szekeres Theorem.
-Intersection patterns of Convex Sets, the fractional Helly Theorem, the colorful Caratheodory theorem.
-Embedding Finite Metric Space into Normed Spaces, the Johnson-Lindenstrauss Flattening Lemma
-Discrete surfaces and discrete curvatures.

-General overview: reporting vs counting, fixed-radius near neighbourhood problem.
-Convex-hull problem: Graham's scan and other algorithms.
-Polygons and Art Gallery problem. Art Gallery Theorem, polygon triangulation.
- Voronoi diagram and Fortune's algorithm.
- Delaunay triangulation properties and Minimum spanning tree.

Reference books
Author Title Publisher Year ISBN Note
Diestel Graph Theory (Edizione 5) Springer 2016
Matousek Lectures on Discrete Geometry (Edizione 1) Springer 2002

Assessment methods and criteria

To pass the exam, students must show that:
- they know and understand the fundamental concepts of graph theory
- they know and understand the fundamental concepts of Discrete and Computational Geometry
- they have analysis and abstraction abilities
- they can apply this knowledge in order to solve problems and exercises and they can rigorously support their arguments.

Written test (2 hours).
The written exam on Graph Theory consists of three/four exercises and two questions (1 on general definition / concepts and 1 with a proof of a theorem presented during the lectures).

Oral Test (Mandatory)
It is a discussion with the lecturer on definitions and proofs discussed during the lectures about Discrete and Computational Geometry.