Zrozumienie graficznego mniejszego twierdzenia

9

To pytanie jest dwojakie i dotyczy głównie odniesienia:

  1. Czy jest gdzieś, gdzie podane są główne intuicje dowodzenia niewielkiego twierdzenia o grafie, bez zbytniego zagłębiania się w szczegóły? Wiem, że dowód jest długi i trudny, ale z pewnością muszą istnieć kluczowe pomysły, które można przekazać w łatwiejszy sposób.

  2. Czy istnieją inne relacje na wykresach, które mogą być pokazane jako quasi-porządki, może w prostszy sposób niż dla relacji mniejszej? (oczywiście nie interesują mnie tutaj trywialne wyniki, takie jak porównywanie rozmiarów). Kierowane wykresy również wchodzą w zakres pytania.

Denis
źródło
1
Szczególnie interesuje mnie pytanie 1 ... Nie istnieje żaden zrozumiały schemat dowodowy twierdzenia Robertsona-Seymour?
Denis

Odpowiedzi:

8

Poniższa książka obejmuje niektóre materiały związane z dowodem twierdzenia o grafie mniejszym (rozdział 12).

Reinhard Diestel: Teoria grafów, 4. edycja, Graduate Texts in Mathematics 173.

Autor stwierdza: „[...] musimy być skromni: jeśli chodzi o rzeczywisty dowód drobnego twierdzenia, ten rozdział przyniesie tylko bardzo szorstkie wrażenie. Jednak, jak w przypadku najbardziej prawdziwie fundamentalnych wyników, dowód wywołał opracowanie metod o dość niezależnym zainteresowaniu i potencjale. ”

Elektroniczną wersję książki można obejrzeć online. http://diestel-graph-theory.com/

Hermann Gruber
źródło
7

W przypadku pytania 2: relacje subgrafu i indukowane subgrafy powodują powstanie dobrze quasi-porządków na niektórych ograniczonych klasach grafów. Jednym z głównych odniesień jest artykuł G. Dinga, Subgrafy i dobrze quasi-porządkowe , J. Graph Theory, 16: 489–502, 1992, doi: 10.1002 / jgt.3190160509 . Papier

  1. pokazuje, że oba porządki dają wqos w klasie wykresów o ograniczonej długości ścieżki, oraz
  2. co jeszcze ciekawsze, charakteryzuje dokładnie dziedziczne klasy grafów, dla których porządkowanie podgraphów staje się wqo (klasa powinna zawierać tylko skończenie wiele cykli i „wykresów H”).

Więcej wyników w przypadku indukowanego uporządkowania subgrafów można znaleźć w najnowszym artykule arXiv autorstwa A. Atminasa, V. Lozina i I. Razgona.

Sylvain
źródło
1
Interesujący w tym względzie może być również następujący artykuł: MR Fellows, D. Hermelin, FA Rosamond: Well-Quasi-zamówienia w podklasach ograniczonych wykresów Treewidth i ich zastosowania algorytmiczne. Al Algorytmica 64 (1): 3-18, 2012
Hermann Gruber