Versi kombinatorial untuk dugaan Hirsch polinomial

Pertimbangkan keluarga menguraikan himpunan bagian dari {1,2, ..., n}, F 1 , F 2 , ... F t .$t$${\cal F}_1,{\cal F_2},\dots {\cal F_t}$

Seandainya

(*)

Untuk setiap dan setiap R ∈ F i , dan T ∈ F k , ada S ∈ F j yang berisi R ∩ T .$i \lt j \lt k$$R \in {\cal F}_i$$T \in {\cal F}_k$$S \in {\cal F}_j$$R \cap T$

Pertanyaan dasarnya adalah:

Seberapa besar tidak bisa ???

Apa yang diketahui?

Batas atas yang paling dikenal adalah kuasi polinomial .$t \le n^{\log n+1}$

Batas bawah yang paling dikenal adalah kuadrat (hingga faktor logaritmik).

Pengaturan abstrak ini diambil dari kertas Diameter Polyhedra: Batas-Batas Abstraksi oleh Friedrich Eisenbrand, Nicolai Hähnle, Sasha Razborov, dan Thomas Rothvoss . Batas bawah kuadratik serta bukti batas atas dapat ditemukan dalam makalah mereka.

Motivasi

Setiap batas atas akan diterapkan pada diameter grafik poltop berdimensi-d dengan n segi. Untuk melihat asosiasi ini ke setiap simpul set S v dari segi yang mengandungnya. Kemudian mulai dari titik w, biarkan F r menjadi himpunan yang sesuai dengan simpul dari polytope jarak r + 1 dari w .$v$$S_v$$w$${\cal F}_r$$r+1$$w$

Lebih

Masalah ini adalah pokok bahasan polymath3 . Tapi saya pikir akan bermanfaat untuk mempresentasikannya di sini dan di MO meskipun itu merupakan masalah terbuka. Jika proyek akan mengarah ke subproblem tertentu, saya (atau orang lain) dapat mencoba menanyakannya juga.

(Perbarui; 5 Okt :) Salah satu masalah khusus yang menarik perhatian adalah membatasi perhatian pada set ukuran d. Biarkan f (d, n) menjadi nilai maksimum t ketika semua set dalam semua keluarga memiliki ukuran d. Misalkan f * (d, n) menjadi nilai maksimal t ketika kita mengizinkan multiset ukuran d. Memahami f * (3, n) mungkin sangat penting.

Masalah: Apakah f * (3, n) berperilaku seperti 3n atau seperti 4n?

Batas bawah dan atas yang diketahui masing-masing adalah 3n-2 dan 4n-1. dan karena 3 adalah awal dari urutan 'd' sedangkan 4 adalah awal dari urutan memutuskan apakah kebenarannya 3 atau 4 tidak penting. Lihat utas kedua .$2^{d-1}$

$t$$n$$d$$3^{2^n}$$f$dari beberapa nilai pertama. Kami juga belum mempelajari semua komentar dari utas sebelumnya secara terperinci, jadi beberapa di antaranya mungkin sudah diketahui - kami pada dasarnya senang membuat kode kami dengan cepat dan ingin memposting hasil kami di suatu tempat, jika saya memiliki lingkungan LaTeX yang berfungsi, saya akan memiliki letakkan ini di ArXiV.

Kode (ini bukan kode produksi ...): http://pastebin.com/bSetW8JS . Nilai:

f(d=2, n)=2n-1 for n <= 6

f(d=3, n=3) = 6
{} {0} {01} {012} {12} {2}

f(d=4, n=4) = 8
f(d=3, n=4) = 8
{} {0} {01} {1,02,03} {2,13} {123} {23} {3}
{} {0} {01} {2,013} {1,02,03} {023} {23} {3}

f(d=5, n=5) = 11
f(d=4, n=5) = 11
f(d=3, n=5) = 11
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {1,02} {2,13,04} {12,03,14} {3,124} {23,24} {234} {34} {4}
{} {0} {01} {012,3} {02,12,013,014} {13,023,04,124} {123,024} {23,24} {234} {34} {4}
{} {0} {01} {012,13} {02,12,013} {03,123,014,024} {023,124} {23,24} {234} {34} {4}

${\cal F}_1, ..., {\cal F}_t$${\cal F}_1, ..., {\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}$${\cal F}_1, ..., {\cal F}_t$$A \in {\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$$A$${\cal F}_1, ..., {\cal F}_{t-1}$${\cal F}_1, ..., {\cal F}_{t-1}, \{ A \}$${\cal F}_t$${\cal F}_1, ..., {\cal F}_t$

$\sim$${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$$A$${\cal F}_1, ..., {\cal F}_t$${\cal F}'_1, ..., {\cal F}'_t$${\cal F}_1, ..., {\cal F}_t \sim {\cal F}'_1, ..., {\cal F}'_t$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1} \sim {\cal F}'_1, ..., {\cal F}'_t, {\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t, {\cal F}_{t+1}$${\cal F}_{t+1}$${\cal F}_1, ..., {\cal F}_t$. Algoritma pemrograman dinamis berikutnya kemudian jelas. Jumlah kelas ekivalensi (bersama dengan waktu yang diambil oleh dua operasi di atas) kemudian memberikan batas waktu berjalan dari algoritma pemrograman dinamis yang jelas.

$A$$\{ 1, \dots, n \}$$A$${\cal F}_1, ..., {\cal F}_t$$\{ k \mid \exists B \in {\cal F}_k : A \subseteq B \} = \{ i, \dots, j \}$$1 \leq i \leq j \leq n$$(i, j)$$A$${\cal F}_1, ..., {\cal F}_t$$\{ 1, \dots, n \}$

${\cal F}_1, ..., {\cal F}_t$$\{ 1, \dots, n \}$${\cal F}_t$${\cal F}_1, ..., {\cal F}_{t-1}$$B$$A$${\cal F}_1, ..., {\cal F}_{t-1}$$(i, j)$$j < t - 1$$A$$\sim$$B$$C \in {\cal F}_t$$D \in {\cal F}_{t+1}$$B \cap C \subseteq D$$3^{2^n}$

Kami juga menggunakan berbagai pemangkasan ekstra. Kami hanya mempertimbangkan antichains untuk dan kami mengharuskan unsur-unsur unsur-unsurnya berasal dari 1 , ... , i . Terakhir, kami menggunakan optimasi yang F 1 = { { 1 } } , F 2 = { ${\cal F}_{t+1}$${1, \dots, i}$${\cal F}_1 = \{ \{ 1 \} \}, {\cal F}_2 = \{ \{ 1, 2 \} \}$${\cal F}_{t-1}$${\cal F}_t$${\cal F}_3$ dapat menghasilkan penghematan yang lebih drastis.