Простирания фактор А.Н. встраиванию мер фактор , с помощью которого вложение искажает расстояния . Предположим, что одно метрическое пространство S вложено в другое метрическое пространство T с помощью метрического отображения , непрерывной взаимно однозначной функции f, которая сохраняет или уменьшает расстояние между каждой парой точек. Тогда вложение приводит к двум различным представлениям о расстоянии между парами точек в S . Любая пара точек ( x , y ) в S имеет внутреннее расстояние , расстояние от xчтобы у в S , а также меньшее расстояние примесного, расстояние от ф ( х ) к ф ( у ) в Т . Фактор растяжения пары - это соотношение между этими двумя расстояниями, d ( f ( x ), f ( y )) / d ( x , y ) . Фактор растяжения всего отображения - это супремум (если он существует) факторов растяжения всех пар точек. Фактор растяжения также называют искажением или расширением отображения.
Фактор растяжения важен в теории геометрических гаечных ключей , взвешенных графиков, которые аппроксимируют евклидовы расстояния между набором точек на евклидовой плоскости . В этом случае вложенная метрика S является конечным метрическим пространством, расстояния которого являются длинами кратчайших путей в графе, а метрика T, в которую вложена S, является евклидовой плоскостью. Когда граф и его вложение фиксированы, но веса ребер графа могут меняться, коэффициент растяжения минимизируется, когда веса в точности равны евклидовым расстояниям между концами ребер. Исследования в этой области были сосредоточены на поиске разреженных графиков для заданного набора точек с низким коэффициентом растяжения. [1]
Джонсон-Линденштраусс лемма утверждает , что любое конечное метрическое пространство с п точками может быть встроены в евклидово пространства размерности O (журнал п ) с искажением 1 + ε , для любой константы ε > 0 , где коэффициента постоянная в O -notation зависит от выбора ε . [2] Этот результат и связанные с ним методы построения метрических вложений с низким уровнем искажений важны в теории приближенных алгоритмов . Основной нерешенной проблемой в этой области является гипотеза GNRS , которая (если она верна) будет характеризовать семейства графов, которые имеют вложения с ограниченным растяжением в пространства как все семейства минорно-замкнутых графов.
В теории узлов искажение узла является инвариантом узла , минимальным фактором растяжения любого вложения узла как пространственной кривой в евклидово пространство . Студент-исследователь Джон Пардон получил в 2012 году премию Моргана за свое исследование, показавшее, что не существует верхней границы искажения торических узлов , решая проблему, первоначально поставленную Михаилом Громовым . [3] [4]
При исследовании потока сокращения кривой , в котором каждая точка кривой на евклидовой плоскости движется перпендикулярно кривой со скоростью, пропорциональной локальной кривизне, Хьюскен (1998) доказал, что коэффициент растяжения любой простой замкнутой гладкой кривой (с собственными расстояниями, измеряемыми длиной дуги) изменяется монотонно. Более конкретно, в каждой паре ( x , y ), которая формирует локальный максимум фактора растяжения, фактор растяжения строго уменьшается, за исключением случаев, когда кривая представляет собой круг. Это свойство позже было использовано для упрощения доказательства теоремы Гейджа – Гамильтона – Грейсона, согласно которой каждая простая замкнутая гладкая кривая остается простой и гладкой до тех пор, пока она не схлопнется в точку, а перед этим сходится по форме к окружности. [5] [6]
Рекомендации
- ^ Нарасимхан, Гири; Smid, Michiel (2007), Геометрические сети гаечного ключа , Cambridge University Press , ISBN 0-521-81513-4.
- ^ Джонсон, Уильям Б .; Lindenstrauss, Joram (1984), "Расширения липшицевых отображений в гильбертово пространство", в Beals, Richard; Бек, Анатоль; Беллоу, Александра; и другие. (ред.), Конференция по современному анализу и вероятности (Нью-Хейвен, штат Коннектикут, 1982) , Contemporary Mathematics, 26 , Providence, RI: American Mathematical Society, pp. 189–206 , doi : 10.1090 / conm / 026/737400 , ISBN 0-8218-5030-X, Руководство по ремонту 0737400.
- ^ Кехо, Элейн (апрель 2012), "2012 Морган премии", Извещения Американского математического общества , 59 (4): 569-571, DOI : 10,1090 / noti825.
- ^ Пардон, Джон (2011), "Об искажения узлов на вложенных поверхностях", Анналы математики , вторая серия, 174 (1): 637-646, Arxiv : 1010.1972 , DOI : 10,4007 / annals.2011.174.1.21 , MR 2811613.
- ^ Хьюскен, Герхард (1998), «Принцип сравнения расстояний для эволюционирующих кривых», Азиатский журнал математики , 2 (1): 127–133, hdl : 11858 / 00-001M-0000-0013-5964-4 , MR 1656553 CS1 maint: обескураженный параметр ( ссылка ).
- ^ Эндрюс, Бен; Брайан, Пол (2011), «Оценка кривизны для потока, укорачивающего кривую, посредством сравнения расстояний и прямого доказательства теоремы Грейсона», Journal für die Reine und Angewandte Mathematik , 653 : 179–187, arXiv : 0908.2682 , doi : 10.1515 / CRELLE. 2011.026 , Руководство по ремонту 2794630.