Самый неплотный разрез: различия между версиями

Помимо задачи о самом неплотном разрезе, Арора и коллеги также рассмотрели тесно связанную с ней задачу о сбалансированном сепараторе. Разбиение (S, V \ S) графа G называется c-сбалансированным сепаратором для <math>0 < c \le \frac{1}{2}</math>, если и S, и V \ S имеют не менее c|V| вершин. Целью задачи о сбалансированном сепараторе является поиск c-сбалансированного разбиения с минимальной разреженностью, которая обозначается как <math>\alpha_c(G)</math>.

'''Определение 1''' (Опр. 4 в [4]). Пусть <math>\vec x_1, \vec x_2, ..., \vec x_n</math> – множество из n точек в <math>\mathcal{R}^n</math>, снабженное квадратично-евклидовой метрикой <math>d(x, y) = \parallel x - y \parallel_2^2</math>. Множество точек считается ''<math>(t, \gamma, \beta)</math>-растяжимым в масштабе <math>\ell</math>'', если для хотя бы части <math>\gamma</math> всех n-мерных единичных векторов u существует частичное соответствие <math>M_u = \{ (x_i, y_i) \} _i</math> между этими точками, причем <math>|M_u| \ge \beta n</math>, такое, что для всех <math>(x, y) \in M_u, d(x, y) \le \ell^2</math> и <math>\langle u, \vec x - \vec y \rangle \ge t \ell / \sqrt{n}</math>. Здесь <math>\langle \cdot , \cdot \rangle</math> обозначает скалярное произведение двух векторов.

'''Теорема 3. Для любых <math>\gamma, \beta ></math> 0 существует константа <math>С = C(\gamma, \beta)</math>, такая, что если <math>t > C \; log^{1/3} n</math>, то никакое множество из n точек в пространстве <math>\mathcal{R}^n</math> не может быть <math>(t, \gamma, \beta)</math>-растяжимым для любого масштаба <math>\ell</math>.'''