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

52

Considere famílias separadas de subconjuntos de {1,2,…, n}, F 1 , F 2 , F t .tF1,F2,Ft

Suponha que

(*)

Para cada e cada R F i , e t F k , há S F j que contém R T .i<j<kRFiTFkSFjRT

A questão básica é:

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


O que é conhecido

O limite superior mais conhecido é quase polinomial .tnlogn+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 S v das facetas que o contêm. Em seguida, a partir de um vértice w let F r ser os conjuntos correspondentes aos vértices do poliepítopo de distância r + 1 a partir de W .vSvwFrr+1w

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 .2d1

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:

4

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

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

F1,...,FtF1,...,FtAF1,...,FtF1,...,FtF1,...,FtF1,...,FtF1,...,Ft,Ft+1F1,...,Ft,Ft+1F1,...,Ft,Ft+1F1,...,Ft,Ft+1Ft+1F1,...,Ft. 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,,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 pode resultar em economias mais drásticas.

Alex ten Brink
fonte