Graph Theory Applications

Instructor  
Rudiger Urbanke  
Office INR 116
Phone +4121 6937692
Email rudiger.urbanke@epfl.ch
Office Hours By appointment

 

Teaching Assistant  
Marco Mondelli  
Office INR038
Phone +4121 693 7514
Email marco.mondelli@epfl.ch
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      
20 Feb Exercise Session 1   Homework 1 Solution 1
25 Feb averaging principle, bipartite graphs, shortest path problem, Dijkstra’s algorithm  
27 Feb Exercise Session 2 Homework 2 Solution 2
04 Mar priority queues, Sperner’s lemma
06 Mar Exercise Session 3 Homework 3 Solution 3
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
13 Mar Exercise Session 4 Graded Homework 4 Solution 4
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
27 Mar Exercise Session 6 Homework 6 Solution 6
01 Apr coverings, Koenig’s theorem, maximum matching and optimal matching
03 Apr Exercise Session 7 Graded Homework 7 Solution 7
08 Apr factors, augmented path search, optimal matching in general graph
10 Apr Exercise Session 8 Homework 8 Solution 8
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
01 May Exercise Session 9 – Project Project Project – Solution
06 May notion of expansion, bound on the minimum distance, the flipping algorithm
08 May Exercise Session 10 Homework 10 Solution 10
13 May Exercise Session 11!!! Homework 11 Solution 11
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
22 May *Exercise Session 12 Homework 12 Solution 12
27 May subgraph inclusion problem and threshold function
29 May Public holiday – no exercise session