Статьи в кредит на спектральное разбиение графиков

Если неориентированный -регулярный граф и представляет собой подмножество вершин мощности , вызови расширение края в г. количестваd S ≤ | V | / 2 $G=(V,E)$$d$$S$$\leq |V|/2$$S$

$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$

Где представляет собой число ребер с одной конечной точкой в и одной конечной точке в . Тогда задача расширения края состоит в том, чтобы найти множество с которое минимизирует . Назовите разложением оптимального множества.A $Edges(A,B)$$A$$B$| S | ≤ | V | / 2 ϕ ( S ) ϕ ( G $S$$|S|\leq |V|/2$$\phi(S)$$\phi(G)$

Спектральная Разметка Алгоритм для задачи пограничного расширения работает путем нахождения собственный вектор из второго по величине собственного , матрицы смежности , а затем с учетом всех `` пороговыми наборов «» вида по всем порогам . Если мы допустим, чтобы было вторым по величине собственным значением матрицы , то анализ алгоритма спектрального разделения показывает, что наилучший пороговый набор найденный алгоритмом, удовлетворяетA G S { v : x ( v ) ≤ t } t λ 2 $x$$A$$G$$S$$\{ v : x(v) \leq t \}$$t$$\lambda_2$SS$\frac 1d \cdot A$$S_{SP}$

$\phi(S_{SP}) \leq 2\sqrt {\phi(G)}$

Что следует из неравенства Чигера

$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

а также

$1-\lambda_2 \leq 2 \phi(G)$

Какова первая статья, чтобы сделать такое требование? Какие документы в кредит на идеи? Вот что я получил:

• Н. Алон и В. Д. Мильман. , изопериметрические неравенства для графов и суперконцентраторы, Журнал комбинаторной теории, серия B, 1985, 38 (1): 73-88 $\lambda_1$

  Докажите результат в духе «простого» неравенства Чигера , но для расширения вершин вместо расширения ребер. Признать, что связь между разложением ребер и собственными значениями является дискретной версией проблемы, изученной Чигером в $1-\lambda_2 \leq 2\phi(G)$

  Дж. Чигер. Нижняя оценка для наименьшего собственного значения лапласиана. Проблемы в анализе, 1970.

• Н. Алон. Собственные значения и расширители. Combinatorica. 6 (2): 83-96, 1986.

  Получается результат в духе сложного неравенства Чигера но для расширения вершин вместо расширения ребер. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

• А. Синклер, М. Джеррум. Приближенный подсчет, равномерная генерация и быстрое перемешивание цепей Маркова. Информация и вычисления 82: 93-133, 1989 (версия конференции 1987)

  Докажите неравенства Чигера, как указано выше. (В их работе исследуется _кондуктивность_ обратимых во времени цепей Маркова, что в регулярных графах оказывается равным _размерному расширению_.) Они приписывают работу Алона, Мильмана и Алона за методы. Они также отдают должное Aldous за связанную границу между временем смешивания и расширением ребер в регулярных графах.

• М Михаил. Кондуктивность и сходимость цепей Маркова - комбинаторная трактовка экспандеров. ФОКС 1989, стр. 526-531

  Хотя основной смысл статьи заключается в том, что ее методы применяются к необратимым по времени цепям Маркова, когда он применяется к регулярным неориентированным графам, он имеет преимущество перед предыдущей работой: он показывает, что если запустить алгоритм спектрального разбиения с произвольным вектор, все еще получается неравенство где - фактор Рэлея вектора. Аргументы Алона, Мильмана, Синклера и Джеррума требуют фактического собственного вектора. Это относится к быстрым алгоритмам спектрального разделения, которые используют приближенные собственные векторы. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda')}$$\lambda'$

Когда впервые признается алгоритмическая значимость приведенных выше результатов в качестве алгоритмов разбиения графов? Вышеуказанные документы не имеют такого обсуждения.

Похоже, что первой статьей, вводящей этот набор идей (использующий алгебраический инвариант , второе наименьшее собственное значение лапласиана графа, чтобы связать различные свойства графа) с теорией графов, была "алгебраическая связность графов" Фидлера в чехословацкой математике Journal. Он появился в 1973 году, примерно в то же время, что и статья Чигера (1970), в которой рассматривались многообразия. Я не уверен, кто первым наблюдал параллель между графами и многообразиями в этом отношении. иногда называют числом Фидлера.$\lambda_2$$\lambda_2$

Интересно, что в конце статьи Фидлера есть замечание, указывающее на независимый технический отчет Андерсона и Морли под названием «Собственные значения лапласиана на графике 1971 года», который, по-видимому, имел аналогичные идеи. Однако именно эта работа Андерсона и Морли с таким же названием появилась в линейной и многолинейной алгебре только в 1985 году.

Некоторые дополнительные ссылки, которые я помню об этой эпохе:

1) Diaconis и Stroock, Геометрические оценки для собственных значений цепей Маркова, Анналы прикладной вероятности, 1991; но я не забываю получить препринт в 1990 году. Этот документ, в свою очередь, относится к

2) Додзюк, Разностные уравнения, изопериметрическое неравенство и кратковременность некоторых случайных блужданий, Труды Американского математического общества, 1984.

Кроме того, важной «алгоритмической компаньонкой» для Синклера и Джеррума в то время была

3) Дайер Фриз Каннан, Случайный алгоритм полиномиального времени для аппроксимации объема выпуклых тел, STOC 89. Конечно, результаты здесь были построены на основе SJ.