Os gráficos de vértices das bordas dos expansores polítopos (decentes)?

Esta questão é inspirada na conjectura polinomial de Hirsch (APS). Dado um polítopo facetado em , a lacuna espectral do seu gráfico de vértice de arestas (chamada ) é mais baixa delimitada por ? Observe que o gráfico de ciclo em vértices mostra que, mesmo para , o intervalo espectral pode ser tão pequeno quanto ; então o limite conjecturado - se verdadeiro - seria quase apertado.$n$$P$$\mathbb R^d$$G$$\Omega(1/\mathrm{poly}(n))$$n$$d=2$$O(1/\mathrm{poly}(n))$

Uma resposta sim implicaria a APS. De fato, isso também implicaria que programas lineares podem ser resolvidos de maneira eficiente com apenas uma caminhada aleatória nos vértices do politopo, e esse algoritmo não está prestando muita atenção à função objetivo! Isso parece bom demais para ser verdade.

Então, qual é o status desse problema: aberto (como PHC) ou falso? Se falso, existem contra-exemplos simples?

Nota : Acabei de perceber as complicações usuais envolvidas na definição de expansores: não precisa ser regular ou bipartido. Espero que esses dois problemas técnicos possam ser superados de maneira padrão e que, em particular, eles não façam minha pergunta trivial. (Por favor corrija-me se eu estiver errado!)$G$

Para polítopos 0/1 (todas as coordenadas do vértice são 0 ou 1), isso não é verdade. Há uma conjectura de Mihail e Vazirani de que a expansão da aresta do gráfico de um polítopo 0/1 é pelo menos um. Mais informações são descritas em um artigo de Volker Kaibel .

Eu devo observar duas coisas. (1) Para 0/1-polytopes, a conjectura de Hirsch é verdadeira . (2) Ao realizar uma caminhada aleatória nos vértices de um polítopo, precisamos cuidar de uma possível degeneração. Um vértice pode corresponder a muitas bases e, portanto, a caminhada pode permanecer no mesmo vértice se realizarmos uma caminhada aleatória sobre as bases. Se queremos realizar uma caminhada aleatória sobre os vértices, precisamos ter um procedimento que forneça um vértice adjacente aleatório.

Em geral, isso não é verdade: considere dois polipópios d duplos a cíclicos com n facetas cada e mescle-os ao longo de um vértice. (Esta é a operação dupla de colar dois polutops). O número de vértices será semelhante a e a diferença espectral será aproximadamente 1 sobre isso. (Você pode usar as arestas d para separar o gráfico em duas partes.$n^{[d/2]}$

Eu provei a separação 1 / poly (n) para os polytopes "de dupla a vizinhança". (Esta foi a minha primeira tentativa na conjectura polinomial de Hiresch ".)" O diâmetro dos gráficos dos pólipos convexos e da teoria dos vetores f "Geometria aplicada e matemática discreta, 387-411, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. , 4, Amer. Math. Soc., Providence, RI, 1991.