Лемма регулярности Семереди: различия между версиями

 

{{рамка}}

 

Двудольный граф <math>G=(U \sqcup V, E)</math> называется <math>\varepsilon</math>-равномерным если для любых <math>S \subset U, T \subset V</math>, удовлетворяющих условиям <math>|S| > \varepsilon |U|, |T| > \varepsilon |V|</math>, выполнено неравенство

Очевидно, что полный и пустой двудольные графы являются <math>\varepsilon</math>-регулярными для любого <math>\varepsilon > 0</math>. Следует заметить, что это, вообще говоря, не так для произвольного [[Регулярный граф|регулярного в обычном смысле]] двудольного графа (в качестве контрпримера можно рассмотреть, например, объединение нескольких непересекающихся по множеству вершин регулярных графов).

 

 

=== Формулировка леммы ===

 

{{рамка}}

 

Для любых <math>\varepsilon > 0,\ m \ge 2</math> существуют <math>M, n_0</math> такие, что для любого графа <math>G=(V,E)</math> с количеством вершин <math>|V| > n_0</math> существует разбиение <math>V = V_1 \sqcup \dots \sqcup V_k\ (m \le k \le M)</math> на максимально возможно равные по размеру доли <math>|V_1|=\dots=|V_{k-1}| \ge |V_k|</math> такие, что для <math>(1-\varepsilon) \binom{k}{2}</math> из пар этих долей двудольный граф из рёбер, пролегающих между ними, является <math>\varepsilon</math>-регулярным.