TUM – TUM – Menü


Extremal Graph Theory

Vorlesung / Lecture Course


Lectures: Anusch Taraz
Exercises: Anusch Taraz
Format: 2+1 SWS
ECTS-Credits: 5 ECTS


  • If you want to participate in the exam, contact the lecturer by email immediately, indicating whether you want your exam to be in July, August or September. First exams will be on July 17 and 18.
  • Third Problem Sheet is online, see below, with many straight forward exercises
  • Next Exercise Class: Wednesday July 10 at 18:00 in 03.10.011
  • Second Problem Sheet is online, see below.
  • Lecture Notes for Lectures 4 and 5 are online.
  • The standard times for Exercise Classes are Wednesday 14-16 and Thursday 10-12. However, in May these are not always possible for me and therefore need to be adjusted. The first Exercise Class will be on Wednesday May 22. Due to a clash with a Fakultätsratsitzung it has to be shifted to 18:00-20:00. Due to a public holiday on Thursday May 30, the second Exercise Class will be on Wednesday May 29, at 14:00-16:00.
  • Lectures will always start at 8:15 from now.
  • There will be no lecture in the first week of term. The first lecture will be on April 24.

Contents of the course

  • Fixed subgaphs (Theorems of Turan and Erdös-Stone)
  • The Regularity Method (Regularity Lemma, Embedding Lemma, Counting Lemma, Blow-up Lemma)
  • Spanning subgraphs (Spanning factors and powers of Hamilton cycles)
  • Ramsey Theory (Graphs with linear Ramsey number)

Target audience

The course is aimed at Master students who are interested in Discrete Mathematics and would like to complement the lectures on optimization. Bachelor students are also invited to attend.

Prerequisites for the course

  • Background in Discrete Mathematics, Analysis, Linear Algebra, Probability

Exercise Classes / Exam

  • There will be an exam at the end of the lecture period. If there are less than 20 candidates taking the exam, it will be done as an oral exam (20-30 minutes) for each student separately, otherwise as a written exam (60 minutes).
  • In the exercise classes, you will be working in small groups on specific problems and discuss your approach with the lecturer. Every student can choose whether she wants her performance during these classes to be evaluated. If yes, this part contributes 50 percent to the final grade, provided that this doesn't worsen the grade.

Übungsbetrieb / Prüfung

  • Nach Abschluss der Vorlesung findet im Prüfungszeitraum eine Prüfung statt. Melden sich weniger als 20 Kandidaten zur Prüfung an, dann erhält jeder Kandidat eine mündliche Prüfung (20-30 Minuten), andernfalls findet eine schriftliche Prüfung (60 Minuten) statt.
  • In den Übungen arbeiten Sie in Kleingruppen an ausgewählten Übungsaufgaben und diskutieren Ihre Lösungsansätze mit dem Dozenten. Jeder Studierende hat die Möglichkeit, dass die hierbei erbrachten Leistungen ebenfalls bewertet und als 50-prozentiger Anteil in die Endnote miteingebracht werden, falls sich diese dadurch nicht verschlechtert. Auf diese Weise soll im Rahmen dieses Pilotprojekts auch die mündliche Mitarbeit in die Bewertung einfließen können.


Dates of lectures / exercise classes

Type Day Time Room Teacher Dates
Lecture Wednesday 8:15-09:45 03.10.011 Taraz every week, starting April 24
Exercise Class Wed, May 22 18:00- to be discussed Taraz  
Exercise Class Wed, May 29 14:15-15:45 MI HS 3 Taraz  
Exercise Class Thu, June 06 10:15-11:45 MI 02.06.020 Taraz  
Exercise Class Wed, June 12 14:15-15:45 MI HS 3 Taraz  
Exercise Class Thu, June 20 10:15-11:45 MI 02.06.020 Taraz  
Exercise Class Thu, July 4 10:15-11:45 MI 02.06.020 Taraz  
Exercise Class Wed, July 10 18:00-19:30 MI 03.10.011 Taraz  


Problem Sheet 1
Problem Sheet 2
Problem Sheet 3

Lecture notes

Day File Topics
24.04.2013 Lecture 1 0. Overview (0.1-0.3)
08.05.2013 Lecture 2 0. Overview (0.4-0.9)
22.05.2013 Lecture 3 1. Regularity Method (0.10-1.4)
29.05.2013 Lecture 4 1. Regularity Method (1.5-1.6, Proof for 0.6)
05.06.2013 Lecture 5 1. Regularity Method (1.7-1.11)
12.06.2013 Lecture 6 2. Ramsey Theory (2.1: Ramsey's theorem)
19.06.2013 Lecture 7 2. Ramsey Theory (2.2: Erdös-Szekeres' theorem)
26.06.2013 Lecture 8 2. Ramsey Theory (2.3-2.9: Schur, Van der Waerden)
03.07.2013 Lecture 9 2. Ramsey Theory (Proof for 2.7 (Hales-Jewett))
10.07.2013 Lecture 10 2. Ramsey Theory (2.9-2.13: Ramsey number of graphs)
17.07.2013 Lecture 11 1.13-1.16 and Proof of 1.2


  • B. Bollobás: Extremal Graph Theory. Cambridge University Press.


question When and where will the exam take place?
info To be decided.

Research Unit M9

Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
phone:+49 89 289-16858
fax:+49 089 289-16859


Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics


Jan 25th, 2019
Case Studies 2019: Preliminary Meeting on Wed, Feb 6th, at 16:00 in room MI 03.06.011.