Algorithmic Combinatorics (Discrete Mathematics II)
Winter 2014/15.

Instructor.

  • Tibor Szabó
  • Phone: 838-75217
  • Office: 211, Arnimallee 3
  • Email: szabo at math dot fu-berlin dot de
    • Top of page

    Time.

    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 requirements.
    !!! 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.
    • Top of page

    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)
  • Top of page

    Prerequisites.

  • basic graph theory, combinatorics, linear algebra, calculus, probability. Here is the list of material covered in Discrete Math I.
    Top of page

    Requirements.

    Here you can read the requirements and formalities of the course.
    Top of page

    Final.

  • 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)
    Top of page

    Exercises.

    You find the exercises and the dynamic list of material here.

    Literature.

  • L. Lovász, J. Pelikán, K. Vesztergombi, Discrete Mathematics
  • J. Matousek - B. Gaertner, Understanding and Using Linear Programming
  • T. Tao - V. Vu, Additive Combinatorics
  • D. West, Introduction to Graph Theory

    Further reading:
  • V. Chvátal, Linear Programming.
  • A. Schrijver, Theory of Linear and Integer Programming
  • A. Schrijver, Combinatorial Optimization