Czy wykresy krawędzi-wierzchołków polytopów (przyzwoitych) ekspanderów?

To pytanie jest inspirowane wielomianową hipotezą Hirscha (PHC). Biorąc pod uwagę -facet polytop w , czy szczelina widmowa jego wykresu wierzchołek-krawędź (nazwij to ) jest niższa ograniczona przez ? Zauważ, że wykres cyklu wierzchołków pokazuje, że nawet dla szczelina widmowa może być tak mała jak ; więc przypuszczalne związanie - jeśli to prawda - byłoby prawie ciasne.$n$$P$$\mathbb R^d$$G$$\Omega(1/\mathrm{poly}(n))$$n$$d=2$$O(1/\mathrm{poly}(n))$

Odpowiedź tak oznaczałaby PHC. W rzeczywistości oznaczałoby to również, że programy liniowe można skutecznie rozwiązać tylko przypadkowym spacerem po wierzchołkach polytopów, a ten algorytm nawet nie zwraca dużej uwagi na funkcję celu! To wydaje się zbyt piękne, aby mogło być prawdziwe.

Więc jaki jest status tego problemu: otwarty (jak PHC), czy fałszywy? Jeśli fałsz, czy istnieją proste kontrprzykłady?

Uwaga : Właśnie zdałem sobie sprawę z typowych komplikacji związanych z definiowaniem ekspanderów: nie musi być regularny ani dwustronny. Mam nadzieję, że oba te problemy techniczne można rozwiązać za pomocą standardowych metod, a w szczególności nie powodują, że moje pytanie jest trywialne. (Proszę, popraw mnie jeśli się mylę!)$G$

W przypadku 0/1 polytopów (wszystkie współrzędne wierzchołków mają wartość 0 lub 1), nie jest to prawdą. Istnieje przypuszczenie Mihaila i Vazirani, że ekspansja krawędzi wykresu politopla 0/1 wynosi co najmniej jeden. Więcej informacji opisano w artykule Volkera Kaibela .

Powinienem zwrócić uwagę na dwie rzeczy. (1) W przypadku 0/1-polytopów hipoteza Hirscha jest prawdziwa . (2) Wykonując losowy spacer po wierzchołkach polytopa, musimy zadbać o możliwą degenerację. Jeden wierzchołek może odpowiadać wielu bazom, więc spacer może pozostać na tym samym wierzchołku, jeśli wykonamy losowy spacer nad bazami. Jeśli chcemy wykonać losowy spacer po wierzchołkach, musimy mieć procedurę, która da losowy sąsiadujący wierzchołek.

Zasadniczo nie jest to prawdą: rozważ dwa podwójne-cykliczne d-polytopy o n ściankach każdy i połącz je wzdłuż wierzchołka. (Jest to podwójna operacja klejenia dwóch polutopsów). Liczba wierzchołków będzie podobna do a odstęp widmowy będzie z tego mniej więcej równy 1. (Możesz użyć krawędzi d, aby podzielić wykres na dwie części.$n^{[d/2]}$

Udowodniłem separację 1 / poli (n) dla polytopów „podwójnych do sąsiadujących”. (To był mój pierwszy rzut na wielomianową hipotezę Hirescha ”.)„ Średnica wykresów wypukłych polytopów i teorii wektora f ”Zastosowana geometria i matematyka dyskretna, 387–411, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. , 4, Amer. Math. Soc., Providence, RI, 1991.