Комбинаторная версия полиномиальной гипотезы Гирша

Рассмотрим непересекающихся семейств подмножеств {1,2,…, n}, F 1 , F 2 , … F t .$t$${\cal F}_1,{\cal F_2},\dots {\cal F_t}$

Предположим, что

(*)

Для каждого , и каждый R ∈ F я и Т ∈ F к , существует S ∈ F J , который содержит 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$

Основной вопрос:

Насколько большой не может быть ???

Что известно

Самая известная верхняя граница является квазиполиномом .$t \le n^{\log n+1}$

Самая известная нижняя граница является (с точностью до логарифмического множителя) квадратичной.

Эта абстрактная установка взята из статьи « Диаметр многогранников: границы абстракции» Фридриха Эйзенбранда, Николая Ханле, Саши Разборова и Томаса Ротвосса . Квадратичная нижняя оценка, а также доказательство верхней границы можно найти в их статье.

мотивация

Каждая верхняя граница будет применяться к диаметру графиков d-мерных многогранников с n гранями. Чтобы увидеть это, свяжите с каждой вершиной множество S v фасет, содержащих ее. Тогда, начиная с вершины w, пусть F r - множества, соответствующие вершинам многогранника расстояния r + 1 от w .$v$$S_v$$w$${\cal F}_r$$r+1$$w$

Больше

Эта проблема является предметом polymath3 . Но я подумал, что было бы полезно представить это здесь и на МО, несмотря на то, что это открытая проблема. Если проект приведет к определенным подзадачам, я (или другие) также могу попытаться задать их.

(Обновление; 5 октября :) Одна особая проблема, которая представляет особый интерес, состоит в ограничении внимания на наборы размера d. Пусть f (d, n) будет максимальным значением t, когда все множества во всех семействах имеют размер d. Пусть f * (d, n) будет максимальным значением t, когда мы разрешаем мультимножества размера d. Понимание f * (3, n) может иметь решающее значение.

Проблема: f * (3, n) ведет себя как 3n или как 4n?

Известные нижняя и верхняя границы составляют 3n-2 и 4n-1 соответственно. и так как 3 - начало последовательности 'd', а 4 - начало последовательности, решает, будет ли истина 3 или 4, может быть важна. Смотрите вторую ветку .$2^{d-1}$

$t$$n$$d$$3^{2^n}$$f$из его первых нескольких значений. Мы также не изучили подробно все комментарии предыдущих потоков, поэтому некоторые из них, возможно, уже известны - мы в основном веселились, делая наш код быстрым, и хотели публиковать наши результаты где-нибудь, если бы у меня была работающая среда LaTeX, я бы положи это на ArXiV.

Код (это не совсем рабочий код ...): http://pastebin.com/bSetW8JS . Ценности:

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$, Последующий алгоритм динамического программирования становится очевидным. Число классов эквивалентности (вместе со временем, затрачиваемым двумя вышеупомянутыми операциями), дает ограничение времени работы очевидного алгоритма динамического программирования.

$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$ может привести к более радикальной экономии.