| Teaching Assistant |
|
| Marco Mondelli |
|
| Office |
INR038 |
| Phone |
+4121 693 7514 |
| Email |
[email protected] |
| Office Hours |
Office Hours 24/24 |
| Lectures: |
|
Tuesday |
11:15 – 13:00 |
Room: INM203 |
|
|
Thursday |
16:15 – 18:00 |
Room: INM 201 |
Language: English Coefficient/Crédits: 4 ECTS
Link to the official course description. CourseInformation.pdf
Course Description
Besides classical notions of graph theory (shortest path, cuts, flows, colouring, independent set, matchings, planarity), we will cover a few more modern concepts. In particular, we will briefly discuss random graphs as well as some basic notions of the spectral theory of graphs.
Grade
The grade will have four components – Homeworks (10%), Project (20%), Midterm Exam (30%) and Final Exam (40%)
Tentatively, there will be two homework sets on both sides of the Midterm exam. The precise topic of the project will be discussed in the class during the semester.
Textbook
We will be using the book Graph Theory with Applications by J.A. Bondy and U.S.R. Murty. You may find the electronic version of the old version of this book here. In addition we recommend that you buy the new version. Other standard references are the book by West as well as the book by Diestel. We will also make use of some material from the following lecture notes lecture notes.
Special Announcements
Information about the final exam: it takes place on Friday, June 27, from 8:15 until 11:00, in room INM 10. Please, be there at 8:00 so that we can assign the seats and start at 8:15 sharp.
Allowed material: four handwritten single-sided A4 pages of notes.
| Date |
Topic |
Assignment |
Due Date/Solutions Posted |
Remarks |
| 18 Feb |
motivation; basic concepts: adjacency, degrees, graphic degree sequences, walk, trail, paths, some special graphs, raids, diameter, averaging principle, pigeonhole principle |
|
|
|
| 25 Feb |
averaging principle, bipartite graphs, shortest path problem, Dijkstra’s algorithm |
|
| 04 Mar |
priority queues, Sperner’s lemma |
| 11 Mar |
consequence of Sperner’s lemma; Brouwer’s fixed point theorem, topologically equivalent domains, proof of Brouwer’s fixed point theorem in two dimensions |
| 18 Mar |
spanning trees, minimum weight spanning trees, Kruskal’s algorithm, matroids, examples of matroids, general greedy algorithm for a weighted matroid, optimality of this greedy algorithm |
| 20 Mar |
Exercise Session 5 |
Homework 5 |
Solution 5 |
| 25 Mar |
matchings, matchings in bipartite graphs, Hall’s condtion |
| 01 Apr |
coverings, Koenig’s theorem, maximum matching and optimal matching |
| 08 Apr |
factors, augmented path search, optimal matching in general graph |
| 15 Apr |
flows, maximum flow, cut, minimum cut, max flow min cut theorem |
| 22 Apr |
Easter break – no course |
| 24 Apr |
Easter break – no course |
| 29 Apr |
Ford-Fulkerson Algorithm, Menger’s theorem, error correcting codes based on sparse bipartite graphs |
| 06 May |
notion of expansion, bound on the minimum distance, the flipping algorithm |
| 15 May |
Course!!!: analysis of flipping algorithm, a bound on the expansion via spectral methods |
| 20 May |
probabilistic method, expansion of random bipartite graphs, Markov inequality, Chebyshev inequality |
| 27 May |
subgraph inclusion problem and threshold function |
| 29 May |
Public holiday – no exercise session |
