Спектральная теория графов: экспандеры и неравенство Чигера
Матричная алгебра способна извлекать колоссальные объемы информации не только из физических уравнений, но и из абстрактных топологических сетей (графов). Спектральная теория графов изучает свойства матриц смежности и лапласианов сетей для ответов на важнейшие вопросы топологии: насколько хорошо перемешивается информация в социальной сети? Насколько сложно разорвать интернет-соединение пополам? В центре этой теории находятся так называемые экспандеры — уникальный класс графов, которые сочетают в себе на первый взгляд несочетаемое: они имеют крайне мало ребер (очень разреженные, дешевые в постройке), но при этом обладают невероятно высокой алгебраической связностью, обеспечивая фантастическую скорость распространения сигнала.
Спектральная щель (Spectral Gap) Лапласиана
Для неориентированного графа матрица Лапласа L (разность диагональной матрицы степеней вершин и матрицы смежности) всегда является положительно полуопределенной. Ее наименьшее собственное значение всегда в точности равно нулю, а соответствующий ему собственный вектор состоит из одних единиц. Фундаментальный интерес представляет второе по величине наименьшее собственное значение (lambda_2), которое чешский математик Мирослав Фидлер назвал алгебраической связностью графа. Разность между первым и вторым собственным значением называется спектральной щелью (Spectral Gap). Чем больше спектральная щель, тем более монолитным и связным является граф. Если спектральная щель равна нулю, граф математически гарантированно распадается на несколько несвязных, изолированных кусков.
Изопериметрическое число и неравенство Чигера
Геометрическая связность графа оценивается через так называемую константу Чигера (или изопериметрическое число). Оно показывает, какую минимальную долю ребер нужно перерезать (разрушить), чтобы отделить от графа существенную часть вершин. Вычисление константы Чигера напрямую является NP-трудной комбинаторной задачей. Однако великое Неравенство Чигера строго связывает эту геометрическую константу с алгебраической спектральной щелью лапласиана двусторонними оценками (корневой зависимостью). Это потрясающий результат: мы можем абсолютно точно оценить, насколько граф уязвим к разрушению или хакерской атаке, просто вычислив второе собственное значение его матрицы (что современные компьютеры делают за доли секунды методом Ланцоша).
Случайные блуждания и лемма о перемешивании (Expander Mixing Lemma)
Высокая спектральная щель наделяет графы-экспандеры сверхъестественным свойством: случайные блуждания на таких графах (марковские цепи) сходятся к равномерному (стационарному) распределению с экспоненциальной скоростью. Знаменитая Лемма о перемешивании (Expander Mixing Lemma) гласит, что в экспандере количество ребер между любыми двумя достаточно большими подмножествами вершин почти в точности совпадает с ожидаемым количеством ребер в абсолютно случайном графе (где все связаны со всеми). Алгебраически это означает, что топология экспандера имитирует поведение случайной матрицы. Это свойство делает экспандеры идеальным математическим каркасом для создания генераторов псевдослучайных чисел, устойчивых блокчейн-протоколов и P2P сетей с гарантированным временем доставки пакетов.
Графы Рамануджана: теоретический предел Алона-Боппаны
Инженеры постоянно ищут графы с максимально возможной спектральной щелью при минимально возможном количестве ребер (степени вершин d). Теорема Алона-Боппаны устанавливает строгий физический предел: для очень больших графов спектральная щель (в терминах матрицы смежности) не может превосходить значения 2*sqrt(d-1). Графы, которые в точности достигают этого идеального математического предела, называются графами Рамануджана (в честь гениального индийского математика). Их построение долгое время оставалось нерешенной задачей, пока математики (включая Григория Маргулиса) не применили методы из продвинутой теории чисел (модулярные формы и алгебры кватернионов). Сегодня матрицы смежности графов Рамануджана считаются непревзойденным эталоном в проектировании сверхнадежных топологий серверов в облачных дата-центрах.
