Об изоморфизмах и изометриях единичных дистанционных графов слоек
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 3 (71) т.18, 2026 года.
Бесплатный доступ
Настоящая работа посвящена некоторым вопросам, связанным с единичными дистанционными графами метрических пространств вида R𝑛 × [0, 𝜀]𝑚, именуемых слойками, и их изоморфизмами.
Короткий адрес: https://sciup.org/142248885
IDS: 142248885 | УДК: 519.17
On isomorphisms and isometries of unit distance graphs of layers
This work is devoted to certain questions related to unit distance graphs of metric spaces of the form R𝑛 × [0, 𝜀]𝑚, referred to as layers, and their isomorphisms.
Текст научной статьи Об изоморфизмах и изометриях единичных дистанционных графов слоек
Напомним, что единичным дистанционным графом подмножества V метрического пространства (X, р) называется граф, множеством вершин которого является V, а ребра проводятся в точности между теми парами вершин (х,у), для которых выполнено р(х,у) = 1. Настоящая работа посвящена вопросам, связанным с единичными дистанционными графами метрических пространств вида R" х [Q,E]m, и их изоморфизмами.
Единичные дистанционные графы различных пространств, в частности, пространства R”, изучалисв во многих работах. Приведем некоторые известные резулвтаты.
Хроматическим числом %(Х ) метрического пространства X называется минималвное число множеств, не содержащих пар точек на расстоянии 1, на которые можно разбитв пространство X. Легко видетв, что у(Х) равно числу независимости единичного дистанционного графа пространства X. Хроматическим числам посвящено множество работ (см., например, обзоры [10] и [11]). Одной из наиболее широко исследуемых связанных задач является знаменитая проблема Нелсона - Хадвигера, которая заключается в нахождении величины y(R2). Эта задача до сих пор остается нерешенной. В настоящий момент известны оценки
5 < x(R2) < 7.
Нижняя граница доказана О. де Греем в 2018 г. (тем самым была улучшена прежняя простая граница 4), а верхняя граница 7 была получена Г. Хадвигером в 1961 г.
«Московский физико-технический институт (пациопальпый исследовательский университет)», 2026
Аналогичный вопрос о хроматическом числе пространства произвольной размерности также широко рассматривался в литературе. Доказаны следующие оценки:
(1.239... + o(1))n < у А') < (3 + о(1))Д
Нижняя граница доказана А. М. Райгородским в работе [9], а верхняя граница получена Д. Ларманом и А. Роджерсом в [6] и передоказана Р. Просановым в [8]. Некоторые оценки величин у (R3) и y(Q”) можно найти в работах [1] и [7].
Теперв введем понятие слойки, с которым мы будем работатв дальше. Оно расширяет понятие планарной ленты, то есть множества вида R х [0, е] на плоскости. Для произвольных натуральных чисел п,т G N и чисел р G [1, +го], е € (0, +го) рассмотрим метрическое пространство, порожденной на подмножестве R" х [0,е]т пространства Rn+m стандартной Zp-метрикой. Обозначим это метрическое пространство как L(n,m,p, е) и будем называть слойкой. Здесь под стандартной Zp-метрикой подразумевается норма, заданная следующей формулой:
И< = (|^1|P + NP + ••• + |^n|P)^ .
Хроматические числа слоек были впервые подробно изучены в работе [7]. В том числе были доказаны следующие оценки:
5 < y(L(2,1,2,е)) = y(R2 х [0,е]) < 7 for 0 <е< ^3/7,
x(L(2,d, 2,е))= y(R2 х [0,е]й) < 7 for 0 < е < еo(d),
X(L(2,2, 2,е))= y(R2 х [0,е]2) > 6 foг е> 0.
В работе [1] был получен следующий результат:
10 < ХЩ3, 6, 2, е)) = y(R3 х [0, е]6) < 15.
Помимо хроматических чисел, активно изучались и другие характеристики единичных дистанционных графов слоек. Так, в работе, [12], Л. Шабанов доказал нижнюю оценку Турановского типа для минимального числа ребер в конечном подграфе единичного дистанционного графа слойки L(2,d, 2е) = R2 х [0, е]^, используя его число независимости. В статье [3] Б. Босло для каждого нечетного натурального к нашел минимальное такое число е(к), что единичный дистанционный граф планарной слойки R х [0, е(к)] = L(1,1, 2, е(к)) содержит простой цикл длины к, и это число тем меньше, чем больше к.
Таким образом, результат Босло позволяет доказать, что единичные дистанционные графы некоторых планарных слоек (ширина которых достаточно сильно отличается) не являются изоморфными, поскольку их различает наличие или отсутствие цикла данный длины. Приведенные выше результаты о хроматических числах слоек также показывают, что в некоторых случаях их единичные дистанционные графы заведомо отличаются. Однако открытым оставался вопрос: верно ли это для произвольной пары слоек?
2. Доказанные ранее результаты
В недавней работе нам удалось доказать, что (при некоторых уточнениях) единичные дистанционные графы слоек разной ширины не являются изоморфными. Приведем доказанные нами результаты.
Теорема 1. Для любых е1,е2 G (0, +го) единичные дистанционные графы планарных слоек L(1, 1, 2, е1) = R х [0, е1] и L(1, 1, 2, е2) = R х [0, е2] являются изоморфными тогда и только тогда, когда е1 = е2.
Теорема 2. Для любых п > 2, m > 1, р G (1, +го), и е1,е2 G (0, +го) единичные дистанционные графы слоек L1 = L(n, т,р, е1) и L2 = L(n, т,р, е2) являются изоморфными тогда и только тогда, когда е1 = е2.
Таким образом, теорема 1 позволяет различить единичные дистанционные графы в случае планарных лент произвольной ширины, а теорема 2 - единичные дистанционные графы многомерных слоек с произвольной гладкой /^-метрикой (то есть в случае р Е (0, +^)). Заметим, что последнее требование существенно. Например, для р = +^ и произвольных 61, 62 Е (0,1) единичные дистанционные графы слоек L(n, 1, +^,щ и L(n, 1, +^,62), очевидно, являются изоморфными.
Основной метод доказательства теоремы 1 состоит в следующем. Мы показали, что любой изоморфизм р единичных дистанционных графов слоек L1 = L(1,1,2,61) и L2 = L(1,1, 2, 62) должен сохранять относительный порядок проекций точек на ось абсцисс, то есть если проекция точки у лежит строго между проекциями точек ж и г, то проекция точки р(у ) лежит строго между проекциями точек р(х) и p(z ). Используя этот факт, можно вывести, что изоморфизм р также сохраняет все отрезки, параллельные оси ординат (будем называть такие отрезки вертикальными), и относительный порядок точек на этих отрезках. Далее вводится конструкция, именуемая (N,M )-расческой (рис. 1), содержащая М «зубцов» (точки Ci на рисунке) и «основание» в виде отрезка длины N, разделенного точками ai на единичные отрезки. Легко видеть, что ширина 6 Е (0,1) планарной ленты однозначно задается множеством всех пар (N,M ), при которых эта планарная лента содержит некоторую (N, М )-расческу. Мы показали, что изоморфизм р должен сохранять расчески, что завершает доказательство в случае 61, 62< 1. В случае 6i > 1 мы дополнительно используем конструкцию fc-сэндвича (рис. 2) и некоторые технические детали.
Рис. 1. Пример (4,5)-расчески
Доказательство теоремы 2 основано на похожих рассуждениях. Мы показали, что изоморфизм единичных дистанционных графов слоек должен сохранять некоторые геометрические свойства. Назовем прямые (отрезки, подпространства и т.д.) в пространстве Rn+m и в соответствующей слойке, параллельные подпространству Rn х {0}, горизонтальными. Назовем прямые (отрезки, подпространства и т.д.), параллельные подпространству
{0} х Rm - вертикальны ми. Для точки ж G Rn+m обозначим через Нх и VX содержащие ее горизонтальное подпространство размерности п и вертикальное подпространство размерности т. соответствеппо.
Фактически при доказательстве теоремы 2 мы получили следующий вспомогательный факт.
Лемма 1. Пусть п > 2, т1, т2 > 1, р G (1, +го), и £1, £2 G (0, +го). Пусть р - изоморфизм единичных дистанционных графов слоек Li = L(п,т1,р,£1) и L2 = L(п,т2,р,£2). Тогда р и р-1 должны сохранять горизонтальные прямые, относительный порядок точек на горизонтальных прямых, расстояния на горизонтальных прямых, отношение у G VX, и любые целые расстояния.
Третья ранее доказанная нами теорема связана с отдельным направлением в изучении единичных дистанционных графов, о котором нужно рассказать подробнее. Напомним, что биективное отображение метрического пространства на себя называется изометрией, если оно сохраняет расстояния между любыми парами точек. В работе [4] Ф. Бекман и Д. Куорлз доказали, что любое биективное отображение пространства R” на себя, сохраняющее единичные расстояния, является изометрией. В статье [2] А. Александров поставил следующий вопрос (известный как проблема Александрова): для каких конечномерных (размерности хотя бы 2) нормированных пространств X любая биекция р : X ^ X, сохраняющая единичные расстояния, является изометрией?
Из леммы 1 легко следует выполнение этого свойства для некоторых слоек с евклидовой нормой.
Теорема 3. Пусть п > 2 и £ G (0, +го), и пусть р - автоморфизм единичного дистанционного графа слойки L1 = L(n, 1, 2,£) (то есть взаимно-однозначное отображение, сохраняющее единичные расстояния). Тогда р является изометрией этой слойки.
3. Обобщения ранее полученных результатов
В данной статье мы докажем обобщение теоремы 3 на случай произвольной гладкой Zp-пормы.
Теорема 4. Пусть п > 2,т G N, р G (1, +го), £ £ G (0, +го). Пусть р - автоморфизм единичного дистанционного графа слойки L = L(n, т, р, g ) . Тогда р является изометрией этой слойки.
Доказательство теоремы 4.
Пусть ж, у G L - две точки, такие, что у GVX, Нх -уН- = а.
Тогда, очевидно, существуют k G N,S > 0и z G L такие, что выполнено z G Нх, Hz - хН- = (к - ар)1/р, Hz - уЦр = к.
Применим лемму 1 к слойкам Li = L2 = L и изоморфизму р их единичных дистанционных графов. Тогда мы получаем
р(z) g H V(x) , р(у) GVp(x), |z - у н р = Hр(z) - р ( у ) н р = к;
1Hz) -р(х)|р = Hz -х|р = (кр - ач1-.
Следовательно,
1|р(х) - р(у)Н- = (ЦрС^ - р(у)|р - Нр^ - р(х)|р)1/р = а.
Таким образом, р сохраняет расстояния не только на горизонтальных прямых, но и на вертикальных множествах вида VX. Если отрезок аЬ - вертикальный, а отрезок Ьс - горизонтальный, то |а - ЬЦ- + НЬ - с|р = |а - сН— Значит, р сохраняет все расстояния и является изометрией. Теорема 5 доказана.
В теоремах 1 и 2 предполагалось, что у слоек L(n, т,р, Ei) различаются только значения ширины ei, а пара метры п, т,р совпадают. Теперь мы сформулируем и докажем обобщение теоремы 2 для случая различных пит.
Теорема 5. Пусть ni,n2 > 2, т1,т2 > 1, р € (1, +w), u е 1 ,е 2 € (0, +го). Пусть Li = L(n1,т1,р,E1) и L2 = L(n2,т2,р,E2) и выполнено хотя бы одно из следующих условий.
(И). ni = П2, р = 2.
(г2). ni = П2, т-1 = т2, Ei = E2.
-
(i3) . ni = п2, е 1 • т^ = е 2 • т2/Р■
Тогда единичные дистанционные графы слоек Li и L2 не изоморфны.
Доказательство теоремы 5. Предположим, выполнено (il). Без ограничения общности будем считать, что ni > П2- Предположим, что f - изоморфизм единичных дистанционных графов слоек Li и L2- Тог да в Li найдутся такие попарно различные точки xi,... ,xn1+i, что для любых различных i,j € {1,...,ni + 1} прямая XiXj является горизонтальной
(см. определение ранее), и выполнено ||x'i — Xj ^2 = 1 (то есть найдется ni-мерный пра вильный симплекс, лежащий в горизонтальной гиперплоскости). Тогда, в силу леммы 1, в L2 найдутся точки f (xi),..., f (xn1+i) с теми же свойствами. Тогда в R”2 существует ni-мерный правильный симплекс, противоречие.
Далее будем считать, что ni = П2- Снова предположим, что f - изоморфизм единичных дистанционных графов слоек Li и L2-
Пусть x,y € Li - две точки, такие, что у € Vx, |x — y^p = а.
Тогда, очевидно, существуют k € N, 5 > 0и z € L такие, что выполнено z € Нх, Hz — xlP = (k — ар)i/p, Hz — у||р = k.
Применим лемму 1 к слойкам Li,L2 и изоморфизму f. Тогда, полностью аналогично доказательству теоремы 4, мы получаем
f(z) €Н(Х), f(у) €V(Щ), |z — у н ₽ = Hf(z) — f(y)Hp = k;
Hf (z) — f (x)H, = Hz — x||„ = Ю ~аЩХ
Hf (x) — f (y)H„ = (Hf (z) — f (y)H’ — Hf (z) — f (x)H’)i/p = a.
Значит, f сохраняет расстояния между точками внутри вертикального множества {0}"1 х [0, Ei]m1, и при этом отображает его в некоторое вертикальное множество вида {0}”2 х [0,E2]m2- Поэтому диаметры (относительно соответствующих в на Li 11 L2) этих вертикальных множеств совпадают. Значит, е • т1/p = max Hx — y|L = max Hx — y|L = e •т^/.
i i х,уе[(Щ1Г1 y"p х,у е [0,^Г2 У"р 2 2
Таким образом, если выполнено условие (i3) или его частный случай (i2), то f не может быть изморфизмом. Теорема 5 доказана.
Исследование выполнено при поддержке Министерства науки и высшего образования Российской Федерации (государственное задание), проект № FSMG-2024-0025.