¿Son los gráficos de borde-vértice de los politopos (decentes) expansores?

21

Esta pregunta está inspirada en la conjetura polinómica de Hirsch (APS). Dado un politopo P de cara en R d , ¿el espacio espectral de su gráfico de borde-vértice (llamado G ) está limitado por Ω ( 1 / p o l y ( n ) ) ? Tenga en cuenta que el gráfico de ciclo en n vértices muestra que, incluso para d = 2 , la brecha espectral podría ser tan pequeña como O ( 1 / p o l y ( n ) )nPRdGΩ(1/poly(n))nd=2O(1/poly(n)); entonces el límite conjeturado, si es cierto, sería casi apretado.

Una respuesta afirmativa implicaría el APS. De hecho, también implicaría que los programas lineales se pueden resolver de manera eficiente con solo una caminata aleatoria en los vértices del politopo, ¡y este algoritmo ni siquiera está prestando mucha atención a la función objetivo! Esto parece demasiado bueno para ser verdad.

Entonces, ¿cuál es el estado de este problema: abierto (como PHC) o falso? Si es falso, ¿hay contraejemplos simples?

Nota : Me acabo de dar cuenta de las complicaciones habituales involucradas en la definición de expansores: no necesita ser regular o bipartito. Espero que estos dos problemas técnicos puedan superarse utilizando formas estándar y que, en particular, no hagan que mi pregunta sea trivial. (¡Por favor, corríjame si estoy equivocado!)G

Srivatsan Narayanan
fuente
¿Alguien puede explicar cómo se relaciona esta pregunta con los nuevos límites inferiores subexponenciales para las reglas pivotantes aleatorias para el algoritmo simplex? Oliver Friedmann, Thomas Dueholm Hansen y Uri Zwick. 2011. Límites inferiores subexponenciales para reglas pivotantes aleatorias para el algoritmo simplex. En Actas del 43º simposio anual de ACM sobre Teoría de la computación (STOC '11). ACM, Nueva York, NY, EE. UU., 283-292. DOI = 10.1145 / 1993636.1993675 doi.acm.org/10.1145/1993636.1993675
Tyson Williams

Respuestas:

10

Para politopos 0/1 (todas las coordenadas de vértice son 0 o 1), esto no se sabe que sea cierto. Hay una conjetura de Mihail y Vazirani de que la expansión del borde de la gráfica de un politopo 0/1 es al menos uno. Volker Kaibel describe más información en un documento .

Debo notar dos cosas. (1) Para 0/1-polytopes, la conjetura de Hirsch es verdadera . (2) Al realizar una caminata aleatoria sobre los vértices de un politopo, debemos cuidar la posible degeneración. Un vértice puede corresponder a muchas bases, por lo que la caminata puede permanecer en el mismo vértice si realizamos una caminata aleatoria sobre las bases. Si queremos realizar una caminata aleatoria sobre los vértices, necesitamos un procedimiento que proporcione un vértice adyacente aleatorio.

Yoshio Okamoto
fuente
9

n[d/2]

Probé la separación 1 / poli (n) para politopos de "doble a vecino". (Esta fue mi primera oportunidad en la conjetura polinómica de Hiresch "." "El diámetro de los gráficos de los politopos convexos y la teoría del vector f" Geometría aplicada y matemáticas discretas, 387–411, DIMACS Ser. Matemáticas discretas. Theoret. Comput. Sci. , 4, Amer. Math. Soc., Providence, RI, 1991.

Gil Kalai
fuente