График Рамануджана
-
Определение и свойства графов Рамануджана
- Графы Рамануджана — это графы с фиксированным числом вершин и степенью, равной простому числу плюс единица.
- Они обладают уникальными свойствами, включая наличие множества собственных значений, которые являются квадратными корнями из простых чисел.
-
История и развитие
- Графы Рамануджана названы в честь индийского математика Рамануджана, который впервые описал их в 1913 году.
- В 1960-х годах Люботцки, Филлипс и Сарнак расширили определение графов Рамануджана, включив в них графы с произвольным числом вершин.
- Моргенштерн расширил конструкцию Люботцки, Филлипса и Сарнака, сохранив свойство Рамануджана при главных степенях.
- Арнольд Пайзер доказал, что графы суперсингулярной изогении также являются графами Рамануджана.
-
Вероятностные примеры и расширения
- Адам Маркус, Дэниел Шпильман и Нихил Шривастава доказали существование бесконечно многих двудольных графов Рамануджана для любой степени.
- Майкл Б. Коэн показал, как строить эти графики за полиномиальное время.
- Холл, Пудер и Савин распространили результаты на r-лифты.
- Проблема существования бесконечно многих d-регулярных (не двудольных) графов Рамануджана остается открытой для d=7.
-
Графики Рамануджана как расширяющие графы
- Графы Рамануджана являются наилучшими расширяющими графами с асимптотически четкой границей Алона-Боппаны.
- Лемма о смешивании расширителя обеспечивает отличные оценки однородности распределения ребер и логарифмического времени смешивания случайных блужданий.
-
Применение графов Рамануджана
- Графы Рамануджана находят применение в информатике, теории чисел и теории групп.
- Они особенно полезны в приложениях, где требуются расширяющие графы.
- Примеры приложений включают быстрые решатели для линейных систем Лапласа и построение расширяющих кодов для исправления ошибок.