Estou interessado em exemplos de construções na teoria da complexidade que são melhores do que construções aleatórias.
O único exemplo dessa construção que eu sei é no campo dos códigos de correção de erros. Os códigos de geometria algébrica são melhores em alguns parâmetros do que os códigos aleatórios.
Pode-se facilmente construir tais exemplos artificiais. Estou interessado em exemplos como códigos de geometria algébrica, onde é fácil fazer uma construção aleatória e não é óbvio como fazer melhor.
Respostas:
Os gráficos de Ramanujan possuem o segundo valor próprio (com o grau do gráfico), enquanto os gráficos aleatórios atingem apenas whp De fato, em geral, temos que , com termo indo para com mantido constante (como o número de vértices ), portanto, em certo sentido, esses são ótimos.λ2≤2D−1√D D λ2≤2D−1√D+o(1) λ2≥2D−1√D−o(1) o(1) 0 D N→∞
fonte
Existe a construção de Behrend de um grande subconjunto de que não contém três elementos na progressão aritmética (abreviado 3AP-free). Um subconjunto aleatório de de tamanho, digamos , conterá muitas progressões aritméticas de comprimento 3, mas Behrend constrói um conjunto de tamanhos NAP free sem 3AP .{ 1 , … , N } N 0,9 N 1 - o ( 1 ){1,…,N} {1,…,N} N0.9 N1−o(1)
fonte
Pode não ser exatamente o que você está procurando, mas Jeff Lagarias e eu (posteriormente aprimorados por Mackey) criamos cubos de espaços dimensionais altos que são contra-exemplos da conjectura de Keller , ou seja, inclinações de dimensões com cubos de unidade onde não há dois os cubos se encontram em uma face dimensional completa ( ). Parece improvável que inclinações aleatórias dêem contra-exemplos.n - 1n n−1
fonte
Em geral, construções aleatórias e construções gananciosas atingem os mesmos limites (por exemplo, códigos de correção de erros). Certa vez, ouvi uma palestra de Lovasz, onde ele disse que escolhas gananciosas e aleatórias são essencialmente as mesmas. Portanto, qualquer construção que supere a construção gananciosa deve fornecer uma resposta para sua pergunta. Como um exemplo rápido, a construção que atinge a capacidade dos gráficos de Sperner é desse tipo. Como Peter Shor disse, existem muitos exemplos em combinações extremas.
fonte