Введение

Разреженный граф с высокой связностью

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

Определения

Интуитивно, граф-экспандер – это конечный, ненаправленный мультиграф, в котором любое подмножество вершин, которое не является "слишком большим", имеет "большую" границу. Различные формализации этих понятий приводят к различным определениям экспандеров: экспандеров по ребрам, экспандеров по вершинам и спектральных экспандеров, как определено ниже. Разрывная (несвязная) графа не является экспандером, поскольку граница связного компонента пуста. Любая связная графа является экспандером; однако, разные связные графы имеют разные параметры экспансии. Полный граф обладает наилучшими свойствами экспансии, но имеет максимально возможную степень. Неформально, граф является хорошим экспандером, если он имеет небольшую степень и высокие параметры экспансии.

Связи между различными свойствами расширения

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

Строительство

Существует четыре основных стратегии явного построения семейств расширяющих графов. Первая стратегия — алгебраическая и теоретико-групповая, вторая — аналитическая и использующая аддитивную комбинаторику, третья — комбинаторная, использующая зигзаг и связанные с ним произведения графов, а четвертая — основана на поднятиях. Нога Алон показал, что определенные графы, построенные на основе конечных геометрий, являются наиболее разреженными примерами сильно расширяющихся графов.

Случайные конструкции

Существует множество результатов, показывающих существование графов с хорошими свойствами расширения с помощью вероятностных аргументов. Фактически, существование экспандеров было впервые доказано Пинскером, который показал, что для случайно выбранного n-вершинного d-регулярного двудольного графа, для всех подмножеств вершин с высокой вероятностью выполняется следующее: где является константой, зависящей от d. Алон и Ройхман показали, что для любого 1 > ε > 0 существует некоторое c(ε) > 0, такое что: для группы G порядка n рассмотрим граф Кейли на G с случайно выбранными элементами из G. Тогда, при стремлении n к бесконечности, полученный граф почти наверняка является ε-экспандером.

Применение и полезные свойства

Первоначальная мотивация для экспандеров заключается в создании экономичных и устойчивых сетей (телефонных или компьютерных): экспандер с ограниченной степенью – это асимптотически устойчивый граф, число ребер которого линейно растет с увеличением размера (количества вершин) для всех подмножеств. Графы-экспандеры нашли широкое применение в информатике, при разработке алгоритмов, кодов коррекции ошибок, экстракторов, псевдослучайных генераторов, сортировочных сетей и устойчивых компьютерных сетей. Они также использовались в доказательствах многих важных результатов в теории вычислительной сложности, таких как SL = L и теорема PCP. В криптографии графы-экспандеры используются для построения хеш-функций. В обзоре экспандерных графов 2006 года Хури, Линиал и Вигдерсон разделили изучение экспандерных графов на четыре категории: экстремальные задачи, типичное поведение, явные построения и алгоритмы. Экстремальные задачи фокусируются на ограничении параметров расширения, в то время как задачи, связанные с типичным поведением, характеризуют распределение параметров расширения в случайных графах. Явные построения направлены на создание графов, оптимизирующих определенные параметры, а алгоритмические вопросы посвящены оценке и определению значений параметров.

Пробоотбор с экспандером

Ограничение Черноффа утверждает, что при выборке большого количества независимых образцов из случайной величины в диапазоне [−1, 1], с большой вероятностью среднее значение этих образцов близко к математическому ожиданию случайной величины. Лемма выборки по экспандер-прогулке, сформулированная и , утверждает, что это также справедливо при выборке из прогулки на экспандер-графе. Это особенно полезно в теории дерандомизации, поскольку выборка в соответствии с экспандер-прогулкой требует значительно меньше случайных битов, чем независимая выборка.

Сеть сортировки AKS и приблизительные полуобороты

Сети сортировки принимают набор входных данных и выполняют серию параллельных шагов для их сортировки. Параллельный шаг состоит из выполнения любого количества непересекающихся сравнений и, возможно, обмена местами сравниваемых пар входных данных. Глубина сети определяется количеством параллельных шагов, необходимых для ее работы. Графы-экспандеры играют важную роль в сети сортировки AKS, которая достигает глубины O(log n). Хотя это асимптотически наилучшая известная глубина для сети сортировки, зависимость от экспандеров делает постоянную границу слишком большой для практического применения. В сети сортировки AKS графы-экспандеры используются для построения ε-полуделителей ограниченной глубины. ε-полуделитель принимает на вход перестановку длины n элементов (1, ..., n) и разделяет входные данные на два непересекающихся множества A и B таким образом, что для каждого целого числа k не более εk наименьших элементов находятся в B и не более εk наибольших элементов находятся в A. Множества A и B образуют ε-полуделитель. Согласно [ссылка на источник], ε-полуделитель глубины d можно построить следующим образом. Возьмем двудольный экспандер с n вершинами и степенью d, части X и Y которого имеют одинаковый размер, так что любое подмножество вершин размера не более εn имеет не менее соседей. Вершины графа можно рассматривать как регистры, содержащие входные данные, а ребра – как провода, сравнивающие входные данные двух регистров. В начале произвольно поместите половину входных данных в X и половину – в Y, а затем разложите ребра на d совершенных паросочетаний. Цель состоит в том, чтобы в конечном итоге X содержал примерно меньшую половину входных данных, а Y – примерно большую половину. Для этого последовательно обрабатываем каждое паросочетание, сравнивая регистры, соединенные ребрами этого паросочетания, и исправляя любые входные данные, находящиеся не в порядке. В частности, для каждого ребра паросочетания, если больший вход находится в регистре в X, а меньший – в регистре в Y, меняем местами эти два входа так, чтобы меньший оказался в X, а больший – в Y. Очевидно, что этот процесс состоит из d параллельных шагов. После всех d раундов множество A принимается за множество входных данных в регистрах в X, а множество B – за множество входных данных в регистрах в Y, чтобы получить ε-полуделитель. Чтобы понять это, заметим, что если регистр u в X и регистр v в Y соединены ребром uv, то после обработки паросочетания с этим ребром вход в u меньше, чем вход в v. Более того, это свойство сохраняется на протяжении всего процесса. Теперь предположим, что для некоторого k более чем εk входных данных (1, ..., k) находятся в B. Тогда, благодаря свойствам расширения графа, регистры этих входных данных в Y соединены как минимум с регистрами в X. В сумме это составляет более k регистров, поэтому должен существовать регистр A в X, соединенный с регистром B в Y, такой что конечный вход A не находится в (1, ..., k), а конечный вход B находится. Однако это противоречит предыдущему свойству, и, следовательно, выходные множества A и B должны быть ε-полуделителем.

Научно-исследовательские статьи

.
.
.