===== Graph Theory Applications ===== \\ |**Instructor**|\\ |**Rudiger Urbanke**| |Office|[[http://plan.epfl.ch/?room=INR116|INR 116]]| |Phone|**+4121 6937692**| |Email|**rudiger.urbanke@epfl.ch**| |Office Hours|**By appointment**| \\ |**Teaching Assistant**|\\ |**Marco Mondelli** | |Office|[[http://plan.epfl.ch/?room=INR038|INR038]]| |Phone|**+4121 693 7514**| |Email|**marco.mondelli@epfl.ch**| |Office Hours|**Office Hours 24/24**| || \\ |**Lectures:** | |Tuesday|11:15 - 13:00|Room: INM203| | | |Thursday |16:15 - 18:00|Room: INM 201| \\ **Language:** English **Coefficient/Crédits:** 4 ECTS \\ \\ [[http://isa.epfl.ch/imoniteur_ISAP/!itffichecours.htm?ww_i_matiere=71646415&ww_x_anneeAcad=2012-2013&ww_i_section=946228&ww_i_niveau=6683117&ww_c_langue=en|Link]] to the official course description. {{:en:courses:2012-2013:info.pdf|CourseInformation.pdf}} \\ ---- ==== Course Description ==== Besides classical notions of graph theory (shortest path, cuts, flows, colouring, independent set, matchings, planarity), we will cover a few more modern concepts. In particular, we will briefly discuss random graphs as well as some basic notions of the spectral theory of graphs. \\ ---- ==== Grade ==== The grade will have four components - Homeworks (10%), Project (20%), Midterm Exam (30%) and Final Exam (40%) Tentatively, there will be two homework sets on both sides of the Midterm exam. The precise topic of the project will be discussed in the class during the semester. \\ ---- ==== Textbook ==== We will be using the book Graph Theory with Applications by J.A. Bondy and U.S.R. Murty. You may find the electronic version of the old version of this book [[http://book.huihoo.com/pdf/graph-theory-With-applications/|here]]. In addition we recommend that you buy the new version. Other standard references are the book by West as well as the book by Diestel. We will also make use of some material from the following lecture notes [[http://www.personal.psu.edu/cxg286/Math485.pdf|lecture notes]]. ==== Special Announcements ==== Information about the **final exam**: it takes place on **Friday, June 27**, **from 8:15 until 11:00**, in **room INM 10**. Please, **be there at 8:00** so that we can assign the seats and start at 8:15 sharp. Allowed material: four handwritten single-sided A4 pages of notes. \\ \\ ^ Date ^ Topic ^ Assignment ^ Due Date/Solutions Posted ^ Remarks ^ |18 Feb| motivation; basic concepts: adjacency, degrees, graphic degree sequences, walk, trail, paths, some special graphs, raids, diameter, averaging principle, pigeonhole principle | | | | |20 Feb| Exercise Session 1 | |{{:en:courses:lthc:gta14_ex1_rev.pdf| Homework 1}} |{{:en:courses:lthc:gta14_ex1_sol.pdf| Solution 1}} | |25 Feb|averaging principle, bipartite graphs, shortest path problem, Dijkstra's algorithm | | |27 Feb| Exercise Session 2 ||{{:en:courses:lthc:gta14_ex2.pdf| Homework 2}}| {{:en:courses:lthc:gta14_ex2_sol.pdf| Solution 2}} | |04 Mar| priority queues, Sperner's lemma| |06 Mar|Exercise Session 3 |{{:en:courses:lthc:gta14_ex3.pdf| Homework 3}}|{{:en:courses:lthc:gta14_ex3_sol.pdf| Solution 3}}|| |11 Mar|consequence of Sperner's lemma; Brouwer's fixed point theorem, topologically equivalent domains, proof of Brouwer's fixed point theorem in two dimensions| |13 Mar|Exercise Session 4 |{{:en:courses:lthc:gta14_ex4.pdf| Graded Homework 4}}|{{:en:courses:lthc:gta14_ex4_sol.pdf| Solution 4}}|| |18 Mar| spanning trees, minimum weight spanning trees, Kruskal's algorithm, matroids, examples of matroids, general greedy algorithm for a weighted matroid, optimality of this greedy algorithm|||| |20 Mar|Exercise Session 5 |{{:en:courses:lthc:gta14_ex5.pdf| Homework 5}} |{{:en:courses:lthc:gta14_ex5_sol.pdf| Solution 5}}|| |25 Mar|matchings, matchings in bipartite graphs, Hall's condtion|||| |27 Mar|Exercise Session 6 |{{:en:courses:lthc:gta14_ex6.pdf| Homework 6}}|{{:en:courses:lthc:gta14_ex6_sol.pdf| Solution 6}}|| |01 Apr|coverings, Koenig's theorem, maximum matching and optimal matching|||| |03 Apr| Exercise Session 7 |{{:en:courses:lthc:gta14_ex7_v3.pdf| Graded Homework 7}}|{{:en:courses:lthc:gta14_ex7_sol.pdf| Solution 7}}|| |08 Apr|factors, augmented path search, optimal matching in general graph|||| |10 Apr| Exercise Session 8 |{{:en:courses:lthc:gta14_ex8.pdf| Homework 8}}|{{:en:courses:lthc:gta14_ex8_sol.pdf| Solution 8}}|| |15 Apr|flows, maximum flow, cut, minimum cut, max flow min cut theorem||| |17 Apr| **MIDTERM** |{{:en:courses:lthc:midtermgta14.pdf| Midterm}}|{{:en:courses:lthc:midtermgta14_solutions.pdf| Midterm - Solution}} | \\ |22 Apr| Easter break - no course| |24 Apr| Easter break - no course| \\ |29 Apr|Ford-Fulkerson Algorithm, Menger's theorem, error correcting codes based on sparse bipartite graphs|||| |01 May| Exercise Session 9 - Project |{{:en:courses:lthc:gta14_project9_rev.pdf| Project}}|{{:en:courses:lthc:gta14_project9_sol.pdf| Project - Solution}} || |06 May|notion of expansion, bound on the minimum distance, the flipping algorithm|||| |08 May| Exercise Session 10 |{{:en:courses:lthc:gta14_ex10.pdf| Homework 10}}|{{:en:courses:lthc:gta14_ex10_sol.pdf| Solution 10}}|| |13 May|**Exercise Session 11!!!** |{{:en:courses:lthc:gta14_ex11.pdf| Homework 11}}|{{:en:courses:lthc:gta14_ex11_sol.pdf| Solution 11}}|| |15 May| **Course!!!:** analysis of flipping algorithm, a bound on the expansion via spectral methods|||| |20 May|probabilistic method, expansion of random bipartite graphs, Markov inequality, Chebyshev inequality|||| |22 May|*Exercise Session 12 |{{:en:courses:lthc:gta14_ex12.pdf| Homework 12}}|{{:en:courses:lthc:gta14_ex12_sol.pdf| Solution 12}}|| |27 May|subgraph inclusion problem and threshold function|||| |29 May| Public holiday - no exercise session |||| |{{:en:courses:lthc:finalgta14_text.pdf| Final Exam}}|{{:en:courses:lthc:finalgta14_sol2.pdf| Final Exam - Solution}}||||