Graph-Minor-Theorem verstehen

9

Diese Frage ist zweifach und hauptsächlich referenzorientiert:

  1. Gibt es irgendwo, wo die wichtigsten Intuitionen zum Beweis des Graph-Minor-Theorems gegeben sind, ohne zu sehr auf die Details einzugehen? Ich weiß, dass der Beweis lang und schwierig ist, aber es muss sicherlich Schlüsselideen geben, die auf einfachere Weise kommuniziert werden können.

  2. Gibt es andere Beziehungen in Graphen, von denen gezeigt werden kann, dass sie quasi gut geordnet sind, vielleicht auf einfachere Weise als für die Nebenbeziehung? (Offensichtlich bin ich nicht an trivialen Ergebnissen interessiert, wie dem Vergleichen von Größen). Gezielte Grafiken sind ebenfalls Gegenstand der Frage.

reference-request graph-theory graph-minor Denis
quelle
1
Ich interessiere mich besonders für Frage 1 ... Gibt es kein verständliches Beweisschema des Robertson-Seymour-Theorems?
Denis

Antworten:

8

Das folgende Buch behandelt einige Materialien, die sich auf den Beweis des Graph-Minor-Theorems beziehen (Kapitel 12).

Reinhard Diestel: Graphentheorie, 4. Auflage, Graduate Texts in Mathematics 173.

Der Autor stellt fest: "[...] wir müssen bescheiden sein: Vom tatsächlichen Beweis des Moll-Theorems wird dieses Kapitel nur einen sehr groben Eindruck vermitteln. Wie bei den wirklich fundamentalen Ergebnissen hat der Beweis jedoch die Entwicklung von Methoden von völlig unabhängigem Interesse und Potenzial. "

Eine elektronische Version des Buches kann online eingesehen werden. http://diestel-graph-theory.com/

Hermann Gruber
quelle
7

Zu Frage (2): Die Beziehungen zwischen Subgraph und induzierten Subgraph führen bei einigen eingeschränkten Klassen von Graphen zu Quasi-Ordnungen. Eine der Hauptreferenzen dort ist ein Artikel von G. Ding, Subgraphs and Well-Quasi-Ordering , J. Graph Theory, 16: 489–502, 1992, doi: 10.1002 / jgt.3190160509 . Das Papier

  1. zeigt, dass beide Ordnungen wqos für die Klasse der Graphen mit begrenzten Pfadlängen ergeben, und
  2. Noch interessanter ist, dass genau die erblichen Klassen von Graphen charakterisiert werden, für die die Untergraphenreihenfolge zu einem WQO wird (die Klasse sollte nur endlich viele Zyklen und "H-Graphen" enthalten).

Weitere Ergebnisse im Fall der induzierten Subgraph-Ordnung finden sich in diesem kürzlich erschienenen arXiv- Artikel von A. Atminas, V. Lozin und I. Razgon.

Sylvain
quelle
1
Das folgende Papier könnte auch in dieser Hinsicht von Interesse sein: MR Fellows, D. Hermelin, FA Rosamond: Well-Quasi-Ordnungen in Unterklassen von Bounded Treewidth-Graphen und ihre algorithmischen Anwendungen. Algorithmica 64 (1): 3-18, 2012
Hermann Gruber