4817
правок
Самый неплотный разрез: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 43: | Строка 43: | ||
'''Определение 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>, такое, что для всех (x | '''Определение 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. Для любых | '''Теорема 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>.''' | ||
