143
правки
Изменения
Экспандер графы без доказательств
|proof=TODO
}}
{{Лемма
|statement= Пусть <tex>G</tex> <tex>d</tex>-регулярный граф, а <tex>h(G)</tex> его реберное расширение. Тогда <tex>\lambda(G) \le d - \frac {h(G)^2} d</tex>
}}
{{Определение
|definition=Собственным числом графа <tex>\lambda</tex> называют собственное число его матрицы смежности.
}}
{{Лемма
|statement=Пусть <tex>G</tex> <tex>d</tex>-регулярный граф со вторым по величине собственным числом <tex>\lambda</tex>. Пусть <tex>F \subseteq E</tex> множество ребер. Вероятность <tex>p</tex> того, что случайный путь, начинающийся со случайного ребра из <tex>F</tex> на <tex>i+1</tex> шаге попадет <tex>F</tex> ограничена <tex>\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i</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]
