max planck institut
informatik

# Graph Theory (Summer 2011)

Lecturers:   Prof. Dr. Benjamin Doerr, Dr. Danny Hermelin, and Dr. Reto Spöhel

Time: Tuesday, 10-12 and Thursday, 10-12

Room: Building E1.4 (MPI main building), room 0.24 (main lecture hall)

Content: This is a first course in graph theory. Topics include basic notions like graphs, subgraphs, trees, cycles, connectivity, colorability, planar graphs etc. We continue with some particularly interesting areas like Ramsey theory, random graphs or expander graphs.

Audience: The course counts both as mathematics and computer science lecture (4 hours of lectures per week, 9 credit points). It requires no particular prerequisites except the basics in mathematics. We offer exercise groups (2 hours per week), which will be set up in the first lecture. The lecture will be given in English.

Exercise groups:

Monday, 14:30-16:00 and 16:00-17:30 in rooms 0.21 and 0.23 (next to the lecture hall). Start: April 18.
You can register, and login to your personal account here.

Lecture details:
Date Lecturer Topic Reference Exercises
April 12 BD Administrative stuff, Graphs, Euler tours 1.0-1.2; 1.8 1st Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
April 14 BD Degree, Double Counting, Minimal Counter Example 1.2
April 19 BD Paths and Cycles, Geometric Series, Connectivity, Proof by Induction 1.3 except 1.3.4 and proof of 1.3.5; 1.4 up to 1.4.1 2nd Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
April 21 BD Connectivity, Trees 1.4.2; 1.5 up to 1.5.2
April 26 RS Test 2; Trees, Multipartite and Bipartite Graphs 1.5.4; 1.6 except proof of 1.6.1 3rd Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
April 28 RS Matchings, Augmenting Paths, König's Theorem proof of 1.6.1; 2 up to 2.1.1
May 3 RS Hall's Theorem and Corollaries rest of 2.1 except 2.1.4 4th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
May 5 RS Tutte's Perfect Matching Theorem 2.2.1
May 10 DH 2-Connected Graphs and Subgraphs 3.1 5th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
May 12 DH Menger's Theorem 3.3.1, 3.3.5, and 3.3.6
May 17 DH Introduction to Planar Graphs, Euler's Formula. Roughly 4.1 and 4.2. Proof of 4.2.9 and 4.2.10. 6th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
May 19 DH Minors and Topological Minors 1.7
May 24 DH Kuratowski's Theorem for 3-Connected Graphs 4.4.2 and 4.4.3 7th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
May 26 DH Kuratowski's Theorem for General Graphs 4.4.4, 4.4.5, and 4.4.6
May 31 RS Chromatic Number, Coloring Number, Greedy Coloring 5.0; 5.2 up to 5.2.2 8th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
June 2 [Ascension Day]
June 7 RS Brooks' Theorem 5.2.4 9th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
June 9 RS Chromatic Index, Line Graph, Vizing's Theorem 5.3
June 14 DH Test 9; Perfect Graphs: Interval Graphs, Comparability Graphs, and Dilworth's Theorem. 5.5 up to 5.5.1. [Wikipedia Interval and Comparability Graphs], [Fulkerson's proof of Dilworth's Theorem] 10th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
June 16 DH The Weak Perfect Graph Theorem 5.5.3, 5.5.4, and 5.5.5
June 21 TK Infinite Graphs, König's Infinity Lemma 8.1 11th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
June 23 [Corpus Christi]
June 28 RS Random Graphs, the Probabilistic Method, Ramsey Numbers 11 up to 11.1.3; 9.1.1 12th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
June 30 BD First Moment Method 11.1.4-11.2.1
July 5 RS Second Moment Method 11.2.2; 11.4 13th Exercise Sheet: [pdf]; Sample Solution: [pdf]; Test: [pdf]
July 7 RS Small Subgraphs Theorem; Online Vertex-Coloring Games in Random Graphs 11.4; Slides 1, Slides 2
July 12 DH WQO and Kruskal's Tree Theorem 12.1 and 12.2
July 14 DH Tree Decompositions and Treewidth 12.3.1-12.3.6, 12.3.11,12.3.12
July 19 BD Hamilton Cycles 10.1.1, Thm. of Ore, 10.1.2., 10.2.1
July 21 BD Rumor Spreading in Graphs B. Doerr, M. Fouz, T. Friedrich.
Social networks spread rumors in sublogarithmic time. [pdf]
In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011), pages 21-30, 2011.

Exams/Credit: There will be a written final exam on July 26, 2011 (see below for details). Eventually, there will also be a repetition exam. The repetition exam will be oral or written, depending on the number of candidates. Anyone who got admitted to the final exam will be allowed to participate in the repetition exam, irrespective of whether they passed or failed the final. If you take both exams, your final grade will be the better one of the two grades you achieve. You get a "Schein" if you reach a grade of "four" or better.

To be admitted to either exam, you have to get at least 50% of all points achievable during the semester. In addition, you not only need to have 50% of all available points at the end of the semester, but also after the third and sixth exercise session. You earn points in two different ways: 1) We will hand out exercise sheets in the lecture. We expect you to hand in written solutions to these homework problems. Your solutions will be graded, and you get points accordingly. 2) In each exercise session, there will be a short (ca. 15 min) quiz to test your understanding of the material discussed in the previous lectures. Again your answers will be graded, and you get points accordingly.

This system is intended to encourage serious efforts from the very beginning, and is also meant to prevent students who miss too much during the first part of the semester from wasting unnecessary efforts later on.

Final Exam: The final exam takes place on Tuesday, July 26, 2011 (this is in the first week of the semester break). It will be in room "AudiMO" in building E2 2. You have to be there at 9:00, and you will have exactly three (3) hours to solve the problems. Since it usually takes some time to set up an exam, don't expect to finish at 12:00 sharp, but allow some extra time. You may use one (1) double-sided hand-written page (size DIN A4) of arbitrary notes and a dictionary. No other books, notes, electronic devices etc. are allowed. You may bring reasonable food etc. You may use your own paper, which of course should not contain any other notes. If you really want, you can write down your answers in German. The exam sheet will be in English, though.

Literature: Most of the lecture will follow Reinhard Diestel's great book on graph theory. Visit this page to see the various formats in which the book is available (note that there is a free PDF version).

Search MPII (type ? for help)