143
правки
Изменения
Лемма о расширении
Эта лемма известна как экспандер-замена(expander-replacement transformation).
{{Лемма
|about=О расширении
|statement=
Пусть <tex>d_0, h_0 >0</tex> некоторые константы. Любой <tex>d</tex>-регулярный граф условий <tex>G</tex> может быть преобразован в <tex>G'</tex> такой, что:
* <tex>G'</tex> <tex>(d + d_0 + 1)</tex>-регулярный, имеет собственные циклы и <tex>\lambda(G') \le d + d_0 + 1 - \frac {h_0^2} {d + d_0 + 1} < deg(G')</tex>
* <tex>size(G')=O(size(G))</tex>
* <tex> \frac d {d + d_0 + 1} \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>
|proof=TODO
}}
===Усиление===
===Композиция===
