Являются ли реберно-вершинные графы многогранников (приличных) экспандерами?

21

Этот вопрос вдохновлен полиномиальной гипотезой Хирша (PHC). Учитывая гранный многогранник в , ограничена ли спектральная щель графа вершин и вершин (назовем его ) снизу ? Обратите внимание, что граф циклов на вершинах показывает, что даже при спектральная щель может быть такой маленькой, как ; так что предполагаемая граница - если это правда - будет почти жесткой.NпрdграммΩ(1/поLY(N))Ndзнак равно2О(1/поLY(N))

Ответ «да» подразумевает ПМСП. Фактически, это также подразумевало бы, что линейные программы могут быть эффективно решены простым случайным блужданием по многогранным вершинам, и этот алгоритм даже не уделяет большого внимания целевой функции! Это кажется слишком хорошим, чтобы быть правдой.

Итак, каков статус этой проблемы: открытая (например, PHC) или ложная? Если ложь, есть ли простые контрпримеры?

Примечание : я только что понял обычные сложности, связанные с определением расширителей: не обязательно должен быть регулярным или двудольным. Я надеюсь, что обе эти технические проблемы могут быть преодолены стандартными способами, и что, в частности, они не делают мой вопрос тривиальным. (Пожалуйста, поправьте меня, если я ошибаюсь!)грамм

Шриватсан Нараянан
источник
Может кто-нибудь объяснить, как этот вопрос связан с новыми субэкспоненциальными нижними оценками для рандомизированных правил поворота для симплексного алгоритма? Оливер Фридман, Томас Дуэхольм, Хансен и Ури Цвик. 2011. Субэкспоненциальные нижние оценки для рандомизированных правил поворота для симплексного алгоритма. В материалах 43-го ежегодного симпозиума ACM по теории вычислений (STOC '11). ACM, Нью-Йорк, Нью-Йорк, США, 283-292. DOI = 10.1145 / 1993636.1993675 doi.acm.org/10.1145/1993636.1993675
Тайсон Уильямс

Ответы:

10

Для 0/1-многогранников (все координаты вершин 0 или 1), это не известно, чтобы быть правдой. Михаил и Вазирани выдвигают гипотезу о том, что разложение по краям графа 0/1-многогранника является хотя бы одним. Более подробная информация описана в документе Volker Kaibel .

Я должен отметить две вещи. (1) Для 0/1-многогранников гипотеза Гирша верна . (2) При выполнении случайного блуждания по вершинам многогранника нам нужно позаботиться о возможном вырождении. Одна вершина может соответствовать большому количеству базисов, поэтому обход может остаться в одной и той же вершине, если мы выполним случайный обход базисов. Если мы хотим выполнить случайное блуждание по вершинам, нам нужна процедура, которая дает случайную смежную вершину.

Ёсио Окамото
источник
9

В общем случае это неверно: рассмотрим два двойных-циклических d-многогранника с n гранями в каждой и объединяем их вдоль вершины. (Это двойная операция по склеиванию двух столешниц). Количество вершин будет равно и спектральный разрыв будет примерно равен 1. (Вы можете использовать d ребер, чтобы разделить график на две части.N[d/2]

Я доказал 1 / poly (n) разделение для «многогранных» многогранников. (Это был мой первый выстрел в полиномиальной гипотезе Хирша ".)" Диаметр графов выпуклых многогранников и теория f-вектора "Прикладная геометрия и дискретная математика, 387–411, DIMACS Сер. Дискретная математика. Теорет. Comput. Sci. 4, Amer. Math. Soc., Providence, RI, 1991.

Гил Калай
источник