Home

Пятница, 13 февраля, 18:00, к. 106

Пятница, 13 февраля, комната 106. Начало в 18:00.

Докладчик: П. Затицкий.

Тема: О вложении конечных метрических пространств в $ l_\infty^n $.

Abstract

Доклад по совестной работе с Ф.В. Петровым.

В докладе будет изучаться изометричное вложение конечного метрического пространства в пространство $ l_\infty^n $. Будет доказано, что
1. Для любой натуральной константы с существует $ N=N(c) $, такое что любое метрическое пространство на $ N $ точках можно вложить в $ l_\infty^{N-c} $.
2. Существует константа $ c $, такая что при больших $ N $ существует метрическое пространство на $ N $ точках, которое невозможно вложить в $ l_\infty^{N-cN^{3/4}} $.

Изометричное вложение в пространство $ l_\infty^n $ есть задание n координатных функций, каждая из которых должна быть 1-липшицевой. Поскольку расстояние между точками $ X $ и $ Y $ в пространстве $ l_\infty $ есть максимум $ |f(X)-f(Y)| $ по координатным функциям $ f $, то для каждой пары точек $ X $ и $ Y $ метрического пространства должна быть хотя бы одна координатная функция, такая что $ |f(X)-f(Y)|=\rho(X,Y) $. Теперь для каждой 1-липшицевой функции нарисуем следующий граф. Вершины будут соответствовать точкам метрического пространства. Две вершины $ X $ и $ Y $ будем соединять ребром только тогда, когда $ |f(X)-f(Y)|=\rho(X,Y) $. Итого, задание вложения конечного метрического пространства в $ l_\infty^n $ равносильно покрытию полного графа с вершинами в точках метрического пространства при помощи n графов 1-липшицевых функций.

Для доказательства первой части, мы будем рассматривать специальные "однородные" пространства, для которых соответствующий полный граф будет покрыт конструктивно. Из теоремы Рамсея получим, что любое достаточно большое пространство содержит достаточно большое однородное подпространство.

Для доказательства второй части, возьмем метрическое пространство с расстояниями 1 и 2 так, чтобы не было цикла длинны 4 из ребер длины 2, и не было большого полного подпространства с расстояниями 1. Получится, что граф 1-липшицевой функции не может содержать два ребра длинны 2, не имеющих общего конца. Из локальной леммы Ловаса следует, что можно построить метрическое пространство такого вида, дающее искомую оценку.

Интересно также, что если наложить на метрическое пространство дополнительное условие --- несоизмеримость растояний (то есть линейную независимость над $ \mathbb{Z} $), то получится, что каждый граф 1-липшицевой функции не имеет циклов. Отсюда простым подсчетом ребер следует, что такое пространство на $ 2n+1 $ точке невозможно вложить в $ l_\infty^n $.