Этот вопрос вдохновлен полиномиальной гипотезой Хирша (PHC). Учитывая гранный многогранник в , ограничена ли спектральная щель графа вершин и вершин (назовем его ) снизу ? Обратите внимание, что граф циклов на вершинах показывает, что даже при спектральная щель может быть такой маленькой, как ; так что предполагаемая граница - если это правда - будет почти жесткой.
Ответ «да» подразумевает ПМСП. Фактически, это также подразумевало бы, что линейные программы могут быть эффективно решены простым случайным блужданием по многогранным вершинам, и этот алгоритм даже не уделяет большого внимания целевой функции! Это кажется слишком хорошим, чтобы быть правдой.
Итак, каков статус этой проблемы: открытая (например, PHC) или ложная? Если ложь, есть ли простые контрпримеры?
Примечание : я только что понял обычные сложности, связанные с определением расширителей: не обязательно должен быть регулярным или двудольным. Я надеюсь, что обе эти технические проблемы могут быть преодолены стандартными способами, и что, в частности, они не делают мой вопрос тривиальным. (Пожалуйста, поправьте меня, если я ошибаюсь!)
источник
Ответы:
Для 0/1-многогранников (все координаты вершин 0 или 1), это не известно, чтобы быть правдой. Михаил и Вазирани выдвигают гипотезу о том, что разложение по краям графа 0/1-многогранника является хотя бы одним. Более подробная информация описана в документе Volker Kaibel .
Я должен отметить две вещи. (1) Для 0/1-многогранников гипотеза Гирша верна . (2) При выполнении случайного блуждания по вершинам многогранника нам нужно позаботиться о возможном вырождении. Одна вершина может соответствовать большому количеству базисов, поэтому обход может остаться в одной и той же вершине, если мы выполним случайный обход базисов. Если мы хотим выполнить случайное блуждание по вершинам, нам нужна процедура, которая дает случайную смежную вершину.
источник
В общем случае это неверно: рассмотрим два двойных-циклических d-многогранника с n гранями в каждой и объединяем их вдоль вершины. (Это двойная операция по склеиванию двух столешниц). Количество вершин будет равно и спектральный разрыв будет примерно равен 1. (Вы можете использовать d ребер, чтобы разделить график на две части.N[ д/ 2]
Я доказал 1 / poly (n) разделение для «многогранных» многогранников. (Это был мой первый выстрел в полиномиальной гипотезе Хирша ".)" Диаметр графов выпуклых многогранников и теория f-вектора "Прикладная геометрия и дискретная математика, 387–411, DIMACS Сер. Дискретная математика. Теорет. Comput. Sci. 4, Amer. Math. Soc., Providence, RI, 1991.
источник