Program of

Mathematical Methods (part B)

(Prof. M. Ferri)

The course consists of two parts. Part A is held by Prof. Nicola Arcozzi Ph.D. Part B is dedicated to Graph Theory.
The following program will be updated during the course.

Theory

1. Graphs and subgraphs (1.1 to 1.7; 1.8 up to first 24 lines of page 19).
Theorems: Thm. 1.1 (with proof), Cor. 1.1 (with proof), Thm.1.2 (with proof)
Exercises: 1.1.3, 1.2.1, 1.2.3, 1.2.4, 1.2.10, 1.2.12(c), 1.3.1, 1.4.4, 1.5.1, 1.5.4, 1.5.5, 1.5.6(a), 1.6.1, 1.6.11, 1.7.2.
2. Trees (2.1; 2.2 up to Cor. 2.4.2; 2.3 up to Thm. 2.7; 2.4; 2.5 up to Thm. 2.10 excluded).
Theorems: Thm. 2.1 (with proof), Thm.2.2 (with proof), Cor. 2.2, Thm. 2.3, Thm. 2.4, Cor. 2.4.1, Cor. 2.4.2 (with proof), Thm. 2.7, Thm. 2.8 (with proof), Thm. 2.9.
Exercises: 2.4.3.
3. Connectivity (3.1; 3.2 up to Cor. 3.2.2).
Theorems: Thm. 3.1, Thm. 3.2, Cor. 3.2.1, Cor. 3.2.2
4. Euler tours and Hamilton cycles (4.1; 4.2 up to Cor. 4.4; 4.3 up to Thm. 4.7; 4.4: first 10 lines).
Theorems: Thm. 4.1, Cor. 4.1, Thm. 4.2, Thm. 4.3 (with proof), Thm. 4.4, Cor. 4.4, Thm. 4.7.
Exercises: 4.1.1, 4.1.2.
5. Matchings (5.1, 5.2; 5.4: first 8 lines).
Theorems: Thm. 5.1, Thm. 5.2, Cor. 5.2, Lemma 5.3, Thm. 5.3.
Exercises: 5.1.1(a), 5.1.5(b).
6. Edge colourings (6.1: first 20 lines, Thm. 6.1; 6.2: Thm. 6.2; 6.3: first 21 lines).
Theorems: Thm. 6.1, Thm. 6.2.
7. Independent sets and cliques (7.1; 7.2 up to the table of numbers).
Theorems: Thm. 7.1 (with proof), Cor. 7.1 (with proof), Thm. 7.2, Thm. 7.3, Thm. 7.4.
8. Vertex colourings (8.1 up to Cor. 8.1.2; 8.2; 8.3: only Thm. 8.5; 8.4; 8.5 up to Thm. 8.7; 8.6).
Theorems: Thm. 8.1 (with proof), Cor. 8.1.1 (with proof), Cor. 8.1.2 (with proof), Thm. 8.4, Thm. 8.5, Thm. 8.6 (with proof), Cor. 8.6, Thm. 8.7.
Exercises: 8.4.1, 8.4.2, 8.4.3(a) 8.6.2.
9. Planar graphs (9.1 excluding Thm. 9.1; 9.2; 9.3; 9.5 without lemmas and without proof; 9.6 up to Thm. 9.12 excluded, without proof; mind the footnotes!).
Theorems: Thm. 9.2 (with proof), Thm. 9.3 (with proof), Thm. 9.4 (with proof), Thm. 9.5 (with proof), Cor. 9.5.1 (with proof), Cor. 9.5.2 (with proof), Cor. 9.5.3 (with proof), Cor. 9.5.4 (with proof), Cor. 9.5.5 (with proof), Thm. 9.10, Thm. 9.11, footnote at p. 157.
Exercises: 9.1.2.
10. Directed graphs (10.1; 10.2 up to Cor. 10.1; 10.4 first 17 lines; 10.5; 10.6 up to Thm. 10.5).
Theorems: Thm. 10.1 (with proof), Cor. 10.1 (with proof), Thm. 10.5 (with proof).
Exercises: 10.1.1

There will be short expositions of basic Topological Data Analysis (NOT part of the exam program): Gradient, divergence and Laplacian on graphs , the "smallworld" model for networks, some topology of surfaces some persistent topology.

Exercises

