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

52

Рассмотрим непересекающихся семейств подмножеств {1,2,…, n}, F 1 , F 2 , F t .tF1,F2,Ft

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

(*)

Для каждого , и каждый R F я и Т F к , существует S F J , который содержит R T .i<j<kRFiTFkSFjRT

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

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


Что известно

Самая известная верхняя граница является квазиполиномом .tnlogn+1

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

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

мотивация

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

Больше

Эта проблема является предметом 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, может быть важна. Смотрите вторую ветку .2d1

Гил Калай
источник
Гипотеза Хирша, Википедия
vzn
кажется, что эта гипотеза была бы очень проверяемой и, возможно, даже восприимчивой к вычислительному / эмпирическому / экспериментальному подходу с использованием метода Монте-Карло. кто-нибудь пробовал это?
2012 года
Является ли ваша новая причина вознаграждения «текущие ответы устаревшими и требуют пересмотра с учетом последних изменений», похоже, что вы имеете в виду что-то конкретное ...? в этой статье 2013 года « Последние достижения в области диаметра многогранников и симплициальных комплексов » Сантоса говорится, что гипотеза Гирша «опровергнута».
ВЗН
Уважаемый vzn, Это была своего рода шутка: любое утверждение о текущих ответах является правильным, если нет ответов.
Гил Калай

Ответы:

4

tnd32nfиз его первых нескольких значений. Мы также не изучили подробно все комментарии предыдущих потоков, поэтому некоторые из них, возможно, уже известны - мы в основном веселились, делая наш код быстрым, и хотели публиковать наши результаты где-нибудь, если бы у меня была работающая среда 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}

F1,...,FtF1,...,FtF1,...,Ft1F1,...,FtAFtF1,...,Ft1,{A}AF1,...,Ft1F1,...,Ft1,{A}FtF1,...,Ft

F1,...,FtF1,...,FtAF1,...,Ft . Во-вторых, если FF1,...,FtF1,...,FtF1,...,FtF1,...,Ft,Ft+1F1,...,Ft,Ft+1F1,...,Ft,Ft+1F1,...,Ft,Ft+1Ft+1F1,...,Ft, Последующий алгоритм динамического программирования становится очевидным. Число классов эквивалентности (вместе со временем, затрачиваемым двумя вышеупомянутыми операциями), дает ограничение времени работы очевидного алгоритма динамического программирования.

A{1,,n}AF1,...,Ft{kBFk:AB}={i,,j}1ijn(i,j)AF1,...,Ft{1,,n}

F1,...,Ft{1,,n}FtF1,...,Ft1BAF1,...,Ft1(i,j)j<t1ABCFtDFt+1BCD32n

Ft+11,,iF1={{1}},F2={{1,2}}Ft1FtF3 может привести к более радикальной экономии.

Алекс тен Бринк
источник