143
правки
Изменения
Лемма о экспандерах
}}
==Экспандер графы==
Экспандер графы играют важную роль во многих теоретических результатах.
{{Определение
|definition= <tex>G=(V,E)</tex> <tex>d</tex>-регулярный граф. Положим <tex>E(S,\overline{S})=|(S \times \overline{S}) \cap E|</tex> равным количеству ребер их подмножества <tex>S\in V</tex> в его дополнение. Определим реберное расширение как
<tex>h(G)=\operatorname*{min}\limits_{S:|S|<\frac {|V|} 2} \frac {E(S, \overline S)} {|S|}</tex>
}}
{{Лемма
|about=О экспандерах
|statement=Существует <tex>d_0 \in \mathbb{N}</tex> и <tex>h_0 >0</tex> такие, что есть построимое за полиномиальное время семейство <tex>\lbrace X_n\rbrace_{n \in \mathbb{N}}</tex> <tex>d_0</tex>-регулярных графов <tex>X_n</tex> с <tex>n</tex> вершинами таких, что <tex>h(X_n) \ge h_0</tex>.
|proof=TODO
}}
==Дополнительные материалы==
* [ http://www.math.ias.edu/ boaz/ExpanderCourse/|N. Linial and A. Wigderson. Expander graphs and their applications. Lecture notes of a course, 2003]
==Источники==
* [http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
* [http://www.cs.utah.edu/~alfeld/LecturePDFs/pcp.pdf|The PCP Theorem, Notes by Scott Alfeld, 2008]
