Długotrwałe przypuszczenia później potajemnie udowodniono przez domniemanie

Chciałbym wiedzieć, czy w TCS istniały przypuszczenia, które od dawna nie zostały udowodnione, a które później udowodniono na podstawie innego twierdzenia, które mogłyby być łatwiejsze do udowodnienia.

Erdös i Pósa udowodnili, że dla dowolnej liczby całkowitej i dowolnego wykresu albo ma rozłącznych cykli, albo istnieje zestaw wielkości co najwyżej wierzchołków tak że jest lasem. (w dowodzie ).$k$$G$$G$$k$$f(k)$$S\in G$$G\setminus S$$f(k) \in O(k \cdot \log k)$

Właściwość Erdösa i Pósy stałego wykresu znana jako następująca (nie formalna definicja):$H$

Klasa wykresów przyjmuje właściwość Erdős-posa jeśli jest funkcja , tak że dla każdego wykresu i dla każdej k \ w \ mathbb {Z} i dla każdego grafu G albo są k rozłączne izomorficzne kopiowaniem (WRT minor lub część) w H w G lub jest zbiór wierzchołków S \ G , tak że | S | \ le Rf (K) and G \ setminus S ma izomorficzną kopię H .$\mathcal{C}$$f$$H\in \mathcal{C}$$k \in \mathbb{Z}$$G$$k$$H$$G$$S\in G$$|S|\le f(k)$$G\setminus S$$H$

Po wyniku Erdösa i Pósy dla klasy cykli, które przyznają tę właściwość, otwartym pytaniem było znalezienie odpowiedniej klasy $\mathcal{C}$ . Na wykresie drugorzędnym V udowodniono, że każdy płaski wykres ma ograniczoną szerokość drzewa lub zawiera dużą siatkę jako drugorzędną, mając w ręku twierdzenie o siatce pokazało, że własność Erdösa i Pósy ma (dla drobnych) wtedy i tylko wtedy, gdy $\mathcal{C}$ to klasa grafów płaskich. Problem jest jednak nadal możliwy do podziału. Ale dowód twierdzenia wrt minor jest jakoś prosty i zgodnie z moją wiedzą nie ma dowodu bez użycia twierdzenia o siatce.

Najnowsze wyniki dla digraphs , dostarcza odpowiedzi na długo otwarte pytania w podobnej dziedzinie dla digraphs. np. jednym bardzo podstawowym pytaniem było to, że istnieje funkcja taka, że ​​dla dowolnego wykresu i liczb całkowitych możemy znaleźć zbiór co najwyżej wierzchołków, taki że ma cykl o długości co najmniej lub istnieją cykli rozłączne z co najmniej o długości w . To tylko wyjątkowy przypadek, ale dlaG k , l S ⊆ V ( G ) f ( k + l ) G - S l k l G l = $f$$G$$k,l$$S\subseteq V(G)$$f(k+l)$$G-S$$l$$k$$l$$G$$l=2$było znane jako przypuszczenie Youngera. Wcześniej przypuszczenie Youngera zostało udowodnione przez Reeda i wsp. Przy dość skomplikowanym podejściu.

Warto wspomnieć, że wciąż istnieją dość nietrywialne przypadki w digrafach. np. Twierdzenie 5.6 w powyższym artykule jest tylko pozytywnym rozszerzeniem hipotezy młodszego człowieka na małą klasę słabo połączonych digrafów, ale dzięki wiedzy i narzędziom matematycznym, które mamy, nie jest to trywialne (a może nie znamy prostego argumentu na ten temat ). Być może dzięki lepszej charakterystyce tych wykresów łatwiej będzie to udowodnić.

tytuł pytania odnosi się do „trywialnych implikacji”, ale treść nie określa dokładnie tych kryteriów, więc jest to trochę mieszany komunikat. jeden semifamiczny przedmiot / przykład zbliżony do ogólnego tematu jest dowodem (przypuszczalnie sprzed 4 lat) Strong Perfect Graph Conjecturew 2002 roku: Maria Chudnovsky, Neil Robertson, Paul Seymour i Robin Thomas. problem algorytmicznej złożoności rozpoznawania idealnych wykresów okazał się być ściśle związany / ściśle z mechaniką dowodową silnej idealnej hipotezy grafowej, chociaż nie było to dokładnie zrozumiane ani znane przed dowodem przypuszczenia. innymi słowy, istniała nieformalna otwarta hipoteza, że ​​„perfekcyjne rozpoznawanie grafu jest w P” (lub „niska złożoność” itd.) stosunkowo szybko rozwiązane poprzez wykorzystanie analizy / właściwości / mechaniki twierdzenia o silnym idealnym grafie.

Algorytm wielomianowy do rozpoznawania idealnych wykresów Gérard Cornuéjols, Xinming Liu, Kristina Vušković 2003