Wersja kombinatoryczna dla wielomianowej hipotezy Hirscha

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

Przypuszczam, że

(*)

Dla każdego i każdy i , jest , który zawiera . $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 aspektów zawierających go. Następnie, zaczynając od wierzchołka niech będzie zestawami odpowiadającymi wierzchołkom polytopu odległości od . $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}$

— Gil Kalai
źródło

— Hipoteza

wygląda na to, że ta hipoteza byłaby bardzo testowalna, a może nawet podatna na podejście obliczeniowe / empiryczne / eksperymentalne przy użyciu metody Monte Carlo. czy ktoś tego próbował?

— vzn

ponownie twoja nowa przyczyna nagród „aktualne odpowiedzi są nieaktualne i wymagają rewizji z uwagi na ostatnie zmiany” wygląda na to, że masz na myśli coś konkretnego…? w artykule z 2013 r. „ Ostatnie postępy w zakresie średnic wielościanów i kompleksów prostych” autorstwa Santosa mówi się, że hipoteza Hirscha została „obalona”.

— vzn

Drogi Vzn, To był rodzaj żartu: każde stwierdzenie na temat aktualnych odpowiedzi jest poprawne, biorąc pod uwagę, że nie ma odpowiedzi.

— Gil Kalai

Mój przyjaciel i ja postanowiliśmy wypróbować metodę brute-force i obliczyć pewne wartości dla małych wartości i . 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 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.

— Alex ten Brink
źródło