Course Details
Listed below are the administrative details regarding the course.
Schedule
There will be two lectures every week, as detailed below.
Lectures: Tuesdays and Wednesdays from 12:30 to 14:00 in Arnimallee 6, SR 32.
You are also encouraged to attend one of the following exercise classes.
(We won't stop you from attending both if you really want to.)
Exercises: Tuesdays from 16:15 to 18:00 in Takustrasse 9, SR 49;
Wednesdays from 08:30 to 10:00 in Arnimallee 6, SR 32.
Instructors
Shagnik Das
Arnimallee 3, Room 204
shagnNOBOTSHEREik@mi.fuberHAHAHAHAHAHAHAlin.de
Tibor Szabó
Arnimallee 3, Room 211a
szabo at math dot fuberlin dot de
Office hours are by appointment, so please email as needed.
Exams and Requirements
The final grade for this course will be from a written exam. The first exam will be held on Wednesday, February 22nd, from 9 am to 12 noon, in Hörsaal 1b of Habelschwerdter Allee 45.
The second exam will be held on Wednesday, April 12th, from 8:45 am to 11:45 am, in the Großer Hörsaal of Takustraße 9.
The full set of requirements and formalities for the course can be found here.
Credits
Master's students at the Freie Universität Berlin may take this course either as
"Diskrete Mathematik II" or as an Ergänzungsmodul.
Phase I students from the Berlin Mathematical School may take this course as the basic course "Discrete Optimization" in teaching area 4.
Topics
We shall explore the use of algorithms in combinatorics. The main topics will be:
 Efficient discrete algorithms
 Sorting algorithms
 Shortest routes in graphs
 Maximum and stable matchings
 Brief introduction to complexity classes
 Algorithmic proofs of combinatorial theorems
 Network flows, connectivity and applications
 Linear programming and duality
 Integer programming and approximation
 Randomised algorithms
 Matchings in general graphs
 Algorithmic Local Lemma
 Derandomisation
References
The following texts are recommended for this course.
 D. Hefetz, M. Krivelevich, M. Stojaković and T. Szabó, Positional Games
 L. Lovász, J. Pelikán and K. Vesztergombi, Discrete Mathematics
 J. Matoušek and Bernd Gärtner, Understanding and Using Linear Programming
 D. West, Introduction to Graph Theory
The interested reader might also enjoy the following.
 V. Chvátal, Linear Programming
 A. Schrijver, Theory of Linear and Integer Programming
 A. Schrijver, Combinatorial Optimization
Prerequisites
This course is a second course in the Discrete Mathematics module, and we assume our students are familiar with the basic concepts of graph theory and combinatorics covered in the Discrete Mathematics I course (see here for the relevant material).
We will also make use of undergraduate linear algebra, calculus and probability.
Exercises
Every week there will be an optional online quiz you can take to test your understanding of the material from lecture.
There will also be a homework assignment you should solve in pairs. If you do not yet have a partner, try finding one on our matchmaking page.
Submit your solutions by the end of the Tuesday lecture, either in class itself, or to the tutor box of Shagnik Das.
In the interest of saving paper, should you wish to print the exercises, a more compact version of the exercises will sometimes be made available below.
Quiz  Homework  Due date  Comments 

Week 0  Sheet 0 (print version)  Never  To be discussed on 18/10 
Week 1  Sheet 1 (print version)  25/10/2016  [20/10: corrected 1, modified 3(b); 23/10: minor textual changes] 
Week 2  Sheet 2  1/11/2016  [27/10: corrected kSAT example; 28/10: corrected ex. 4] 
Sheet 3  8/11/2016  [4/11: sum limits added to ex. 1]  
Sheet 4 (print version)  15/11/2016  [14/11: missing +1 returned to exercise 6(b)]  
Sheet 5  22/11/2016  
Sheet 6  29/11/2016  
Sheet 7  6/12/2016  [3/12: corrected Ex 1]  
Sheet 8 (print version)  13/12/2016  
Midterm exam  3/1/2017  Optional  
Sheet 9 (print version)  10/1/2017  
Sheet 10  17/1/2017  
Sheet 11  24/1/2017  [21/1: corrected Ex 5]  
Sheet 12 (print version)  31/1/2017  [30/1: corrected Ex 6]  
Week 14  Sheet 13  7/2/2017  [6/2: corrected Ex 5, 6] 
Sheet 14  14/2/2017  
Sheet 15  Never  Solutions 
Course Progress
Topics
As we make our way through the semester, we will provide below a brief review of the topics covered each week.
Lecture  Topics  References 

1  Sorting algorithms: (Binary) insertion sort, Mergesort; Analysis: running time, matching lower bound  
2  Spanning trees: Depthfirst and breadthfirst search, Kruskal's algorithm for minimumweight spanning trees  LPV 9.1 West 2.3 
3  Shortest paths: Dijkstra's algorithm, TSP; Complexity and P 
West 2.3 West App B 
4  Complexity classes: NP, coNP, NPcompleteness; 2approximation to TSP 
LPV 15.1 LPV 9.2 
5  Perfect matchings: Hall's theorem, Tutte's theorem; kfactors: Petersen's 2factor theorem 
West 3.1, 3.3 LPV 10.3 
6  Maximum matchings: characterisation, covers and duality, augmenting path algorithm 
West 3.12 LPV 10.4 
7  Weighted matchings and the Hungarian algorithm  West 3.2 
8  Stable matchings, GaleShapley proposal algorithm Chromatic number: review, basic bounds 
West 3.2 West 5.1 
9  Listcolouring: definition, comparison to chromatic number, greedy upper bound  West 8.4 
10  Listcolouring: Thomassen's theorem for planar graphs Edgecolouring: definition, examples, bounds, line graphs 
West 8.4 West 7.1 
11  Vizing's Theorem: Schrijver's proof  West 7.1 
12  Edgechoosability: conjectures (listcolouring, Dinitz), Galvin's theorem for K_{n,n}  West 8.4 
13  Vertex and edgeconnectivity: definitions, examples, Whitney's Theorem  West 4.1 
14  Connectivity: Menger's theorem (local/global, vertex/edge) Network flows: formulation of problem 
West 4.2 West 4.3 
15  Network flows: weak duality, FordFulkerson Theorem, FordFulkerson Algorithm and the Integrality Theorem 
West 4.3 
16  Flow applications: local, vertex Menger's Theorem, Baranyai's Theorem on perfect matching decompositions 
West 4.3 
17  Linear programming: network flows, history, 2D examples, framework, standard form, dietary application 
MG 1.14 MG 2.12 
18  Linear programming applications: absolute values, strict inequalities, hidden variables 
MG 2.37 
19  Integer programming: complexity, LP relaxations, maximum weight matchings, independence number 
MG 3.1 MG 3.2, 3.4 
20  Solving LPs: geometric intuition, basic feasible solutions, every bounded feasible program has an optimal bfs 
MG 4.12 
21  Simplex algorithm: tableaux, pivoting, worked example  MG 5.15 
22  Simplex algorithm: outline of steps, pivot rules, proof that Bland's rule avoids cycling 
MG 5.68 
23  LP Complexity: other pivot rules, worstcase examples, Hirsch conjecture, nonsimplex methods Duality: formulation of dual, weak duality, Duality Theorem 
MG 5.7, 5.9 MG 6.1, 6.3 
24  Zerosum twoplayer games: examples, mixed strategies, Nash equilibria, worstcase optimal strategies 
MG 8.1 
25  Zerosum twoplayer games: the Minimax Theorem; Total unimodularity: definition, integer solutions to LPs 
MG 8.1 MG 8.2 
26  Transversals of dintervals: Helly's Theorem, definitions, proof of 2d^{2} bound 
MG 8.6 
27  Randomised algorithms: Las Vegas vs Monte Carlo, onesided errors; matrix multiplication verification  
28  Polynomial identity testing: oracle access, SchwartzZippel lemma, perfect matchings in bipartite graphs  
29  Twocolourability: motivation, hypergraph formulation, randomised algorithm, extremal problem with lower bound 

30  Positional games: derandomised twocolouring, extremal function for games, ErdősSelfridge criterion 

31  Lovász Local Lemma: motivation, statement, application: twocolouring sparse kgraphs 

32  Algorithmic Local Lemma: recolouring algorithm, auxiliary tree, entropy compression, efficient recording 
Notes
Below are some relevant notes, mostly from previous years when this course has been taught.
 First week
 Kruskal's algorithm
 Solution to Sheet 1, Exercise 2
 Matchings and TSP
 Bipartite matching algorithms
 Graph colouring and stable matchings
 Connectivity, flows, and Baranyai's Theorem (updated 6/1)
 Solution to Sheet 8, Exercise 6
 Skeletal notes for: Lecture 28, Lecture 29, Lecture 30
 The ErdősSelfridge criterion
 The Lovász Local Lemma
 The Algorithmic Local Lemma