Graph MinorsModulbeschreibung #40935 / Version 1
- 9 LP
- Mündliche Prüfung
- Benotet
- Winter- und Sommersemester
- Englisch
| Modul / Version | #40935 / #1 |
|---|---|
| Gültigkeit | Seit SS 2019 |
| Verfügbare Sprache(n) | Englisch |
| Leistungspunkte | 9 |
| Modulverantwortliche*r | Kreutzer, Stephan |
| Benotung | Benotet |
| Prüfungsform | Mündliche Prüfung |
| Lehrsprache(n) | Englisch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Softwaretechnik und Theoretische Informatik |
| Fachgebiet | 34352200 FG Logik und Semantik (LaS) |
Kontakt
| Sekretariat | EN 24 |
|---|---|
| Ansprechpartner*in | Pilz, Jana |
| E-Mail-Adresse | stephan.kreutzer@tu-berlin.de |
| Webseite | https://www.tu.berlin/las |
Lernergebnisse
After completion of this course students will have a profound understanding of the concepts, ideas and intermediate steps of the proof of the graph minor structure theorem. They will be able to identify the main steps in the proof and will be able to apply these ideas and results in other areas and applications.
Lehrinhalte
Among the most important results in modern combinatorics is Robertson and Seymour's proof of the graph minor theorem, commonly known as Wagner's conjecture. One way of stating this result is as follows: in every infinite class of finite undirected simple graphs there are two graphs H and G such that H is a minor of G.
To prove this result, Robertson and Seymour developed a deep structure theory of graphs in terms of the graph minor relation. Several concepts, ideas and intermediate results developed as part of this theory have found numerous applications in other areas of mathematics, computer science and beyond. In fact, the impact of concepts such as the "tree width" of a graph and its dual concepts of "brambles" or "grid minors" has been so pervasive that one could say that entirely new fields of research have emerged based on these ideas.
The structure theory developed as part of the graph minor project culminates in Robertson and Seymour's famous structure theorem for graphs excluding a fixed minor. Informally it says that every graph G
1. is somewhat similar to a tree (formalised by the notion of "tree width") or
2. contains a large complete graph as a minor or
3. can be decomposed into a tree of subgraphs of (almost) bounded genus (slightly more pecisely: has a tree decomposition whose pieces can almost be embedded into a fixed surface (into which G itself cannot be embedded of course)).
This theorem is not only interesting from a structural perspective but has deep implication in the theory of graph algorithms.
Despite its enormous complexity, the proof of the structure theorem follows a clear route with clearly identifiable intermediate steps, which are important in their own right. Furthermore, many results along the way can be understood on an intuitive level and many of them can be applied algorithmically as a black-box. That is, even without understanding or even reading their proof one can apply them in many algorithmic settings.
Finally, many steps of the proof are not only very interesting, or important, the underlying concepts and ideas are often simply stunning in their mathematical beauty making the study of graph minors an exciting endeavour.
In this course we will cover all essential aspects of the proof of the graph minor structure theorem. Starting with essentially no prerequisites we will introduce the fundamental concepts of tree width and grid minors, surfaces and surface embeddings, and then develop the proof of the structure theorem over the period of the course.
To prove this result, Robertson and Seymour developed a deep structure theory of graphs in terms of the graph minor relation. Several concepts, ideas and intermediate results developed as part of this theory have found numerous applications in other areas of mathematics, computer science and beyond. In fact, the impact of concepts such as the "tree width" of a graph and its dual concepts of "brambles" or "grid minors" has been so pervasive that one could say that entirely new fields of research have emerged based on these ideas.
The structure theory developed as part of the graph minor project culminates in Robertson and Seymour's famous structure theorem for graphs excluding a fixed minor. Informally it says that every graph G
1. is somewhat similar to a tree (formalised by the notion of "tree width") or
2. contains a large complete graph as a minor or
3. can be decomposed into a tree of subgraphs of (almost) bounded genus (slightly more pecisely: has a tree decomposition whose pieces can almost be embedded into a fixed surface (into which G itself cannot be embedded of course)).
This theorem is not only interesting from a structural perspective but has deep implication in the theory of graph algorithms.
Despite its enormous complexity, the proof of the structure theorem follows a clear route with clearly identifiable intermediate steps, which are important in their own right. Furthermore, many results along the way can be understood on an intuitive level and many of them can be applied algorithmically as a black-box. That is, even without understanding or even reading their proof one can apply them in many algorithmic settings.
Finally, many steps of the proof are not only very interesting, or important, the underlying concepts and ideas are often simply stunning in their mathematical beauty making the study of graph minors an exciting endeavour.
In this course we will cover all essential aspects of the proof of the graph minor structure theorem. Starting with essentially no prerequisites we will introduce the fundamental concepts of tree width and grid minors, surfaces and surface embeddings, and then develop the proof of the structure theorem over the period of the course.
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|---|---|---|---|---|---|
| Graph Minors | Integrierte Veranstaltung | Unregelmässig | [en] | 6 | ISIS |
Arbeitsaufwand und Leistungspunkte
Graph Minors (Integrierte Veranstaltung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 6 h | 90 h |
| Vor-/Nachbereitung | 15 | 12 h | 180 h |
| 270 h | |||
Der Aufwand des Moduls summiert sich zu 270 Stunden. Damit umfasst das Modul 9 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
The module is designed following the inverted class room model. After a few lectures recalling some basic concepts of graph and matroid theory, the students will follow a sequence of 18 videos taking them through the proof. After each video session there will be a tutorial style meeting in which various aspects of the proof step will be explored.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
The course will essentially introduce all concepts required for the course outcome. So only common knowledge of graph theory is required.
However, this is an extremely advanced course taking students into one of the most beautiful, but also most complex and deep theories of modern combinatorics/mathematics. Therefore, students should have a strong interest in graph theory and a very high level of mathematical maturity.
However, this is an extremely advanced course taking students into one of the most beautiful, but also most complex and deep theories of modern combinatorics/mathematics. Therefore, students should have a strong interest in graph theory and a very high level of mathematical maturity.
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Mündliche Prüfung |
| Sprache | Englisch, Deutsch |
| Dauer/Umfang | 30-45 minutes |
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Winter- und Sommersemester.
Maximale teilnehmende Personen
Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.
Anmeldeformalitäten
Students will have to sign up for the exam in the usual way.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
verfügbar
Empfohlene Literatur
Keine empfohlene Literatur angegeben
Zugeordnete Studiengänge
Diese Modulversion wird in folgenden Studiengängen verwendet:
| Studiengang / StuPO | Semester | Studiengangsbereich |
|---|---|---|
| Computer Engineering StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science (Informatik) StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Elektrotechnik StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
Master of Computer Science
Master of Mathematics
Master of Mathematics
Sonstiges
Keine Angabe