Cytowanie pokazujące osoby niepełnoletnie są nieletnimi topologicznymi dla wykresów podrzędnych

Jeśli jest wykresem w stopniu maksymalnie 3 i jest minor , a jest topologiczna minor . $G$ $H$ $G$ $H$

Wikipedia cytuje ten wynik z „Teorii grafów” Diestela. Jest wymieniony jako Prop 1.7.4 w najnowszej wersji książki. W książce brakuje dowodu lub cytowania.

Czy miejsce pobytu znane jest z (oryginalnego) dowodu na to?

Co więcej, czy istnieje odniesienie potwierdzające, że jeśli jest ścieżką lub podpozycją pazura i jest mniejszy od to jest podrozdziałem ? Jest tu krótko wspomniane , ale nie ma odniesienia. $G$ $H$ $G$ $H$

— Eli
źródło

Książka jest dostępna na diestel-graph-theory.com

— Alexander Langer,

Dzięki Alexander. Ta wersja książki nie zawiera odniesienia ani dowodu na propozycję, czy wiesz, czy pełne wydanie ma ją, czy może inne źródło?

— Eli

Pamiętam, że szukałem cytatu z drugiego stwierdzonego przez ciebie faktu, ale niczego nie znalazłem. Najlepszy cytat, jaki znam na pierwsze stwierdzenie, to książka Diestela, która nie dowodzi tego stwierdzenia. Poczekam, czy ktoś znajdzie cytat. Jeśli nie, opublikuję dowód jako odpowiedź.

— Robin Kothari,

@ Robin, w tym momencie, jeśli opublikujesz dowód, to mi wystarczy. Czy istnieje odpowiedni sposób na przypisanie, że należy gdzieś użyć tego wyniku? Nie znam zasad wymiany stosów ani standardowych praktyk.

— Eli

W rzeczywistości cytowanie zostało już omówione i rozwiązane tutaj: meta.cstheory.stackexchange.com/questions/352/…

— Aaron Sterling

Jeśli jest wykresem w stopniu maksymalnie 3 i jest minor , a jest topologiczna minor . $G$ $H$ $G$ $H$

Ponieważ jest mniejsze od , można uzyskać z , usuwając krawędzie, izolując wierzchołki i wykonując skurcze krawędzi. Łatwo jest również wykazać, że możemy nalegać, aby najpierw wykonać operacje subgraficzne, tzn. Możemy najpierw wykonać wszystkie usuwanie krawędzi i wierzchołków, a następnie wykonać wszystkie skurcze krawędzi. Ponadto ograniczmy definicję „skurczu krawędzi”, aby nie dopuścić do kurczenia się krawędzi, gdy jeden z wierzchołków ma stopień 1. Skurczenie takiej krawędzi jest równoznaczne z jej usunięciem, więc nie zmieni to definicji drugorzędnych wykresów. $G$ $H$ $G$ $H$

Niech będzie wykresem uzyskanym z , wykonując najpierw wszystkie usunięcia krawędzi / wierzchołków. nadal zawiera jako nieletni. Jeśli pokażemy, że zawiera jako drobną topologię, to już skończymy, ponieważ definicja drobnej topologii pozwala również na usuwanie krawędzi / wierzchołków. $H'$ $H$ $H'$ $G$ $H'$ $G$

$G$ $H'$ $H'$

$H'$ $G$

$H_1$ $H_2$ $H_2$ $H_1$ $H'$ $G$ $G$ $H'$ $H$

$G$ $H$ $G$ $H$

$G$ $H$ $H$ $H$ $G$

Potrzebowaliśmy tego wyniku raz, więc umieściliśmy krótki dowód w naszym dokumencie. Możesz znaleźć wynik w kwantowej złożoności kwantowych właściwości niewielkich zamkniętych wykresów . Wspomniano o tym na stronie 13. Jednak fakt ten jest ukryty w dowodzie czegoś innego i nie został wyraźnie określony jako twierdzenie.

Interesujące jest również to, że istnieje odwrotność tego twierdzenia:

$G$ $G$ $G$

— Robin Kothari
źródło

Dzięki. Jeśli zdarzy ci się natknąć na opublikowane cytowanie tych wyników, nadal bym to chciał, ale to jest gwiezdne.

— Eli

Ta odpowiedź jest teraz dostępna na blogu społeczności.

— Aaron Sterling

Dobra odpowiedź, ale myślę, że twoja technika nie pozwalania na skurcze stopnia 1 ma wadę. Na przykład rozważmy G = K_4 minus jakakolwiek krawędź. Skurczenie wzdłuż dwóch wierzchołków stopnia 3 w G spowoduje wygenerowanie wykresu ścieżki P_3, z maksymalnym stopniem 2. Zamiast tego, jeśli nie dopuścisz żadnych skurczów na krawędzi, które byłyby równoważne z pewnym usunięciem, dowód powinien przejść. Formalnie zabrania się jakiegokolwiek skurczu między wierzchołkiem x i y, jeśli gamma (x) \ {y} = gamma (y) \ x. Łatwo jest wykazać, że każdy skurcz nie naruszający tego ograniczenia spowoduje powstanie nowego wierzchołka o nie zmniejszonym stopniu.

— RussellStewart

@ user2237635: Masz rację, dzięki.

— Robin Kothari