Изменения
определение для однородного экспандера
'''Граф-экспандер''' (или расширяющийся граф, англ. ''expander graph'') - в комбинаторике сильно разреженный граф, при этом связность определяется по вершинам, дугам или спектру.
{{Определение
|definition=
'''Однородный (комбинаторный) экспандер''' называется граф <tex>G = (V, E)</tex> с параметрами <tex>(n, d, \epsilon)</tex>, где <tex>n = |V|</tex>, степень любой вершины равно d, <tex>\epsilon</tex> < 1, если выполняется условие: для <tex>\forall S \subset V</tex> <tex>|S| \leq n/2</tex> <tex>\exists</tex> множество соседей <tex>S</tex> <tex>r(S) = {v: \exists w \in S, (v, w) \in E}</tex> достаточно велико, то есть <tex>|r(S)| > (1 + \epsilon)|S|</tex>.
}}
'''Замечание 1:''' в графе могут присутствовать кратные ребра и петли. Если у любой вершины есть петля, то <tex>\forall S \supseteq r(S)</tex>.
'''Замечание 2:''' чем больше <tex>\epsilon</tex>, тем сильнее свойство расширения.
{{Теорема
|statement=
<tex>\forall n</tex>, <tex>\forall \epsilon < 1</tex>
для достаточно больших четных <tex>d = d(\epsilon)</tex> существует однородный(комбинаторный) экспандер с параметрами <tex>(n, d, \epsilon)</tex>.
}}
{{Определение
|definition=
