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

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

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

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

В Лемма Джонсона – Линденштрауса утверждает, что любое конечное метрическое пространство с п точки могут быть вложены в евклидово пространство размерности О(бревноп) с искажением 1 + ε, для любой постоянной ε > 0, где постоянный множитель в О-значение зависит от выбораε.[2] Этот результат и связанные с ним методы построения метрических вложений с малым искажением важны в теории аппроксимационные алгоритмы. Основной нерешенной проблемой в этой области является Гипотеза GNRS, который (если это так) будет характеризовать семейства графов, которые имеют вложения с ограниченным растяжением в пространства как все семейства минорно-замкнутых графов.

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

При изучении поток, сокращающий кривую, в котором каждая точка кривой в евклидовой плоскости движется перпендикулярно кривой со скоростью, пропорциональной локальной кривизне, Хьюскен (1998) Доказано, что коэффициент растяжения любой простой замкнутой гладкой кривой (с внутренними расстояниями, измеряемыми длиной дуги) изменяется монотонно. Точнее, в каждой паре (Икс,у) который формирует локальный максимум фактора растяжения, фактор растяжения строго уменьшается, кроме случаев, когда кривая представляет собой круг. Это свойство позже было использовано для упрощения доказательства теоремы Гейджа – Гамильтона – Грейсона, согласно которой каждая простая замкнутая гладкая кривая остается простой и гладкой до тех пор, пока она не схлопнется в точку, а перед этим сходится по форме к окружности.[5][6]

Рекомендации

  1. ^ Нарасимхан, Гири; Smid, Michiel (2007), Геометрические гаечные сети, Издательство Кембриджского университета, ISBN  0-521-81513-4.
  2. ^ Джонсон, Уильям Б.; Линденштраус, Иорам (1984), «Расширения липшицевых отображений в гильбертово пространство», Билс, Ричард; Бек, Анатоль; Беллоу, Александра; и другие. (ред.), Конференция по современному анализу и вероятности (Нью-Хейвен, штат Коннектикут, 1982), Современная математика, 26, Провиденс, Род-Айленд: Американское математическое общество, стр.189–206, Дои:10.1090 / conm / 026/737400, ISBN  0-8218-5030-X, МИСТЕР  0737400.
  3. ^ Кехо, Элейн (апрель 2012 г.), «Премия Моргана 2012 г.», Уведомления Американского математического общества, 59 (4): 569–571, Дои:10.1090 / noti825.
  4. ^ Пардон, Джон (2011), "Об искажении узлов на вложенных поверхностях", Анналы математики, Вторая серия, 174 (1): 637–646, arXiv:1010.1972, Дои:10.4007 / летопись.2011.174.1.21, МИСТЕР  2811613.
  5. ^ Хёйскен, Герхард (1998), "Принцип сравнения расстояний для эволюционирующих кривых", Азиатский математический журнал, 2 (1): 127–133, МИСТЕР  1656553.
  6. ^ Эндрюс, Бен; Брайан, Пол (2011), "Оценка кривизны для потока, укорачивающего кривую, посредством сравнения расстояний и прямого доказательства теоремы Грейсона", Journal für die Reine und Angewandte Mathematik, 653: 179–187, arXiv:0908.2682, Дои:10.1515 / CRELLE.2011.026, МИСТЕР  2794630.