To pytanie jest dwojakie i dotyczy głównie odniesienia:
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.
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.
Odpowiedzi:
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/
źródło
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
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.
źródło