Изменения

|statement=

Пусть <tex>\epsilon</tex> - некоторое положительное число. Тогда для <tex>\forall \ n</tex> и <tex>k \leq n</tex> найдется <tex>d = O(\log n)</tex> и <tex>m = O(dk)</tex> такие, что <tex>\exists</tex> двудольный экспандер с параметрами <tex>(n, m, d, k, \epsilon)</tex>.

|proof=

Выберем случайный граф, то есть для <tex>\forall \ v \in L</tex> случайно и независимо выбираем <tex>d</tex> соседей в <tex>R</tex> (разрешаются кратные ребра). Покажем с большой вероятностью такой граф оказывается экспандером.

Таким образом, для выбранных значений параметров сумм не превосходят 1. Это означает, что с положительной вероятностью случайный двудольный граф является <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex> - экспандером. Теорема доказана.

}}

{{Теорема

|statement=