Modelling problems with graphs. Writing matrices associated with graphs. Computing graph invariants. Solving elementary graph problems: Shortest path problem (by Dijkstra's Algorithm), Connector problem (by Kruskal's algorithm), Chinese postman problem (by Fleury's algorithm), finding minimal coverings and maximal independent sets (by logical operations), making a 2-edge-connected graph diconnected.
The student is bound to (try to) solve the book exercises listed above for each chapter.

Textbooks

Official textbook:

J.A. Bondy and U.S.R. Murty, "Graph theory with applications",
North Holland, 1976.
Freely downloadable at https://www.zib.de/groetschel/teaching/WS1314/BondyMurtyGTWA.pdf (24 MB).

Support textbooks:

J.A. Bondy and U.S.R. Murty, "Graph theory",
Springer Series: Graduate Texts in Mathematics, Vol. 244 (2008)

R. Diestel, "Graph theory", Springer Series: Graduate Texts in Mathematics, Vol. 173 (2005)
Freely downloadable at http://diestel-graph-theory.com/basic.html (3 MB).

Exams

A mid-term test will be given on December 20, 2024, during class; no booking needed. The mid-term test MUST be passed with a score of at least 14 (over 24). If you don't pass, you must recover it.
Dates for mid-term recovering: 7 January 2025, 22 January 2025, 10 February 2025, 9:00 AM, Teams ("classroom" MathMeth - Graph Th. - Exams); if you want to recover, write to me for booking!

Apply for the final exam at AlmaEsami. Booking is possible only after the end of the course and up to two days before the exam. The final exam is on the whole program above and is as follows: I propose two subjects (each of which is either the title of a long chapter, or the sum of the titles of two short ones); you choose one and write down all what you remember about it, and then we discuss on your essay and in general about the chosen subject. It is an oral examination, so writing is only a help for you to gather ideas.

ATTENTION! If you need to be examined in a precise day of the proposed ones, please register ahead of time: if the maximum number (30) of students for a shift has been reached, the system automatically registers you at the following shift!

Supplementary material:

Example 1 of mid-term test and its solution.
Example 2 of mid-term test and its solution.

Have a look at the demos of graph theory.

Recordings of year 2024

Recording and whiteboard of the lecture of December 13, 2024.
Recording and whiteboard of the lecture of November 29, 2024.
Recording and whiteboard of the lecture of November 22, 2024.
Recording and whiteboard of the lecture of November 15, 2024.
First part, second part and whiteboard of the lecture of November 8, 2024.
Recording and whiteboard of the lecture of October 25, 2024.
Recording and whiteboard of the lecture of October 18, 2024.
Recording and slides of the lecture of October 11, 2024.
First part, second part and whiteboard of the lecture of September 27, 2024.
First part, second part and whiteboard of the lecture of September 20, 2024.

Recordings of year 2023

First part, second part and whiteboard of the lecture of December 19, 2023.
Recording and whiteboard of the lecture of December 12, 2023.
Recording and whiteboard of the lecture of December 5, 2023.
Recording and whiteboard of the lecture of December 1, 2023.
Recording and whiteboard of the lecture of November 28, 2023.
Recording and whiteboard of the lecture of November 24, 2023.
Recording and whiteboard of the lecture of November 21, 2023.
Recording and whiteboard of the lecture of November 17, 2023.
Recording and whiteboard of the lecture of November 10, 2023.
Recording and whiteboard of the lecture of October 27, 2023.
Recording and whiteboard of the lecture of October 24, 2023.
Recording and whiteboard of the lecture of October 13, 2023.

Recordings of year 2022

Recording of the seminars of December 20, 2022.
Recording and whiteboard of the lecture of December 16, 2022.
First part, second part and whiteboard of the lecture of December 13, 2022.
Recording and whiteboard of the lecture of December 2, 2022.
Recording and whiteboard of the lecture of November 29, 2022.
Recording and whiteboard of the lecture of November 25, 2022.
Recording and whiteboard of the lecture of November 22, 2022.
Recording and whiteboard of the lecture of November 18, 2022.
Recording and whiteboard of the lecture of November 15, 2022.
Recording and whiteboard of the lecture of November 11, 2022.
Recording and whiteboard of the lecture of November 8, 2022.

Recordings of year 2021

Recording and whiteboard of the seminar of December 21, 2021.
Recording and whiteboard of the lecture of December 17, 2021.
Recording and whiteboard of the lecture of December 14, 2021.
Recording and whiteboard of the lecture of December 10, 2021.
Recording and whiteboard of the lecture of December 7, 2021.
Recording and whiteboard of the lecture of December 3, 2021.
Recording and whiteboard of the lecture of November 30, 2021.
Recording and whiteboard of the lecture of November 26, 2021.
Recording and whiteboard of the lecture of November 23, 2021.
Recording and whiteboard of the lecture of November 19, 2021.
Recording and whiteboard of the lecture of November 16, 2021.
Recording and whiteboard of the lecture of November 12, 2021.
Recording and whiteboard of the lecture of November 9, 2021.

Recordings of year 2020

First, second part and whiteboard of the lecture of October 27, 2020.
First, second part and whiteboard of the lecture of October 20, 2020.
First, second part and whiteboard of the lecture of October 19, 2020.
First, second part and whiteboard of the lecture of October 13, 2020.
First, second part and whiteboard of the lecture of October 12, 2020.
First, second part and whiteboard of the lecture of October 6, 2020.
First, second part and whiteboard of the lecture of October 5, 2020.
First, second part and whiteboard of the lecture of September 29, 2020.
First, second part and whiteboard of the lecture of September 28, 2020.
First, second part and whiteboard of the lecture of September 22, 2020.
First, second, third part and whiteboard of the lecture of September 21, 2020.

Recordings of year 2019

First, second part and blackboard of the lecture of December 9, 2019.
First, second part and blackboard of the lecture of December 5, 2019.
First, second, third part and blackboard of the lecture of December 2, 2019.
First, second part and blackboard of the lecture of November 28, 2019.
First, second, third part and blackboard of the lecture of November 25, 2019.
First, second part and blackboard of the lecture of November 21, 2019.
First, second, third part and blackboard of the lecture of November 18, 2019.
First, second part and blackboard of the lecture of November 14, 2019.
First, second part and blackboard of the lecture of November 11, 2019.
First, second part and blackboard of the lecture of November 7, 2019.
First, second, third part and blackboard of the lecture of November 4, 2019.