92
правки
Изменения
м
→Лемма о перемешивании
===Лемма о перемешивании===
Лемма о перемешивании утверждает, что для любых двух подмножеств вершин <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>-регулярном графе, также как и в случайном графе Эрдёша — Реньи<ref>[[wikipedia:Erdős–Rényi model|Wikipedia {{---}} Erdős–Rényi model]]</ref> с вероятностью <tex>{\tfrac cfrac {d}{n}}</tex> выбора ребра, ожидается <tex>{\tfrac cfrac {d}{n}}\cdot |S|\cdot |T|</tex> рёбер между <tex>S</tex> и <tex>T</tex>.
Более формально, пусть <tex>E(S, T)</tex> обозначает число рёбер между <tex>S</tex> и <tex>T</tex>. Если эти два множества пересекаются, дуги в пересечении считаются дважды, так что
где <tex>\lambda </tex> — абсолютное значение нормализованного второго по величине собственного значения.
Недавно Билу (Bilu) и Линайл (Linial) показали, что обратное тоже верно, то есть, при условии выполнения неравенства из леммы второе по величине собственное значение равно <tex>O(d\lambda \cdot (1+\log(\tfrac{1/}{\lambda })))</tex><ref>[[http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf|Lifts, discrepancy and nearly optimal spectral gap]]</ref>.
===Блуждания по экспандеру===
