Sind Edge-Vertex-Graphen von Polytopen (anständige) Expander?

21

Diese Frage ist von der Polynom-Hirsch-Vermutung (PHC) inspiriert. Ist bei gegebenem Facetten-Polytop in die spektrale Lücke seines Kantenscheitelpunkt-Graphen (nenne es ) niedriger begrenzt durch ? Man beachte, dass der Zyklusgraph auf Eckpunkten zeigt, dass die spektrale Lücke selbst für so klein sein könnte wie ; also wäre die vermutete Grenze - wenn sie wahr wäre - fast eng.P R d G Ω ( 1 / p o l y ( n ) ) , n d = 2 O ( 1 / p o l y ( n ) )nPRdGΩ(1/poly(n))nd=2O(1/poly(n))

Eine Ja-Antwort würde die PHC implizieren. Tatsächlich würde dies auch bedeuten, dass lineare Programme effizient durch einen zufälligen Durchlauf auf den Polytop-Eckpunkten gelöst werden können, und dieser Algorithmus widmet der objektiven Funktion nicht einmal viel Aufmerksamkeit! Das scheint zu schön, um wahr zu sein.

Wie ist der Status dieses Problems: offen (wie PHC) oder falsch? Wenn falsch, gibt es einfache Gegenbeispiele?

Hinweis : Ich habe gerade die üblichen Komplikationen bei der Definition von Expandern erkannt: muss nicht regelmäßig oder zweiteilig sein. Ich hoffe, dass diese beiden technischen Probleme mit Standardmethoden gelöst werden können, und dass sie insbesondere meine Frage nicht trivial machen. (Bitte korrigieren Sie mich, wenn ich falsch liege!)G

co.combinatorics linear-programming expanders Srivatsan Narayanan
quelle
Kann jemand erklären, wie diese Frage mit den neuen subexponentiellen Untergrenzen für randomisierte Schwenkregeln für den Simplex-Algorithmus zusammenhängt? Oliver Friedmann, Thomas Dueholm Hansen und Uri Zwick. 2011. Subexponentielle Untergrenzen für randomisierte Pivot-Regeln für den Simplex-Algorithmus. In Proceedings des 43. jährlichen ACM-Symposiums zur Theorie des Rechnens (STOC '11). ACM, New York, NY, USA, 283–292. DOI = 10.1145 / 1993636.1993675 doi.acm.org/10.1145/1993636.1993675
Tyson Williams

Antworten:

10

Für 0/1-Polytope (alle Scheitelpunktkoordinaten sind 0 oder 1) ist dies nicht als wahr bekannt. Es gibt eine Vermutung von Mihail und Vazirani, dass die Kantenexpansion des Graphen eines 0/1-Polytops mindestens eins beträgt. Weitere Informationen sind in einem Artikel von Volker Kaibel beschrieben .

Ich sollte zwei Dinge beachten. (1) Für 0/1-Polytope gilt die Hirsch-Vermutung . (2) Wenn wir einen zufälligen Spaziergang auf den Eckpunkten eines Polytops durchführen, müssen wir auf mögliche Entartungen achten. Ein Scheitelpunkt kann vielen Basen entsprechen, und so kann der Lauf auf demselben Scheitelpunkt bleiben, wenn wir einen zufälligen Lauf über die Basen ausführen. Wenn wir einen zufälligen Spaziergang über die Scheitelpunkte durchführen möchten, benötigen wir eine Prozedur, die einen zufälligen benachbarten Scheitelpunkt ergibt.

Yoshio Okamoto
quelle
9

n[d/2]

Ich habe eine 1 / Poly (n) -Trennung für "dual-to-neighbourly" -Polytope nachgewiesen. (Dies war meine erste Aufnahme mit der Polynom-Hiresch-Vermutung.) "Der Durchmesser von Graphen konvexer Polytope und der f-Vektortheorie" Angewandte Geometrie und diskrete Mathematik, 387–411, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. , 4, Amer. Math. Soc., Providence, RI, 1991.

Gil Kalai
quelle