Properti tertutup kecil yang secara eksplisit dapat diekspresikan MSO

Di bawah ini, MSO menunjukkan logika urutan kedua monadik dari grafik dengan kuantifikasi himpunan sudut dan himpunan tepi.

Biarkan menjadi kelompok kecil grafik tertutup. Ini mengikuti dari teori minor minor Robertson dan Seymour bahwa ditandai dengan daftar berhingga dari anak di bawah umur yang terlarang. Dengan kata lain, untuk setiap grafik , kita memiliki bahwa milik jika dan hanya jika mengecualikan semua grafik sebagai anak di bawah umur.$\mathcal{F}$$\mathcal{F}$$H_1,H_2,...,H_k$$G$$G$$\mathcal{F}$$G$$H_i$

Sebagai konsekuensi dari fakta ini, kami memiliki rumus MSO yang benar pada grafik$\varphi_{\mathcal{F}}$$G$ jika dan hanya jika . Sebagai contoh, grafik planar dicirikan oleh tidak adanya grafik K 3 , 3 dan K 5 sebagai anak di bawah umur, dan oleh karena itu mudah untuk secara eksplisit menulis rumus MSO yang mencirikan grafik planar.$G\in \mathcal{F}$$K_{3,3}$$K_5$

Masalahnya adalah bahwa bagi banyak properti grafik tertutup kecil yang bagus, daftar anak terlarang tidak diketahui. Jadi, sementara kita tahu bahwa rumus MSO mencirikan bahwa keluarga grafik ada, kita mungkin tidak tahu apa rumus ini.

Di sisi lain, itu mungkin terjadi bahwa seseorang dapat datang dengan formula eksplisit untuk properti yang diberikan tanpa menggunakan teorema minor grafik. Pertanyaan saya terkait dengan kemungkinan ini.

Pertanyaan 1: Apakah ada keluarga kecil tertutup dari grafik , sehingga himpunan anak di bawah umur terlarang tidak diketahui, tetapi beberapa rumus MSO φ yang mengkarakterisasi bahwa himpunan grafik diketahui?$\mathcal{F}$$\varphi$

Pertanyaan 2: Apakah beberapa formula MSO eksplisit diketahui mengkarakterisasi beberapa properti berikut?$\varphi$

1. Genus 1 (grafik dapat ditanam dalam torus) (lihat EDIT di bawah)
2. Genus k untuk beberapa tetap > 1 (lihat EDIT di bawah)$k>1$
3. k-outerplanarity untuk beberapa fixed $k> 1$

Saya akan sangat menghargai referensi atau pemikiran tentang masalah ini. Jangan ragu untuk mempertimbangkan properti tertutup kecil lainnya, daftar yang diberikan di atas hanya ilustrasi.

Obs: Secara eksplisit maksud saya bukan berarti kecil. Cukup memberikan argumen atau algoritme eksplisit yang menunjukkan cara membuat rumus yang mengkarakterisasi properti yang diberikan. Demikian pula, dalam konteks pertanyaan ini saya menganggap keluarga anak di bawah umur terlarang diketahui jika seseorang telah memberikan algoritma eksplisit membangun keluarga itu.

EDIT: Saya menemukan sebuah makalah oleh Adler, Kreutzer, Grohe yang menyusun rumus yang mencirikan grafik genus dengan dasar rumus mencirikan grafik genus k-1. Jadi makalah ini menjawab dua item pertama dari Pertanyaan 2. Di sisi lain, ini tidak menjawab Pertanyaan 1 karena memang ada algoritma yang membangun untuk setiap k, keluarga anak-anak terlarang yang mencirikan grafik genus k (Lihat bagian 4.2). Karena itu keluarga ini "dikenal" dalam arti pertanyaan.$k$

Saya punya jawaban di sini yang melibatkan grafik puncak tetapi gagal definisi tidak memiliki set halangan eksplisit yang diberikan dalam pertanyaan ini: ada algoritma yang diterbitkan untuk menemukan set halangan, meskipun terlalu lambat untuk dijalankan sehingga kita tidak benar-benar tahu apa set obstruksi itu.

Jadi, inilah keluarga jawaban parameterable lainnya tanpa cacat itu (setidaknya, sejauh yang saya tahu). Diberikan keluarga tertutup kecil , dan bilangan bulat k ≥ 1 , apakah grafik yang diberikan G memiliki k -ply yang mencakup grafik dalam F ? Banyak tentang pertanyaan semacam ini masih belum diketahui: khususnya dugaan Negami, yang akan menjadi ciri grafik yang memiliki grafik planar yang meliputi, tetap tidak terbukti. Dan itu tertutup kecil karena setiap langkah yang Anda ambil untuk membuat di bawah umur dari G dapat disalin di sampul.$F$$k\ge 1$$G$$k$$F$$G$

$k$$G$$F$$_2$

• $G$
• $(i,j)$$0\le i,j<k$$G$$i$$j$
• $G$
• $F$