Niewielkie zamknięte właściwości, które są wyraźnie wyrażalne przez MSO

Poniżej MSO oznacza monadyczną logikę drugiego rzędu grafów z kwantyfikacjami zbioru wierzchołków i zbocza.

Niech będzie niewielką zamkniętą rodziną grafów. Z teorii drugorzędnej grafu Robertsona i Seymour wynika, że charakteryzuje się skończoną listą zakazanych nieletnich. Innymi słowy, dla każdego wykresu mamy, że należy do wtedy i tylko wtedy, gdy wyklucza wszystkie wykresy jako nieletnie.F H 1 , H 2 , . . . , H k G G F G H $\mathcal{F}$$\mathcal{F}$$H_1,H_2,...,H_k$$G$$G$$\mathcal{F}$$G$$H_i$

W wyniku tego mamy formułę MSO która jest prawdziwa na wykresie wtedy i tylko wtedy, gdy . Na przykład wykresy płaskie charakteryzują się brakiem wykresów i jako nieletnich, dlatego łatwo jest wyraźnie napisać formułę MSO charakteryzującą wykresy płaskie. G G ∈ F K 3 , 3 K $\varphi_{\mathcal{F}}$$G$$G\in \mathcal{F}$$K_{3,3}$$K_5$

Problem polega na tym, że dla wielu ładnych drobnych zamkniętych wykresów lista zabronionych nieletnich jest nieznana. Chociaż wiemy, że istnieje formuła MSO charakteryzująca tę rodzinę grafów, możemy nie wiedzieć, czym jest ta formuła.

Z drugiej strony może się zdarzyć, że uda się opracować wyraźną formułę dla danej właściwości bez użycia twierdzenia graf moll. Moje pytanie dotyczy tej możliwości.

Pytanie 1: Czy istnieje niewielka zamknięta rodzina grafów , taka, że ​​zestaw zabronionych nieletnich nie jest znany, ale znana jest pewna formuła MSO charakteryzująca ten zestaw grafów?$\mathcal{F}$$\varphi$

Pytanie 2: Czy znana jest konkretna formuła MSO charakteryzująca niektóre z następujących właściwości?$\varphi$

1. Rodzaj 1 (wykres można osadzić w torusie) (patrz EDYCJA poniżej)
2. Rodzaj k dla niektórych ustalonych (patrz EDYCJA poniżej)$k>1$
3. k-zewnętrzna płaszczyzna dla niektórych ustalonych $k> 1$

Byłbym wdzięczny za wszelkie odniesienia lub przemyślenia na ten temat. Proszę wziąć pod uwagę inne drobne zamknięte nieruchomości, powyższa lista ma jedynie charakter poglądowy.

Obs: Mówiąc wprost, nie mam na myśli niekoniecznie małych. Wystarczy podać wyraźny argument lub algorytm pokazujący, jak skonstruować formułę charakteryzującą daną właściwość. Podobnie w kontekście tego pytania uważam rodzinę niedozwolonych nieletnich za znaną, jeśli podano wyraźny algorytm konstruujący tę rodzinę.

EDYCJA: Znalazłem artykuł Adlera, Kreutzera, Grohe, który konstruuje formułę charakteryzującą wykresy rodzaju na podstawie formuły charakteryzującej wykresy rodzaju k-1. Zatem niniejszy artykuł odpowiada na dwa pierwsze pytania pytania 2. Z drugiej strony nie odpowiada to na pytanie 1, ponieważ rzeczywiście istnieje algorytm konstruujący dla każdego k, rodziny zabronionych nieletnich charakteryzujących wykresy rodzaju k (patrz punkt 4.2). Dlatego ta rodzina jest „znana” w sensie pytania.$k$

Miałem tutaj odpowiedź dotyczącą wykresów wierzchołkowych, ale nie spełnia ona definicji braku wyraźnego zestawu przeszkód podanego w tym pytaniu: istnieje opublikowany algorytm znajdowania zestawu przeszkód, mimo że jest zbyt wolny, aby uruchomić, więc nie wiemy czym jest zestaw przeszkód.

Oto kolejna parametryzowana rodzina odpowiedzi bez tej wady (przynajmniej, o ile mi wiadomo). Biorąc pod uwagę niewielką zamkniętą rodzinę i liczbę całkowitą k ≥ 1 , czy dany wykres G ma k- płynny wykres pokrywający w F ? Wiele na temat tego rodzaju pytań pozostaje nieznanych: w szczególności hipoteza Negami'ego, która charakteryzowałaby wykresy zawierające płaski wykres pokrywający, pozostaje niepotwierdzona. I jest drobno zamknięty, ponieważ wszelkie kroki, które zrobisz, aby zrobić z G mniejszą, można skopiować na okładce.$F$$k\ge 1$$G$$k$$F$$G$

W celu sprawdzenia istnienia -ply osłoną G na F w MSO 2 , należy wykonać następujące czynności:$k$$G$$F$$_2$

• Użyj trick głębokość pierwszego wyszukiwania drzewo dostać (dowolny) orientację .$G$
• Dla każdej pary o wartości 0 ≤ i , j < k wybierz zestaw krawędzi w G , prawdopodobnie tych, które mają krawędź okrywającą, która przechodzi od warstwy i do warstwy j .$(i,j)$$0\le i,j<k$$G$$i$$j$
• $G$
• $F$