Расширяющий график
-
Определение и свойства расширяющих графов
- Расширяющие графы — это графы с ограниченной степенью, которые расширяются равномерно по всем подмножествам.
- Они обладают важными свойствами, такими как асимптотическая надежность и оптимальность для некоторых задач.
-
История и мотивация
- Расширяющие графы были впервые изучены Рамануджаном в 1930-х годах.
- Они нашли применение в различных областях, включая криптографию и теорию сложности вычислений.
-
Основные результаты
- Алон и Ройхман доказали существование ε-расширителей для любого ε > 0.
- Билу и Линиал предложили улучшенную границу для двудольных расширяющих графов.
- Холл, Пудер и Савин обобщили метод чередующихся многочленов для r-лифтов.
-
Области применения и полезные свойства
- Расширяющие графы используются в создании надежных сетей и в разработке алгоритмов.
- Они применяются в криптографии для построения хэш-функций и в теории сложности вычислений.
-
Лемма о смешивании расширителя
- Утверждает, что число ребер между двумя подмножествами в (n, d, λ)-графе приблизительно равно ожидаемому числу в случайном d-регулярном графе.
-
Оценка Чернова и лемма о выборке обхода расширителя
- Лемма о выборке обхода позволяет использовать меньше случайных битов при выборке из обхода на расширяющем графе.
-
Сортировочная сеть AKS и приближенное сокращение вдвое
- Расширяющие графы играют ключевую роль в сортировочной сети AKS, обеспечивая глубину O(log n).
- Они используются для построения ε-половинок ограниченной глубины в сортировочной сети.
- Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.