Constante na conjectura de Komlos

8

nv1,,vnRNvi221i{1,,n}cRn,Nϵ{1,+1}n

i=1nϵivi<c.
c

O melhor limite superior é .c=O(logn)

Existe um conjunto de exemplos para para qualquer que a conjectura de Komlos falha?c=1+δδ>0

T ....
fonte
Uma maneira fácil de ver que deve ser pelo menos é considerar os vetores , e . Não tenho certeza se isso merece uma resposta. c3212(1,1,1,1)12(1,1,1,1)12(1,1,1,1)
Klaus Draeger
@KlausDraeger Sim, se você também puder dizer a lógica por trás do exemplo. Eu posso ver como você pode ter construído isso.
T ....

Respostas:

8

Uma maneira simples de obter um limite inferior é considerar pares de vetores . Antes de tudo, faz sentido focar nos pares de vetores unitários para os quais todas as combinações lineares - são tão longas quanto possível (observe que esse é apenas um caso especial interessante, não estou dizendo que é opotimal de qualquer maneira). Isso é obtido quando são ortogonais e, verificando as possíveis rotações, descobrimos que mostra que deve ser pelo menos .c2u,vR{1,1}u,vu=12(1,1),v=12(1,1)c2

Este exemplo pode ser generalizado para os conjuntos de vetores , onde o coeficiente de é se o dígito binário em for e caso contrário.Vk={2k2vi,k | 0ik}R2kj(vi,k)jvi,k1ithj01

A -norm de qualquer combinação linear dos vetores em é , que atinge seu máximo em , com o conjunto de vetores{1,1}Vk(k+1)2k232k=2

V2={12(1,1,1,1),12(1,1,1,1),12(1,1,1,1)} .

Pode haver limites inferiores melhores, mas isso é um começo.

Klaus Draeger
fonte
Parece-me que seu exemplo já é muito bom. poderia ser muito mais do que isso? c
T ....
4

Tomando o como as colunas desta matriz mostra (eu encontrei e verifiquei a matriz por experimento em computador):vic461.633

M=16(111111111111111111111111111111111111)
Chris Jones
fonte
-3

Não há melhor limite inferior, porque c é um limite superior. O limite superior mais conhecido é , conforme comprovado por Banaszczyk em 1998.O(logn)

Yossi Lonke
fonte
7
Não há melhor limite inferior - não entendo o que você quer dizer com isso. Interpreto a pergunta como "qual é o maior para o qual se sabe que a declaração de conjectura é falsa?" o que parece bem definido. c
usul
2
Turbo: Ok, então você corrigiu sua formatação, mas ainda falta precisão matemática, porque, pelo que sabemos, a conjectura de Komlos pode ser falsa, de modo que pode não haver "o menor valor" para os cs, porque o conjunto é não delimitado abaixo. Agora, se sua pergunta é algo como "Supondo que a conjectura de Komlos seja verdadeira, qual é o menor dos c's"? a resposta mais conhecida atualmente é "não sei". usul: Essa é uma boa interpretação. Não acho que alguém tenha estudado isso com muita profundidade. Em alguns experimentos ad-hoc que eu fiz, eu descobri que existem contra-exemplos para c = 2.
Yossi Lonke
@Turbo Por que você não exclui toda a postagem?
Yossi Lonke