Algorithmic Combinatorics (Discrete Mathematics II)
Office: 211, Arnimallee 3
Email: szabo at math dot fu-berlin dot de
The course starts out with a unique opportunity, an intensive block course about Additive
Combinatorics which is a part of this
Hence during the week of October 6-10, there will be lectures from
9:00-12:00 and exercise sessions 16:30-17:30 in HS 001 on Monday, Tuesday, Thursday, and
Friday. After this week the normal weekly hours of the course resume on November 3rd.
There will be a question and answer information period on October 6th
8:15-8:45 in HS 001 of Arnimallee 3,
about the material, as
well as the rules and
!!! If you missed the first week here
here, here, and
here (revised Oct 13) are the handouts for the block course part of the
course. Here are the lecture notes. The
exercises are due October 29th in the box of Shagnik Das.
Lectures: Tuesdays, 8:30 - 10:00 Uhr - Arnimallee 6 SR 032 and Wednesdays, 8:30 - 10:00, Arnimalle 6 SR 032.
Exercises: Mondays, 10:15-12:00 SR 210, Arnimallee 3 OR Tuesdays, 12:30 - 14:00 - Arnimallee 6 SR 032.
Topics of the course.
Additive Combinatorics (basic cardinality inequalities, covering lemmas, Ruzsa's
power trick, Freiman isomorphisms, additive energy and Balog-Szemeredi-Gowers
Theorem, sum-product estimates, Szemer\'edi-Trotter Theorem
and/or Bourgain-Katz-Tao Theorem)
Algorithms (sorting, TSP, maximum matchings, certificates
(Tutte's Theorem), network flows and its
applications (Menger's Theorem, Baranyai's Theorem), Stable Matching
and its application (list coloring))
Linear Programming (Simplex Algorithm), Duality and its applications in Combinatorics and Algorithms
Randomized algorithms (randomized matchiung algorithms,
hypergraph-coloring, derandomization, Erdos-Selfridge Criterion, algorithmization of Local Lemma)
basic graph theory, combinatorics, linear algebra, calculus, probability. Here
is the list of material covered in Discrete Math I.
Here you can read the requirements and
formalities of the course.
Final exam: February 18th (Wednesday), 9:00 - 12:00, Room: HS 001,
Arnimallee 3. (Results)
Make-up final exam: March 24th (Tuesday), 9:00 - 12:00 Room: HS 001,
Arnimallee 3. (Results)
You find the exercises and the dynamic list of material
L. Lovász, J. Pelikán, K. Vesztergombi, Discrete
J. Matousek - B. Gaertner, Understanding and Using Linear Programming
T. Tao - V. Vu, Additive Combinatorics
D. West, Introduction to Graph Theory
V. Chvátal, Linear Programming.
A. Schrijver, Theory of Linear and Integer Programming
A. Schrijver, Combinatorial Optimization