Wersja kombinatoryczna dla wielomianowej hipotezy Hirscha

Rozważ rozłącznych rodzin podzbiorów {1,2,…, n}, F 1 , F 2 , … F t .$t$${\cal F}_1,{\cal F_2},\dots {\cal F_t}$

Przypuszczam, że

(*)

Dla każdego i każdy R ∈ F ı i T ∈ K K , jest S ∈ F j , który zawiera 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$

Podstawowe pytanie brzmi:

Jak duży może być ???

Co jest znane

Najbardziej znaną górną granicą jest quasi-wielomian .$t \le n^{\log n+1}$

Najbardziej znana dolna granica to (do współczynnika logarytmicznego) kwadratowa.

To abstrakcyjne ustawienie pochodzi z pracy Diameter of Polyhedra: The Limits of Abstraction autorstwa Friedricha Eisenbranda, Nicolai Hähnle, Sashy Razborova i Thomasa Rothvossa . Kwadratowa dolna granica oraz dowód górnej granicy można znaleźć w ich pracy.

Motywacja

Każda górna granica dotyczy średnicy wykresów dwuwymiarowych polytopów o n ściankach. Aby zobaczyć to skojarzenie z każdym wierzchołkiem zestaw S v aspektów zawierających go. Następnie, zaczynając od wierzchołka w, niech F r będzie zestawami odpowiadającymi wierzchołkom polytopu odległości r + 1 od w .$v$$S_v$$w$${\cal F}_r$$r+1$$w$

Więcej

Ten problem jest przedmiotem polymath3 . Ale pomyślałem, że może być użyteczne zaprezentowanie go tutaj i na MO, mimo że jest to otwarty problem. Jeśli projekt doprowadzi do określonych podproblemów, ja (lub inni) też mogę spróbować je zapytać.

(Aktualizacja; 5 października :) Jednym szczególnym problemem, który jest szczególnie interesujący, jest ograniczenie uwagi do zestawów rozmiarów d. Niech f (d, n) będzie maksymalną wartością t, gdy wszystkie zbiory we wszystkich rodzinach mają rozmiar d. Niech f * (d, n) będzie wartością maksymalną t, gdy dopuszczymy wielokrotności wielkości d. Zrozumienie f * (3, n) może być kluczowe.

Problem: Czy f * (3, n) zachowuje się jak 3n czy jak 4n?

Znane dolne i górne granice to odpowiednio 3n-2 i 4n-1. a ponieważ 3 jest początkiem sekwencji „d”, podczas gdy 4 jest początkiem sekwencji decyduje, czy prawda jest ważna 3, czy 4. Zobacz drugi wątek .$2^{d-1}$

Mój przyjaciel i ja postanowiliśmy wypróbować metodę brute-force i obliczyć pewne wartości dla małych wartości n i d . Jest to całkowicie niemożliwe bez zastosowania przycinania i mamy nadzieję, że znalezione przez nas sztuczki dadzą wgląd w resztę problemu. Do tej pory nie udało nam się znacząco obniżyć podwójnie wykładniczego czasu działania metody brutalnej siły (około 3 2 n jest naszym najlepszym dotychczasowym ograniczeniem), a zatem nie osiągnęliśmy jeszcze naszego pierwotnego celu jakimś przewidywaniem funkcji stojącej za nią $t$$n$$d$$3^{2^n}$$f$z pierwszych kilku wartości. Nie przeanalizowaliśmy również szczegółowo wszystkich komentarzy poprzednich wątków, więc niektóre z nich mogą być już znane - po prostu dobrze się bawiliśmy, robiąc nasz kod szybko i chcieliśmy gdzieś opublikować nasze wyniki, gdybym miał działające środowisko LaTeX, miałbym umieść to na ArXiV.

Kod (nie jest to dokładnie kod produkcyjny ...): http://pastebin.com/bSetW8JS . Wartości:

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$. Wynikający z tego algorytm programowania dynamicznego jest wtedy oczywisty. Liczba klas równoważności (wraz z czasem wymaganym przez powyższe dwie operacje) określa następnie czas działania oczywistego algorytmu programowania dynamicznego.

$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}$

${\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$ może przynieść bardziej drastyczne oszczędności.