Изменения
→Приложения и полезные свойства
Первоначально интерес к экспандерам возник с целью построения устойчивой сети (телефонов или компьютеров) — число дуг графов расширения с ограниченным значением регулярности растет линейно по отношению к числу вершин.
Экспандеры нашли широкое применение в теории вычислительных машин и систем, для построения алгоритмов, в корректирующих кодах[en], экстракторах[en], генераторах псевдослучайных чисел, сетях сортировки[8] и компьютерных сетях. Они также используются для доказательства многих важных результатов в теории вычислительной сложности, таких как <tex>SL[en]=L[en][9] </tex> и Теорема PCP[10]. В rриптографии криптографии экспандеры используются для создания хеш-функций.
Ниже приведены некоторые свойства экспандеров, считающиеся полезными во многих областях.
===Лемма о перемешивании===
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <tex>S,T\subseteq V </tex> число рёбер между <tex>S </tex> и <tex>T </tex> примерно равно числу рёбер в случайном <tex>d</tex>-регулярном графе. Приближение тем лучше, чем меньше <tex>\lambda =\max\{|\lambda _{2}|</tex>,<tex>|\lambda _{n}|\}</tex>. В случайном <tex>d<tex/>-регулярном графе, также как и в случайном графе Эрдёша — Реньи[en]с вероятностью <tex>{\tfrac {d}{n}} </tex> выбора ребра, ожидается <tex>{\tfrac {d}{n}}\cdot |S|\cdot |T| </tex> рёбер между S и T.
Более формально, пусть <tex>E(S, T) </tex> обозначает число рёбер между <tex>S </tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
<tex>E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S)</tex>.Лемма о перемешивании утверждает, что[11]
<tex>\left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq d\lambda {\sqrt {|S|\cdot |T|}}</tex>,где λ <tex>\lambda </tex> — абсолютное значение нормализованного второго по величине собственного значения.
Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <tex>O(d\lambda \cdot (1+\log(1/\lambda )))[12]</tex>.
===Блуждания по экспандеру===
Согласно границе Чернова[en], если выбирать много независимых случайных значений из интервала <tex>[−1, 1]</tex>, с большой степенью вероятности среднее выбранных значений будет близко к математическому ожиданию случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди[13] и Гилмана[14], утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации[en], поскольку блуждание по экспандеру использует много меньше случайных бит, чем случайная независимая выборка.
==Источники==
// на потом
