Фактор растяжения

Не путать с коэффициентом растяжения псевдоаносовского отображения .

Коэффициент растяжения (т.е. константа билипшица ) вложения измеряет фактор, с помощью которого вложение искажает расстояния . Предположим, что одно метрическое пространство S вложено в другое метрическое пространство T с помощью метрического отображения , непрерывной взаимно однозначной функции f , которая сохраняет или уменьшает расстояние между каждой парой точек. Тогда вложение порождает два разных понятия расстояния между парами точек в S . Любая пара точек ( x , y ) в S имеет как внутреннее расстояние , расстояние от x до y в S так и меньшее внешнее расстояние, расстояние от f ( x ) до f ( y ) в T. , Коэффициент растяжения пары — это соотношение между этими двумя расстояниями d ( f ( x ), f ( y ))/ d ( x , y ) . Коэффициент растяжения всего отображения — это верхняя граница коэффициентов растяжения всех пар точек. Коэффициент растяжения также называют искажением. или расширение отображения.

Фактор растяжения важен в теории геометрических ключей , взвешенных графиков , которые аппроксимируют евклидовы расстояния между набором точек на евклидовой плоскости . В этом случае встроенная метрика S представляет собой конечное метрическое пространство, расстояния которого представляют собой длины кратчайших путей в графе, а метрика T , в которую вкладывается S, представляет собой евклидову плоскость. Когда граф и его вложение фиксированы, но веса ребер графа могут меняться, коэффициент растяжения минимизируется, когда веса точно равны евклидовым расстояниям между конечными точками ребер. Исследования в этой области были сосредоточены на поиске разреженных графов для заданного набора точек с низким коэффициентом растяжения.

Лемма Джонсона -Линденштрауса утверждает, что любое конечное множество с n точками в евклидовом пространстве может быть вложено в евклидово пространство размерности O (log n ) с искажением 1 + ε для любой константы ε > 0 , где постоянный множитель в O -обозначение зависит от выбора ε . Этот результат и связанные с ним методы построения метрических вложений с малыми искажениями важны в теории аппроксимационных алгоритмов . Основной открытой проблемой в этой области является гипотеза GNRS , которая (если она верна) будет характеризовать семейства графов, которые имеют вложения ограниченного растяжения в $\ell _{1}$ пространства как все минорно-замкнутые семейства графов.

В теории узлов искажение узла — это инвариант узла , минимальный коэффициент растяжения любого вложения узла в качестве пространственной кривой в евклидово пространство .Студент-исследователь Джон Пардон получил премию Моргана в 2012 году за исследование, показывающее, что не существует верхней границы искажения торических узлов , решая проблему, первоначально поставленную Михаилом Громовым .

При исследовании потока, сокращающего кривую , в котором каждая точка кривой в евклидовой плоскости движется перпендикулярно кривой со скоростью, пропорциональной локальной кривизне, Хьюскен (1998) доказал, что коэффициент растяжения любой простой замкнутой гладкой кривой (при этом внутренние расстояния измеряются длиной дуги) изменяется монотонно. Более конкретно, в каждой паре ( x , y ) , которая образует локальный максимум коэффициента растяжения, коэффициент растяжения строго уменьшается, за исключением случаев, когда кривая представляет собой круг. Позже это свойство было использовано для упрощения доказательства теоремы Гейджа-Гамильтона-Грейсона, согласно которой каждая простая замкнутая гладкая кривая остается простой и гладкой до тех пор, пока она не схлопнется в точку, а перед этим сходится по форме к кругу.