Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Benjamin Doerr: Teaching


Graph Theory (winter 06/07)

PD Dr. Benjamin Doerr and Dr. Martin Kutz †

Time: Monday + Wednesday 14-16. Start: October 18, 2006. Graph
Room: Room 001, Building E13

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 SWS, 9 LP). It needs no particular prerequisites except the basics in mathematics. We offer exercise groups (2 SWS), which will be set up in the first lecture. The lecture will be given in English.

The problems for the exercises can be found here.

Forum: A discussion forum on anything related to the course can be found here.
Lecture details:
Date Lecturer Topic Reference
Oct 18 BD Introduction, Euler tours [1.8]
Oct 23 BD Degrees, Paths, Cycles [1.2, 1.3 except 1.3.3, 1.3.4]
Oct 25 BD Connectivity, Trees [1.4 except 1.4.3; 1.5.1]
Oct 30 PS Bipartite graphs [1.5.2 - 1.5.4; 1.6]
Nov 1 [Allerheiligen]
Nov 6 BD Matchings in bipartite graphs [2.1]
Nov 8 BD Tutte's 1-factor theorem [2.2.1 and proof]
Nov 13 PS Matchings in general graphs [2.2.2, 2.2.3 without proof]
Nov 15 PS Matchings in general graphs [proof of 2.2.3]
Nov 20 BD Dilworth, Contractions, Menger [2.5, p.18, 3.3.1 1st proof]
Nov 22 BD global Menger, vertex coloring [3.3.5+6, 5.0, 5.2.1+4]
Nov 27 BD Edge coloring [5.3]
Nov 29 BD Ramsey Theory: R(3)=6, Ramsey's Thm. for 2 colors, Erdoes' lower bound, chit-chat Wikipedia [partial coverage].
Dec 4 BD Hypergraph coloring, discrepancy :-)
Dec 6
Dec 11 BD, PS Exam preparation
Dec 13 -- Midterm Exam: 14:00-as you like ;-)
Dec 18 PS Topological prerequisites [4.1, 4.2.1]
Dec 20 PS Plane Graphs [4.2.2 - 4.2.7]
[christmas holidays]
Jan 8 BD Discussion Midterm Exam
Jan 10 BD Euler's formula [4.2.8 - 11]
Jan 15 DJ Planar graphs, coloring planar graphs, minors, Kuratowski's theorem [1.7.1 without proof as definition, 1.7.2 as exercise 10.3, 4.4.1, 4.4.6 without proof, 5.1.1, 5.1.2]
Jan 17 BD Introduction to random graphs [11.1]
Jan 22 BD Threshold functions, expectation, variance [11.3 except 11.3.4, 11.3.5]
Jan 24 BD Second moment method [11.4, proof of 11.4.3 for H = triangle]
Jan 29 BD Large girth and chromatic number, Hamilton cycles [11.2, 10.1.1]
Jan 31 BD Theorems of Ore, Erdös-Chvátal. [Ex., 10.1.2, 10.2.1 weak form]
Feb 5 BD Extremal graph theory, Turan graphs, Turan's theorem [7.1.1]
Feb 7 BD Random walks on undirected graph
Feb 12 BD
Feb 14 -- Final Exam


Exams/Credit: There is a midterm exam on December 13, 2006, and a final exam on February 14, 2007. To get admitted to the midterm and the final exam, one has to get at least 62.5% of the points from all exercise sheets up to the respective exam (recall the one-point bonus for not touching a problem) and show up regularly in the exercise sessions (at most two misses). Eventually, there will also be a repetition examination.

You have to pass the midterm exam (grade "four" or better) in order to get admitted to the final or even the repetition exam. This shall encourage serious efforts from the very beginning and is also meant to avoid that anyone who missed too much during the first half of the semester wastes unneccessary efforts later on.
In exceptional cases, students who fail in the midterm may continue to the final exam. There has be serious reason for such an exception.

Your final grade depends on both, the midterm and the final exam. Each will contribute 50% to the final result. You get a "Schein", if you reach a grade of "four" or better.

Anyone who got admitted to the final exam will be allowed to participate in the repetition exam. Irrespective of whether they passed or failed in the final. Grades in the repetition exam can only improve the total performance. If better, they will replace the combined grades from midterm and final. (In particular, if you scored very high in the midterm but failed in the final, a successful repetition exam will determine the grade for the whole course. The grade from the midterm will get overridden in this case.)
The repetition exam will be oral or written, depending on the number of candidates.

Midterm Exam: The midterm exam takes place December 13, 2006. It will be in the other (larger) lecture hall (next to the one we're normally in). It starts at 14:00 and lasts longer than the usual lecture (allow time). More precisely, you have as much time as you like, but no longer than 19:45, because of building restrictions. However, a typical candidate should be able to solve the exam within three hours. The extra time is just because we like you to come up with good solutions instead of fast ones.

You may use one (1) single-sided hand-written page (size DIN A4) of arbitrary notes. [Note: In the final exam, you may use one hand-written sheet (both sides).] No other books, notes, electronic devices etc. are allowed. You may bring reasonable food etc. if you plan to use plenty of time. You may use your own paper, which of course should not contains any other notes. If I catch you cheating, (a) you fail and face all other problems the "Studienordnung" tells you, and (b) I hate you for that. So better don't do that.

Final Exam: The final exam takes place February 14, 2007. It will be in the other (larger) lecture hall (next to the one we're normally in). You have to be there at 14:00. You will have exactly three (3) hours to solve the problems. Naturally, there will be fewer problems than last time, but also slightly less time per problem (sorry, that's what the Pruefungsordnung asks me to do).

Since it usually takes some time to set up an exam, don't expect to finish at 17:00 sharp, but allow some extra time.
You may use one (1) double-sided hand-written page (size DIN A4) of arbitrary notes. 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.

We plan to correct the exam Thursday and Friday and have the results ready and posted on the web by Friday evening.

Literature: Most of the lecture will follow Reinhard Diestels great book on graph theory. Visit his page for the details. As you can see, there is an English language edition for 39.95 or 42.95 Euros (depending on whether you look a his or Springer's page) and a German one for 29.95 Euros. The English one has an extra chapter on infinite graphs and some other additions. These will, however, not be covered in the lecture. Hence the only real difference is the language (and the price). Numbers given as references above refer to chapters or theorems in the English version, 3rd (=current) edition.
Search MPII (type ? for help)