## Course Summary

#### Exam: July 1;  Time 9:00-12:00 Location: TBD     Interim: August 12, 9:00-12:00

Instructors:  Nikhil Bansal -   MF 4.95
Ph: 040 247 2299. Email:  n dot bansal at tue dot nl

Jorn van der Pol    Email:  j.g.v.d.pol at tue.nl

Prerequisites: This is a masters level class and a basic background in algorithms and discrete mathematics is expected.  Above all, the most important prerequisite is mathematical maturity. If you are not familiar with certain topics, you can contact me after the class to extra background reading material.

Goals:  At the end of the course, the student should be well-versed in basic concepts of graph theory such as coloring, planarity, independent sets, flows etc. They should understand basic proof techniques in graph theory such as the probabilistic method. They should also be able to use various algorithmic techniques.

Grading Policy:  The final grade will be based on homeworks (20%),  midterm exam (30%) and final exam (50%).

Homeworks:  There will be four homeworks, which can be done in groups of up to 2 people. All homeworks must be written in Tex, and the proofs must be clearly written.

Exercise Sessions: The exercises consists of basic problems which you should master. The exercises sessions are for solving exercises, discussing homework problems (after their due date).

Study material:

• #### There is no particular textbook for the course. The relevant reading material will be provided during the course.

Tentative Topic List:

• Concepts from Graph Theory
• Matchings: Bipartite and general graphs, related min-max theorems. Applications. Chinese Postman Problem, TSP.
• Planarity:  Duality, finding max cut in planar graphs, planarity testing algorithm, planar separator theorem and applications.
• Flows: Max-flow Min-cut, min-cost circulations and their various applications, connectivity results.
• Operations on Graphs:  Graph Products, Line Graphs. Application to independent set hardness.
• Probabilistic Methods: Various graph constructions, Expanders and their applications, Karger's min-cut, polynomial identity testing.
• Extremal graph theory: Basic results
• Algebraic Methods: Graph expansion, Determinants, Permanents
• Algorithmic Concepts:
• Min-max relaxation and polynomial time algorithms
• Dynamic Programming
• Exact Algorithms: Color coding, algebraic techniques
• Randomized Graph Algorithms: Graph Sparsification.
• Approximation: SDPs for maxcut and 3-coloring

Note: The above list is tentative.

###### Homeworks: (see guidelines above)

Lectures:

(Tentative Plan,  will be updated as the course proceeds)

 Lecture Date/Location Topic Reading Material L1 Feb 4, We Introduction, basic graph theory concepts  (N) Slides for lectures 1-2; wikipedia is useful source for basic graph theory concepts L2 Feb  5, Th Halls Thm, Bipartite matching, non-bipartite matching applications (N) Nice slides on Hall's theorem; bipartite matching and applications 5-coloring planar graphs (pdf; from page 10); L3 Feb 11, We Max-flow; circulation and applications; Slides on maxflow bascis and  maxflow-mincut theorem L4 Feb 12, Th Advanced Applications of max-flow; (N) Applications of maxflow (slides);  Homework 1 (pdf) Feb  25, We no class Feb 26, Th no class L5 Mar 4, We Planarity testing and planar separator theorem  (N) Wikipedia on planar graph basics,  four color theorem , planar separator theorem. Section 1.5.1 here  has the planarity testing algorithm we discussed. Sariel Har-Peled's proof of planar separator thm. Old lecture notes (pdf) L6 Mar 5, Th Planar Duality and application to exact algorithm for planar  max-cut (N) Feige's notes on planar max-cut (first page).  Excellent optional reading:  Has proof of Koebe's theorem and tons of other great stuff! Old lecture notes  (pdf ) Slides for lectures 5 and 6  (pdf) L7 Mar 11, We Probabilistic arguments: First moment method; crossing number inequality, Ramsey results, tournaments with no winners (J) Handout (Probability Basics) Lecture notes; Terry Tao has an excellent blog post on the crossing number inequality. Standard book on the probabilistic method: Alon & Spencer L8 Mar 12, Th Probabilistic arguments: Erdős-Rényi random graph, Clique size in G(n,1/2) via second moment method (J) Lecture notes L9 Mar 18, We Probabilistic arguments: alterations, stable sets, Ramsey results (J) Lecture notes Some background information on "Property B" (=hypergraph 2-coloring) L10 Mar 19, Th Probabilistic arguments: Chernoff bound and applications (J) Lecture notes E1 Mar 25, We Problem session Homework 2 (pdf) L11 Mar 26, Th Probabilistic arguments: random walks, application to 2-SAT, 3-COL (J) Lecture notes E2 Apr 01, We Problem session (N) Apr 02, Th Mid-term (Solutions) (pdf) L12 Apr  22, We Probabilistic arguments: Karger's min-cut algorithm, Schwartz-Zippel (J) Lecture notes Books on randomised algorithms: Motwani & Raghavan, Mitzenmacher & Upfal E3 Apr 23, Th Mid-term (resit) L13 Apr 29, We Benczúr-Karger Graph Sparsification (J) Lecture notes A paper by Benczúr & Karger about graph sparsification L14 Apr 30, Th Extremal graph theory. Turan's theorem, Ramsey upper bound. (J) Proof of Mantel's and Turán's theorems (pdf); Upper bound on Ramsey numbers Extremal Combinatorics (Statys Jukna): good book on extremal combinatorics (free draft available on the author's website) L15 May 6, We Exact Algorithms (N); Dynamic Programming Slides for lectures 15 and 16  (pdf)  ;  Notes on branching (sections 1 and 2)   (pdf)  ; Slides on inclusion-exclusion + applications  (pdf) ; Survey on exact algorithms (pdf) ;  Paper of Ryan Williams on  max-3-sat using triangle finding (pdf) L16 May 7, Th Inclusion-Exclusion; FPT (N) Mid-term resit solutions (pdf) ; Homework 3 (pdf) L17 May 13, We Color Coding, ETH; No FPT for independent sets Slides on color coding for k-path (pdf, see slide 5 and later) Survey on lower bounds using ETH (pdf). We did Thm 5.1 E4 May 20, We Problem session (J) May 21, Th no class May 27, We no class May 28, Th no class L18 Jun 3, We Treediwdth  + Feedback arc set in tournaments The Feedback arc set in tournaments paper.  Lecture  on treewidth (see definition and section 11.2). Homeword  4 (pdf) E5 Jun 18, Th Problem session (J) Jul 1 Final Exam (location PAV SH1)  9:00-12:00 Older final exams for practice 2012,  2013, 2014  (warning: some of the course content was different than what we covered this year)