Zrozumienie graficznego mniejszego twierdzenia

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.

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/

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.