106
правок
Изменения
→Лемма о перемешивании
Ниже приведены некоторые свойства экспандеров, считающиеся полезными во многих областях.
===Лемма о перемешивании===
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <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/>-регулярном графе, также как и в случайном графе Эрдёша — Реньи с вероятностью <tex>{\tfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\tfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между <tex>S </tex> и <tex>T</tex>.
Более формально, пусть <tex>E(S, T)</tex> обозначает число рёбер между <tex>S</tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <tex>O(d\lambda \cdot (1+\log(1/\lambda )))</tex>.
===Блуждания по экспандеру===
Согласно границе Чернова, если выбирать много независимых случайных значений из интервала <tex>[−1, 1]</tex>, с большой степенью вероятности среднее выбранных значений будет близко к математическому ожиданию случайной переменной. Лемма о блуждании по экспандеру, согласно статьям Аджтари, Комлоша и Семереди и Гилмана, утверждает, что то же самое верно и для блужданий по экспандеру. Это полезно в теории дерандомизации, поскольку блуждание по экспандеру использует много меньше случайных бит, чем случайная независимая выборка.
