Uma versão combinatória para a conjectura polinomial de Hirsch

Considere famílias separadas de subconjuntos de {1,2,…, n}, . $t$ ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$

Suponha que

(*)

Para cada e cada , e , há que contém . $i \lt j \lt k$ $R \in {\cal F}_i$ $T \in {\cal F}_k$ $S \in {\cal F}_j$ $R \cap T$

A questão básica é:

Quão grande não pode ser ???

O que é conhecido

O limite superior mais conhecido é quase polinomial . $t \le n^{\log n+1}$

O limite inferior mais conhecido é (até um fator logarítmico) quadrático.

Essa configuração abstrata foi retirada do artigo Diâmetro de Poliedros: Os Limites da Abstração, de Friedrich Eisenbrand, Nicolai Hähnle, Sasha Razborov e Thomas Rothvoss . O limite inferior quadrático, bem como uma prova do limite superior, podem ser encontrados em seus trabalhos.

Motivação

Todo limite superior será aplicado ao diâmetro dos gráficos de polítopos d-dimensionais com n facetas. Para ver isso associado a todos os vértices defina das facetas que o contêm. Em seguida, a partir de um vértice let ser os conjuntos correspondentes aos vértices do poliepítopo de distância a partir de . $v$ $S_v$ $w$ ${\cal F}_r$ $r+1$ $w$

Mais

Esse problema é o assunto do polímato3 . Mas pensei que seria útil apresentá-lo aqui e no MO , apesar de ser um problema em aberto. Se o projeto levar a subproblemas específicos, eu (ou outros) também tentamos perguntar a eles.

(Atualização; 5 de outubro :) Um problema específico de interesse especial é restringir a atenção a conjuntos de tamanho d. Seja f (d, n) o valor máximo de t quando todos os conjuntos em todas as famílias tiverem o tamanho d. Seja f * (d, n) o valor máximo de t quando permitimos vários conjuntos de tamanho d. Compreender f * (3, n) pode ser crucial.

Problema: f * (3, n) se comporta como 3n ou como 4n?

Os limites inferior e superior conhecidos são 3n-2 e 4n-1, respectivamente. e já que o 3 é o início da sequência 'd' enquanto o 4 é o início da sequência decidindo se a verdade é 3 ou 4 não é importante. Veja a segunda discussão . $2^{d-1}$

co.combinatorics cg.comp-geom open-problem linear-programming Gil Kalai
fonte

Conjectura de Hirsch, wikipedia

vzn

Parece que essa conjectura seria muito testável e talvez até suscetível a uma abordagem computacional / empírica / experimental usando o método de Monte Carlo. alguém tentou isso?

vzn

re sua nova razão de recompensa "as respostas atuais estão desatualizadas e exigem revisão devido às alterações recentes" parece que você tem algo em mente ...? Este artigo de 2013, Progressos Recentes sobre o Diâmetro dos Poliedros e Complexos Simpliciais de Santos, diz que a conjectura de Hirsch está "agora refutada".

vzn

Caro vzn, Isso foi uma espécie de piada: qualquer afirmação sobre as respostas atuais está correta, uma vez que não há respostas.

Gil Kalai

Respostas:

$t$ $n$ $d$ $3^{2^n}$ $f$ dos seus primeiros valores. Também não estudamos todos os comentários dos tópicos anteriores em detalhes; portanto, isso já pode ser conhecido - basicamente nos divertimos em tornar nosso código rápido e queríamos publicar nossos resultados em algum lugar, se eu tivesse um ambiente LaTeX em funcionamento, teria coloque isso no ArXiV.

Código (não é exatamente o código de produção ...): http://pastebin.com/bSetW8JS . Valores:

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$ . O algoritmo de programação dinâmica resultante é então óbvio. O número de classes de equivalência (junto com o tempo gasto pelas duas operações acima) fornece um limite ao tempo de execução do algoritmo de programação dinâmica óbvio.

$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$ pode resultar em economias mais drásticas.

Alex ten Brink
fonte