Algorithmic Combinatorics

Winter 2016-17

FU Berlin, Mathematics and Informatics

Many thanks to Toptal for this animation.

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.fu-berHAHAHAHAHAHAHAlin.de

Tibor Szabó
Arnimallee 3, Room 211a
szabo at math dot fu-berlin dot de

Office hours are by appointment, so please e-mail 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.

Return to top

Topics

We shall explore the use of algorithms in combinatorics. The main topics will be:

References

The following texts are recommended for this course.

The interested reader might also enjoy the following.

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.

Return to top

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 k-SAT 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
Return to top

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: Depth-first and breadth-first search, Kruskal's algorithm for minimum-weight 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, co-NP, NP-completeness;
2-approximation to TSP		 LPV 15.1
LPV 9.2
5 Perfect matchings: Hall's theorem, Tutte's theorem;
k-factors: Petersen's 2-factor theorem		 West 3.1, 3.3
LPV 10.3
6 Maximum matchings: characterisation, covers and duality,
augmenting path algorithm		 West 3.1-2
LPV 10.4
7 Weighted matchings and the Hungarian algorithm West 3.2
8 Stable matchings, Gale-Shapley proposal algorithm
Chromatic number: review, basic bounds		 West 3.2
West 5.1
9 List-colouring: definition, comparison to chromatic number, greedy upper bound West 8.4
10 List-colouring: Thomassen's theorem for planar graphs
Edge-colouring: definition, examples, bounds, line graphs		 West 8.4
West 7.1
11 Vizing's Theorem: Schrijver's proof West 7.1
12 Edge-choosability: conjectures (list-colouring, Dinitz), Galvin's theorem for K_{n,n} West 8.4
13 Vertex- and edge-connectivity: 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, Ford-Fulkerson Theorem,
Ford-Fulkerson 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.1-4
MG 2.1-2
18 Linear programming applications: absolute values,
strict inequalities, hidden variables		 MG 2.3-7
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.1-2
21 Simplex algorithm: tableaux, pivoting, worked example MG 5.1-5
22 Simplex algorithm: outline of steps, pivot rules,
proof that Bland's rule avoids cycling		 MG 5.6-8
23 LP Complexity: other pivot rules, worst-case examples, Hirsch conjecture, non-simplex methods
Duality: formulation of dual, weak duality, Duality Theorem		 MG 5.7, 5.9
 
MG 6.1, 6.3
24 Zero-sum two-player games: examples, mixed strategies,
Nash equilibria, worst-case optimal strategies		 MG 8.1
25 Zero-sum two-player games: the Minimax Theorem;
Total unimodularity: definition, integer solutions to LPs		 MG 8.1
MG 8.2
26 Transversals of d-intervals: Helly's Theorem, definitions,
proof of 2d2 bound		 MG 8.6
27 Randomised algorithms: Las Vegas vs Monte Carlo, one-sided errors; matrix multiplication verification
28 Polynomial identity testing: oracle access, Schwartz-Zippel lemma, perfect matchings in bipartite graphs
29 Two-colourability: motivation, hypergraph formulation,
randomised algorithm, extremal problem with lower bound
30 Positional games: derandomised two-colouring,
extremal function for games, Erdős-Selfridge criterion
31 Lovász Local Lemma: motivation, statement,
application: two-colouring sparse k-graphs
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.

Return to top