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