## Course Summary

#### (The course will consist of lectures and several exercise sessions. See detailed schedule below)

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

TA:             Ruben van der Zwaan     Email:  g.r.j.v.d.zwaan@tue.nl

Prerequisites: This is a masters level class and a basic background in algorithms and discrete mathematics is expected. Familiarity with some basic ideas from optimization will be helpful, but is not necessary. 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:
• Power of min-max relations: NP and co-NP problems.
• LP Duality: Understanding Bipartite Matching, Flow, Shortest Paths via LP duality.
• Exact Algorithms: Dynamic programming, 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) Homework 1  (due Feb 28,2014) Homework 2  (due Apr 22, 2014) Homework 3  (due June 17, 2014)

Lectures:

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

 Lecture Date/Location Topic Reading Material L1 Feb 4, Tu, Introduction, basic graph theory, NP, co-NP, examples Exercise 1 (pdf);  5-coloring planar graphs (pdf; from page 10); wikipedia is useful source for basic graph theory concepts L2 Feb  6, Th Bipartite matching, max-flow and applications Hoffman's circulation theorem (pdf, sections 1.1 and 1.2); notes on max-flow; notes on bipartite matching; nice slides on applications of max-flow, Konig-Egervary,... E1 Feb 11, Tu Exercise E2 Feb 13, Th Exercise L3 Feb 18, Tu, Planarity testing and planar separator theorem Wikipedia on planar graph basics,  four color theorem , planar separator theorem. Sariel Har-Peled's proof of planar separator thm. Notes for the lecture (pdf) L4 Feb 25, Th Planar Duality and application to exact algorithm for planar  max-cut Feige's notes on planar max-cut (first page).  Excellent optional reading:  Has proof of Koebe's theorem and tons of other great stuff! Notes  (pdf ) E3 Feb 27, Th Exercise Exercise 2 (pdf) L5 Mar 11, Tu Probabilistic arguments: crossing number inequality, graphs with large girth and chromatic number, tournaments with no winners. Terry Tao's blog on crossing number inequaity. Notes on graps with large girth,chromatic number. Scribe notes  (pdf) L6 Mar 13, Th Expanders: Application to super-concentrators of O(n) size. Clique size in G(n,1/2) via second moment method. See section 9.2 here for cliques in random graphs. These notes also have other nice applications. Scribe notes ( pdf)  (ignore the part on super-concentrators) E4 Mar 18, Tu Exercise L7 Mar 20, Th Algorithmic uses of Probability: Karger's min-cut,  Schwartz Zippel Lemma and  matching. Schwartz Zippel on wikipedia (proof and applications) Notes on Karger's mincut algorithm. Scribe notes ( pdf )  (ignore the part on graph products) April 1, Tu midterm exam Exam (pdf); Solutions (pdf) L8 Apr  22, Tu Problem solving techniques (pdf) Apr  24, Th Mid-term resit L9 Apr 29, Tu Extremal graph theory. Turan's theorem, Ramsey upper bound. Proofs of Mantel's and Turan's theorems (pdf); Ramsey upper bound; nice course on extremal graph theory L10 May 1, Th Coloring dense 3-colorable graphs, randomized 2-SAT algorithm. Exercise 3 (pdf) Old scribe notes (pdf) L11 May 13, Tu Graph products; Chernoff bound; applications Old scribe notes (pdf) L12 May 15, Th Edge disjoint paths; Power of two choices; Graph Sparsification Old scribe notes (pdf); Notes of Nick Harvey on sparsification L13 May  20, Tu Exact algorithms; Hamiltonian paths; coloring; inclusion-exclusion method; dynamic programing; braching; algorithms on trees Nice slides on inclusion-exclusion by Lukasz Kowalik. Many things we dicussed can be found in this survey by Gerhard Woeginger L14 Jun 5, Th fixed parameter tractability, no-existence of FPT for independent set; Color coding: simple path Color Coding (see section 3 here) Nice survey on proving lower bounds  assuming ETH. Scribe (pdf) L15 Jun 10, Tu Problem Solving Session Jul 2, Th, 9:00-12:00 Final Exam