Лемма о перемешивании расширителей - Expander mixing lemma - Wikipedia

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

-Регулярные графики расширителя

Определить -граф быть -регулярный график на вершины такие, что все собственные значения его матрицы смежности кроме одного иметь величину не больше В -регулярность графика гарантирует, что его собственное значение наибольшей величины будет Фактически, вектор всех единиц является собственным вектором с собственным значением , а собственные векторы матрицы смежности никогда не будет превышать максимальную степень по величине.

Если мы исправим и тогда -графы образуют семейство графики расширителей с постоянным спектральный промежуток.

Заявление

Позволять быть -граф. Для любых двух подмножеств , позволять быть количеством ребер между S и Т (считая ребра, содержащиеся в пересечении S и Т дважды). потом

Более плотная связь

Фактически мы можем показать, что

используя аналогичные методы.[1]

Бирегулярные графы

За бирегулярные графы, имеем следующий вариант.[2]

Позволять - двудольный граф такой, что каждая вершина в примыкает к вершины и каждая вершина в примыкает к вершины . Позволять с и . Позволять . потом

Обратите внимание, что - наибольшая абсолютная величина собственных значений .

Доказательства

Доказательство первого утверждения

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

Позволять быть матрица всех единиц. Обратите внимание, что является собственным вектором с собственным значением и друг друга , будучи перпендикулярным , является собственным вектором с собственным значением 0. Для подмножества вершин , позволять быть вектор-столбцом с координата равна 1, если и 0 в противном случае. Потом,

.

Позволять . Потому что и разделяют собственные векторы, собственные значения находятся . Посредством Неравенство Коши-Шварца у нас есть это . Кроме того, поскольку самосопряженный, мы можем написать

.

Отсюда следует, что и .

Доказательство более тесной связи

Чтобы показать более точную оценку выше, мы вместо этого рассматриваем векторы и , которые оба перпендикулярны . Мы можем расширить

потому что два других члена разложения равны нулю. Первый член равен , поэтому мы находим, что

Мы можем связать правую часть с помощью используя те же методы, что и в предыдущем доказательстве.

Приложения

Лемму о смешивании расширителей можно использовать для оценки сверху размера независимого набора в графе. В частности, размер независимого множества в -граф не более Это доказывается положением в заявлении выше и используя тот факт, что

Дополнительным следствием является то, что если является -граф, то его хроматическое число по крайней мере Это потому, что в допустимой раскраске графа набор вершин данного цвета является независимым набором. По вышеуказанному факту, каждый независимый набор имеет размер не более так по крайней мере такие наборы нужны, чтобы покрыть все вершины.

Второе применение леммы о смешивании расширителей - обеспечить верхнюю границу максимально возможного размера независимого набора в графе полярности. Учитывая конечное проективная плоскость с полярность граф полярности - это граф, вершинами которого являются точки a , а вершины и связаны тогда и только тогда, когда В частности, если есть заказ то лемма о смешивании расширителей может показать, что независимое множество в графе полярностей может иметь размер не более оценка, доказанная Хобартом и Уиллифордом.

Converse

Билу и Linial показал[3] верно и обратное: если -регулярный график удовлетворяет тому, что для любых двух подмножеств с у нас есть

то его второе по величине (по модулю) собственное значение ограничено .

Обобщение на гиперграфы

Фридман и Виджерсон доказали следующее обобщение леммы о перемешивании на гиперграфы.

Позволять быть -равномерный гиперграф, т.е. гиперграф, в котором каждое «ребро» является набором вершины. Для любого выбора подмножеств вершин,

Примечания

  1. ^ Вадхан, Салил (весна 2009 г.). «Расширительные графики» (PDF). Гарвардский университет. Получено 1 декабря, 2019.
  2. ^ См. Теорему 5.1 в книге Хемерса «Чередование собственных значений и графиков».
  3. ^ Лемма о перемешивании расширителей, обратная

Рекомендации

  • Alon, N .; Чанг, Ф. Р. К. (1988), "Явное построение терпимых сетей линейного размера", Дискретная математика, 72 (1–3): 15–19, Дои:10.1016 / 0012-365X (88) 90189-6.