Київський національний університет імені Тараса Шевченка

Олійник Богдана Віталіївна

УДК 519.11

ІЗОМОРФНІ ЗАНУРЕННЯ

І МЕТРИКА ГРОМОВА–ХАУСДОРФА

ДЛЯ СКІНЧЕННИХ МЕТРИЧНИХ ПРОСТОРІВ

(01.01.08 — математична логіка,

теорія алгоритмів і дискретна математика)

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико–математичних наук

Київ — 2002

Дисертацією є рукопис.

Роботу виконано в Київському національному

університеті імені Тараса Шевченка.

Науковий керівник: доктор фізико–математичних

наук, професор ПРОТАСОВ Ігор Володимирович, Київський

національний університет імені Тараса Шевченка, професор

кафедри дослідження операцій

Офіційні опоненти: доктор фізико–математичних наук,

професор ЛЕВИТСЬКА Аліна Олександрівна, Міжнародний

Соломонів Університет, м.Київ, професор кафедри

вищої математики

доктор фізико–математичних наук, доцент БАНАХ

Тарас Онуфрійович,

Львівський національний університет імені Івана Франка,

доцент кафедри алгебри і топології

Провідна установа: Одеський державний університет

ім.І.І.Мечникова МОН України, м.Одеса

Захист відбудеться “ 24 ” травня 2002 року о 14 год. на засіданні

спеціалізованої вченої ради Д 26.001.18 при Київському національному

університеті імені Тараса Шевченка за адресою:

03127, м. Київ-127, проспект Академіка Глушкова, 6,

механіко-математичний факультет.

З дисертацією можна ознайомитися в бібліотеці Київського

національного університету імені Тараса Шевченка

(вул. Володимирська, 58).

Автореферат розіслано “3” квітня 2002 року.

Вчений секретар

спеціалізованої вченої ради ПЛАХОТНИК В.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Скінченні метричні простори є одним із основних об’єктів дискретної математики. Основні поняття і результати теорії скінченних метричних просторів широко використовуються нині в геометричній теорії чисел, теорії кодування, теорії графів, теоретичних основах сучасного програмування, математичній теорії експертних оцінок тощо. Перші роботи з теорії скінченних метричних просторів появилися ще в 30–х роках минулого століття в зв’язку з проблемою ізометричної зображуваності довільних метрик в евклідових просторах . Menger K. New foundations of euclidean geometry// Amer. J. of Math. 1931. V.53.– p.721–745. von Neumann J., Shoenberg I.J. Fourier integrals and metric geometry// Trans. of the AMS. 1941. V.50.– p.226–251. Shoenberg I.J. Remarks to Maurice Frechet’s article// Ann. Math. V.36. 1935. P.724-732. Shoenberg I.J. On certain metric spaces arising from Euclidean spaces by a change of metric and their imbedding in Hilbert space// Annals of Math. 1937. V.38.– p.787–793. Проблематика ізометричної зображуваності одних метричних просторів іншими і досьогодні залишається однією з центральних в теорії скінченних метричних просторів.

Хоча поняття ізометричності є базовим в теорії метричних просторів, для багатьох цілей — наприклад, в деяких задачах теорії експертних оцінок, теорії асоціативних схем, тощо — відношення ізометричності можна замінювати більш грубими відношеннями. Основним з них є поняття ізоморфності метричних просторів. Два метричні простори називають ізоморфними, якщо існує бієкція одного з них на інший, яка зберігає рівності і строгі нерівності між парами точок. Для скінченних метричних просторів це поняття виявилось рівносильним так званим перетворенням метрик за допомогою функції шкали. Перетворення метрик за допомогою функції шкали було введено в 30–х роках минулого століття Shoenberg I.J. Metric space and completely monotone functions// Ann. Math. V.39. 1938. P.811-841. Wilson W.A. On certain types of continuous transformations of metric spaces// Amer. J. of Math. 1935. V.57.– p.62–68.. Воно, зокрема, дозволяє вивчати геометричні властивості метричних просторів, пов’язані з тернарним відношенням "точка . лежить між точками .", і тому перше важливе застосування це поняття знайшло в дослідженнях з дистанційної геометрії. Основні результати, отримані в цьому напрямку, підсумовано у відомій монографії Л.Блюменталя Blumental L.M. Theory and applications of distance geometry. New York: Chelsea, 1970.- 612p.. Численні результати, отримані за 60 років розвитку теорії скінченних метричних просторів, було відображено в енциклопедичній монографії М.Деза і М.Лоран Deza M.M., Laurent M. Geometry of cuts and metrics. Berlin: Springer, 1997.– 588p. — список літератури про скінченні метричні простори в якій є практично повним і складає близько 450 найменувань.

Відношення ізоморфності для кожного натурального ділить клас всіх –точкових метричних просторів на скінченне число класів еквівалентності. При цьому ряд комбінаторних об’єктів, які природним чином пов’язані зі скінченним метричним простором (наприклад, його група ізометрій) залежать тільки від класу еквівалентності і не залежать від вибору конкретного представника цього класу. А тому виникає задача вибору в певному розумінні стандартних представників з класів ізоморфних між собою скінченних метричних просторів так, щоб у дослідженнях, де використовуються лише властивості класів ізоморфних метричних просторів, оперувати не з довільними скінченними просторами, а зі стандартними представниками класів, до яких вони належать.

У 1994 році відомий фахівець з дискретної математики, професор Дрезденського технічного університету Б.Гантер на конференції "Алгебра і комбінаторика, взаємодія і перспективи" (Дрезден–Кьонінгштайн) поставив проблему, чи можна в якості стандартних брати підпростори просторів Хемінга — одного з найбільш вивчених класів скінченних метричних просторів.

Ця проблема стала відправною точкою досліджень, викладених у дисертаційній роботі. Інша задача, яка розв’язується в роботі, пов’язана з вивченням метрики Громова–Хаусдорфа між скінченними метричними просторами. Метрика Хаусдорфа між підпросторами даного метричного простору є одним з основних понять теорії метричних просторів і широко використовується в сучасній геометрії Gromov M. Metric structures Riemannian and non–Riemannian spaces. Birkhдser Boston Inc.: Boston, MA, 1999. Fukaya K. Hausdorff convergence of Riemannian manifolds and its applications// Recent topics in differential and analytic geometry, p142–248. Academic Press: Boston, MA, 1990. теорії фракталів Edgar G.A. Measure, topology and fractal geometry. New–York: Springer, 1990.– 232p. тощо. На початку 80–х років минулого століття відомий французький математик М.Громов запропонував розглядати узагальнення метрики Хаусдорфа, впровадивши визначення відстані між довільними компактними метричними просторами Gromov M. Groups of polynomial growth and expanding maps// Inst. Hautes Йtudes Sci. Publ. Math., 1981, ?53, p.53–73.. Метрика Громова–Хаусдорфа насьогодні є ще маловивченою навіть у найпростіших випадках. Зокрема, маловивченим є простір усіх попарно неізометричних скінченних метричних просторів із метрикою Громова–Хаусдорфа. Однією з відомих гіпотез про цей простір є гіпотеза про те, що він є щільним у гільбертовому просторі ..

Починаючи з 60–х років минулого століття, в зв’язку із потребами застосувань, появляються численні роботи, де аналізується складність алгоритмів для обчислень зі скінченними метричними просторами Hakimi S.L., Yau S.S. Distance matrix of a graph and its realizability// Quart. J. of Appl. Math.,– 22, 1964,– p.305–317. Тылкин М.Е. Реализуемость матриц расстояний в единичных кубах// Проблемы кибернетики.962. Т.6.– с.31–42..

Оскільки дана дисертаційна робота стосується досліджень ізоморфних занурень скінченних метричних просторів у простори з тими чи іншими властивостями і вивчення метрики Громова–Хаусдорфа між скінченними метричними просторами, то все сказане вище служить обгрунтуванням актуальності проблематики дисертаційної роботи.

Зв’язок роботи з науковими програмами, планами, темами. Роботу виконано у відповідності до завдань науково–дослідної роботи 97054 “Розробка статистичного аналізу марківських процесів. Вивчення топології на групах” (номер державної реєстрації 0197U014611).

Мета роботи. Метою дисертаційної роботи є: —

побудувати конкретне занурення довільного –точкового метричного простору у метричний простір Хемінга . для деякого натурального ; —

ввести до розгляду і дослідити властивості мозаїк скінченних метричних просторів, описати їх групи ізометрій; —

побудувати метричні простори, які є універсальними щодо ізоморфних занурень скінченних просторів і мають властивості однорідності і локальної скінченності; —

охарактеризувати відстань Громова–Хаусдорфа між скінченними метричними просторами як відстань Хаусдорфа між певними їх ізометричними образами, визначити експоненту Громова–Хаусдорфа скінченного метричного простору і вивчити деякі її властивості.

Методи дослідження. У дисеpтацiйнiй pоботi викоpистовуються методи теоpiї скінченних метричних просторів, комбiнаторного аналізу, теорії груп підстановок, теорії складності обчислень.

Наукова новизна. Усі одержані наукові результати є новими. В дисертаційній роботі:

побудовано конкретне занурення довільного –точкового метричного простору у метричний простір Хемінга , де

введено до розгляду і досліджено властивості мозаїк скінченних метричних просторів, описано групи ізометрій мозаїк; —

побудовано метричні простори, які є універсальними щодо ізоморфних занурень скінченних просторів і мають властивості однорідності і локальної скінченності; —

знайдено відстань Громова–Хаусдорфа між скінченними метричними просторами як відстань Хаусдорфа між певними їх ізометричними образами, визначено експоненту Громова–Хаусдорфа скінченного метричного простору і вивчено деякі її властивості.

Практичне значення одержаних результатів. Результати дисеpтацiї є певним внеском в теорію скінченних метричних просторів. Запропоновані конструкції, встановлені твердження та техніка доведень можуть бути використані в дослідженнях з теорії скінченних метричних просторів та її застосуваннях у дискретній геометрії та теорії експертних оцінок.

Апробація результатів дисертації. Результати, отpиманi в дисеpтацiї, доповiдалися: на семiнаpi "Теоpiя гpуп та напiвгpуп" у Київському національному унiвеpситетi iменi Таpаса Шевченка; на алгебраїчному семiнарi Київського національного унiвеpситету iменi Таpаса Шевченка; на Всеукраїнськiй науковiй конференцiї "Розробка та застосування математичних методiв в науково–технiчних дослiдженнях" (Львiв, 1995); на П’ятiй Мiжнаpоднiй конфеpенцiї iменi академiка М.Кpавчука (Київ, 1996), а також на Першій (Слов’янськ, 1997) та Третій (Суми, 2001) мiжнаpодних алгебраїчних конфеpенцiях в Україні.

Публікації. Основнi pезультати дисеpтацiї опублiковано в 7 pоботах автора, список яких подано наприкінці автореферату. З них 4 — статтi у фахових виданнях i 3 — тези доповідей наукових конференцiй.

Особистий внесок здобувача. Всі pезультати дисеpтації отpимані автоpом самостійно.

Структура і об’єм роботи. Дисеpтаційна pобота складається зі вступу, чотиpьох pозділів, висновків і списку літеpатуpи, викладених на 124 стоpінках машинописного тексту. Список літеpатуpи містить 46 найменувань, викладених на 5 сторінках машинопису.

ОСНОВНИЙ ЗМІСТ

В першому розділі роботи наводяться необхідні теоретичні відомості, подається короткий огляд результатів інших авторів, близьких за проблематикою до теми дисертаційної роботи.

В першому параграфі розглядаються стандартні конструкції метричних просторів. Описано способи задання скінченних метричних просторів, наведено визначення основних метричних просторів, які використовуються як у загальній теорії, так і в її застосуваннях. Зокрема, розглянуто метричні простори, що визначаються графами, простори Хемінга, –степені гіперкуба, біотопні простори, простори Бера. Охарактеризовано групи ізометрій просторів Хемінга, –степенів гіперкуба, біотопних просторів та просторів Бера.

В другому параграфі розглядається ізометрична реалізація скінченних метричних просторів і вводиться поняття перетворення шкали. Виділено стандартні простори, в яких ізометрично реалізуються довільні метрики.

Сформульовано класичну теорему Блюменталя про умову ізометричної занурюваності –точкових (напів)метричних просторів у евклідові простори, яка формулюється в термінах граміана скінченного метричного простору. Наведено відомий результат Хертеля про ізометричну занурюваність довільного –точкового метричного простору у простір . всіх векторів . з метрикою

Обговорено також умови ізометричної занурюваності довільних скінченних метричних просторів у скінченновимірні –простори, –простори, ., гіперкуби та простори Хемінга. Наведено відомі твердження про занурення графів у гіперкуби та довільних скінченних метричних просторів з раціональнозначною метрикою в графи.

Вже при дослідженні умов ізометричної занурюваності одних метричних просторів у інші виникає потреба певним чином перетворювати метрику одного або другого простору. Найбільш уживаними є перетворення, що задаються шкалами. Шкалою може бути кожна неперервна монотонно зростаюча функція ., визначена при всіх . так, що .. Метрика . при цьому замінюється на .. Трансформація . метричного простору . взагалі кажучи метричним простором не буде. Проте для широкого класу функцій, зокрема для опуклих вгору, простір . буде метричним простором разом з .. За допомогою перетворення шкали вводиться поняття ізоморфізму метричних просторів. А саме, простори . і . називаються ізоморфними, якщо існує шкала . така, що .. Далі в параграфі 1.2 характеризуються основні типи ізоморфних перетворень: гомометрія метричних просторів, степеневі перетворення, перетворення Шьонберга та деякі інші. Перетворення шкали дають змогу змінити метрику так, щоб трансформований простір ізометрично занурювався у стандартні простори. Так виділяються евклідові шкали, .–шкали тощо. Найбільш дослідженим є клас евклідових шкал. Відомо наприклад, що не існує спільної евклідової шкали для всіх скінченних метричних просторів, але при довільному всі –елементні метричні простори, що визначаються графами, мають спільну евклідову функцію шкали (твердження 1.27).

В параграфі 1.3 поняття перетворення шкали для скінченних метричних просторів переформульовується в категорних термінах. А саме, відображення одного метричного простору в інший називається монотонним, якщо воно зберігає нерівності відстаней між парами точок. Клас всіх скінченних метричних просторів утворює категорію ., об’єктами якої є скінченні метричні простори, а морфізмами — їх монотонні відображення. Ізоморфізми категорії . є одночасно ізоморфізмами метричних просторів у сенсі перетворення шкали (твердження 2.1). Наводиться ряд тверджень, що характеризують властивості ізоморфізмів метричних просторів та їх ізоморфних занурень. Зокрема описано, як пов’язані між собою матриці відстаней ізоморфних просторів (твердження 2.2), їх групи ізометрій (твердження 1.31). Ненульові значення метрики кожного скінченного метричного простору утворюють зростаючу послідовність, яку називають його спектром. Наводиться відоме твердження про те, що кожен –точковий метричний простір, спектр якого має довжину , є iзоморфним простору зі спектром

Відношення ізоморфності є при кожному еквівалентністю на множині –точкових метричних просторів зі скінченною кількістю класів еквівалентності. Наводиться формула для визначення числа класів еквівалентності.

В параграфі 1.4 наводяться необхідні поняття і твердження з теорії складності алгоритмів. Використовується напівформалізований опис алгоритмів як процесів перетворення слів одного алфавіту на слова іншого алфавіту. Охарактеризовано поняття поліноміальної звідності однієї алгоритмічної задачі до іншої. Наведено визначення класів і , –повних і –важких алгоритмічних задач. Сформульовано ряд відомих тверджень про алгоритми поліноміальної складності для розв’язування задач теорії скінченних метричних просторів. Наведено класичні приклади –повних і –важких алгоритмічних задач в теорії ізометричних занурень скінченних метричних просторів.

Другий розділ дисертаційної роботи присвячено вивченню ізоморфних занурень скінченних метричних просторів у простори Хемінга та опису конструкцій –універсальних просторів, тобто метричних просторів, які містять ізоморфну копію кожного скінченного метричного простору. У параграфі 2.1 доводиться

Теорема 2.10. Кожен –точковий скінченний метричний простір можна ізоморфно занурити у простір Хемінга ., де

Ця теорема дає позитивну відповідь на відоме питання Б.Гантера про існування ізоморфних занурень довільних скінченних метричних просторів у простори Хемінга. Її доведення конструктивне, тобто занурення будується в явному вигляді. Воно визначається таким чином, що відстань між образами кожних двох точок із заданого метричного простору є парним числом. А тому із теореми 2.10 дістаємо

Наслідок 2.11 Довiльний –точковий метричний простiр можна iзоморфно занурити в напівгіперкуб ., де визначено вище.

Враховуючи теорему Фрухта про точну зображуваність скінченних груп автоморфізмами скінченних графів з теореми 2.10 одержуємо також

Наслідок 2.13 Довiльна скiнченна група iзоморфна групi всіх iзометрiй деякого пiдпростору певного простору Хемiнга.

Поряд із скінченними просторами Хемінга . можна розглядати також нескінченний простір Хемінга ., елементами якого є нескінченні .–вектори, майже всі координати яких нульові, а відстань між векторами є відстанню Хемінга. Простір . очевидним чином ізометричний простору всіх скінченних підмножин деякої зліченної множини, у якому відстань між двома підмножинами визначається як потужність симетричної різниці цих множин. Група ізометрій простору . описується за допомогою конструкції обмеженого добутку дій або, що те саме, обмеженого експоненціювання двох груп підстановок. При цьому обмеженим добутком дій груп підстановок . i . ми називаємо групу підстановок ., де . — це обмежений вінцевий добуток груп . і ., а дію . на . визначено рівністю

Теорема 2.15 Група iзометрiй . є обмеженим добутком дiй . i ., тобто вона iзоморфна обмеженому вiнцевому добутку ..

З теореми 2.10 як наслідок дістаємо

Теорема 2.17 Нескiнченний простiр Хемiнга . є .–унiверсальним метричним простором.

Зауважимо, що простір . є однорідним, але не локально скінченним, бо в ньому кожна куля радіуса, більшого одиниці, містить безліч точок.

В параграфі 2.3 розглядається загальна конструкція — з’єднання метричних просторів, яка дає змогу будувати локально скінченні (але не однорідні) –унiверсальні метричні простори.

Нехай . — родина метричних просторiв скiнченного дiаметра таких, що при .. Покладемо ., , і фiксуємо нескiнченну послiдовнiсть додатних дiйсних чисел так, щоб при довільному . мала місце нерiвнiсть

На об’єднанні

визначимо функцію d(x,y), поклавши

Функція є метрикою на , а простір ми називаємо з’єднанням просторів за допомогою послідовності , і позначаємо символом

Теорема 2.20 1) Нехай послiдовності i задовольняють умовi (2.4). Якщо для всiх таких , що ., вiдрiзок числової прямої з кiнцями в точках . i не мiстить жодного значення метрики просторiв ., то з’єднання та будуть iзоморфними.

2) З’єднання скiнченних просторiв . за допомогою послiдовностi . буде локально скiнченним простором тодi й тiльки тодi, коли послiдовнiсть . необмежена.

3) Якщо для будь-якого . не співпадає з жодним значенням метрик просторів , то група iзометрiй з’єднання попарно неізометричних просторів є декартовим добутком груп .

Враховуючи теорему 2.20 дістаємо

Теорема 2.21 Клас локально скiнченних метричних просторiв мiстить континуум багато -унiверсальних просторів. В цьому ж класі містяться -універсальні простори із тривіальною групою ізометрій.

З’єднання ультраметричних просторів буде ультраметричним простором, а тому цю конструкцію можна використати для побудови універсальних щодо занурень ультраметричних просторів.

Теорема 2.23 В класі локально скінченних ультраметричних просторів містяться простори, які є універсальними щодо ізоморфних занурень в них скінченних ультраметричних просторів.

В параграфі 2.4 описано алгоритм занурення довільного скінченного метричного простору, який задано своєю матрицею відстаней, у відповідний простір Хемінга, і оцінюється складність цього алгоритму.

В розділі 3 розглядаються конструкції мозаїк метричних просторів, які дозволяють будувати –універсальні метричні простори, що одночасно є локально скінченними і однорідними.

В параграфі 3.1 розглядаються скінченні мозаїки. Спочатку дається визначення розширення метричного простору . за допомогою простору ., який має скінченний діаметр . Для побудови розширення з кожною точкою зіставляється копія простору так, щоб при ., і розглядається об’єднання

При довільному . функція ., визначена на . рівністю

є метрикою, а метричний простір називається розширенням простору за допомогою простору . З точністю до ізоморфізму метричних просторів конструкція розширення не залежить від вибору константи . (лема 3.2). За допомогою конструкції розширення вводяться поняття мозаїки першого та другого роду даної висоти . А саме, нехай . ., — метричні простори такі, що . для ., — фіксовані числа, які задовольняють умовам .. Мозаїкою першого роду висоти називається метричний простір

Мозаїка другого роду висоти , складена з метричних просторів ,
. . скінченного діаметра з використанням чисел ., . . ., що задовольняють умовам ., ., визначається як простір

З точністю до ізоморфізму ці конструкції не залежать від вибору констант; їх можна описати, задаючи відповідним чином метрику на декартовому добутку . Мозаїки та . містять ізоморфні копії просторів., , але можуть і не містити ізометричних копій цих просторів.

Групи ізометрій метричних просторів та
описуються в термінах скінченно ітерованих вінцевих добутків.

Теорема 3.9 Для довільних скінченних метричних просторів . . . . група ізометрій мозаїки другого роду ізоморфна, як група підстановок, вінцевому добутку груп ізометрій цих просторів:

Теорема 3.10 Для довільних скінченних метричних просторів . . . . група ізометрій мозаїки першого роду ізоморфна, як група підстановок, вінцевому добутку груп ізометрій цих просторів, взятих у зворотному порядку:

В параграфі 3.2 вводяться до розгляду мозаїки над нескінченними родинами метричних просторів. Нехай . — нескінченна послідовність метричних просторів скінченного діаметра, причому для кожного . в просторі . виділено точку ., і нехай . — послідовність чисел така, що .. Для кожного . визначено канонічне занурення простору у простір , при якому образом є його копія, індексована елементом .. Маючи ланцюг занурень

можна побудувати граничний простір

який і називається мозаїкою, складеною з просторів . Група ізометрій мозаїки описується в термінах вінцевого добутку за нескінченною вліво послідовністю груп підстановок Иванюта И.Д. Силовские p–подгруппы счетной симметрической группы// УМЖ. Т.15,– №3,– 1963,– с.240–249..

Теорема 3.14 Група ізометрій мозаїки над послідовністю метричних просторів . ізоморфна як група підстановок вінцевому добутку за нескінченною послідовністю вліво груп ізометрій цих просторів

Основні властивості мозаїки даються в такому твердженні.

Теорема 3.15 Нехай є мозаїкою над послідовністю метричних просторів . Тоді

Мозаїка . містить ізоморфну копію кожного з просторів . ;

Простір . буде локально скінченним тоді й лише тоді, коли кожен з просторів є скінченним;

Простір буде однорідним тоді й тільки тоді, коли кожен з просторів є однорідним.

В параграфі 3.3 розглянуто деякі застосування конструкції мозаїк над нескінченною послідовністю метричних просторів.

Теорема 3.16 Для довільної необмеженої послідовності натуральних чисел . мозаїка ., складена з просторів Хемінга . є –універсальним однорідним локально скінченним простором.

Так побудований клас .–універсальних просторів є континуальним, про що свідчить

Теорема 3.19 Нехай зростаючі послідовності натуральних чисел . та . є різними. Тоді мозаїки і не ізоморфні між собою, але ізоморфно занурюються одна в одну.

Розділ 4 присвячено вивченню відстані Громова–Хаусдорфа між скінченними метричними просторами.

Нехай — скінченні метричні простори. Метрика , визначена на диз’юнктному об’єднанні називається допустимою для метрик . та ., якщо її звуження на множини . і . збігається з метриками . i . відповідно. Відстань Громова–Хаусдорфа між неізометричними просторами . і . визначається як інфімум за всіма допустимими метриками на відстаней Хаусдорфа між і у просторах .

Далі вводиться конструкція –з’єднання просторів , . Позначимо символом . клас відображень

для яких виконуються виконуються нерівності

Для відображення . .–з’єднання визначається як метричний простір на множині, яка утворюється з диз’юнктного об’єднання ототожненням тих елементів . і ., для яких ., з метрикою, визначеною рівністю

У теоремі 4.5 доведено, що існує таке .–з’єднання просторів . і ., в якому відстань Хаусдорфа між ізометричними образами цих просторів дорівнює відстані Громова–Хаусдорфа між . і ..

Теорема 4.7 Відстань Громова–Хаусдорфа . між скінченними метричними просторами . i . визначається рівністю

У параграфі 4.2 доведена

Теорема 4.8 Відстань Громова–Хаусдорфа між скінченними метричними просторами . задовольняє нерівності

Де , . — більший і менший з діаметрів просторів . і . відповідно.

Обчислено відстань Громова–Хаусдорфа між деякими типами метричних просторів. Зокрема, має місце така

Теорема 4.10 Нехай і . — еквідістантні скінченні метричні простори, ненульові значення метрики в яких рівні . і . відповідно, .. Тоді

В параграфі 4.3 вводиться до розгляду експонента Громова–Хаусдорфа скінченного метричного простору. .–експонентою простору . називається метричний простір, носієм якого є множина класів ізометричних підпросторів ., а метрика індукується метрикою Громова–Хаусдорфа. Наводяться основні властивості .–експоненти. Зокрема встановлено (теорема 4.13), що потужність .–експоненти .–точкового простору обмежена знизу числом ., а згори — числом ., а її діаметр не перевищує . (теорема 4.15). У теоремі 4.16 доведено, що .–експонента простору . буде еквідістантним простором в тому й лише тому разі, коли еквідістантним є простір .. Наведено приклад, який показує, що .–експоненти ізоморфних просторів можуть бути неізоморфні.

ВИСНОВКИ

У даній роботі наводиться конструкція ізоморфного занурення довільного скінченного метричного простору у деякий простір Хемінга. Описується алгоритм такого занурення і оцінюється його складність. На основі цієї конструкції будуються приклади однорідних або локально скінченних метричних просторів, універсальних щодо ізоморфних занурень в них довільних скінченних просторів.

Запропоновані дві конструкціі мозаїк за скінченною послідовністю метричних просторів і описано їх групи ізометрій в термінах скінченно ітерованих вінцевих добутків груп підстановок. Наведено конструкцію мозаїки за нескінченною послідовністю метричних просторів, описано групу ізометрій такої мозаїки. Побудовано континуальну родину попарно неізоморфних однорідних локально скінченних метричних просторів, кожен з яких містить ізоморфну копію довільного скінченного метричного простору.

Встановлено, що відстань Громова–Хаусдорфа між заданими скінченними метричними просторами рівна відстані Хаусдорфа між ізометричними образами цих просторів у деякому скінченному метричному просторі. Наведено оцінки для значення відстані Громова–Хаусдорфа між скінченними метричними просторами. Отримано явні формули для знаходження відстані Громова–Хаусдорфа між деякими типами метричних просторів. Визначено поняття експоненти Громова–Хаусдорфа скінченного метричного простору і досліджено деякі її властивості.

Автор висловлює подяку своєму науковому керівнику, професору Протасову І.В. за постійну увагу й підтримку в роботі.

СПИСОК РОБІТ АВТОРА ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Олійник Б.В. Універсальність зліченних просторів Хемінга щодо ізоморфних занурень// Вісник Київського університету. Сер. фіз.-мат. науки.- 1996.-в.2.- с.53-62.

2. Olijnyk B.V. Isomorphic embeddings of finite metric spaces into Hamming spaces// Matematychni Studii.- 1997.- v.8, №2.- p.176-179.

3. Олійник Б.В. Мозаїки метричних просторів// Доповіді НАН України, 1999,– №8, с.20–23.

4. Олійник Б.В. Експонента Громова–Хаусдорфа скінченного метричного простору// Вісник Київського університету. Сер. фіз.-мат. науки.- 2001.-в.3.- с.53-57.

5. Олiйник Б. Iзоморфнi занурення скiнченних метричних просторiв у простори Хемiнга// тези доповiдi на Всеукраїнськiй науковiй конференцiї "Розробка та застосування математичних методiв в науково-технiчних дослiдженнях" (Львiв 5-7 жовтня 1995 р.). С.39-40.

6. Олiйник Б. Злiченнi .–унiверсальнi метричнi простори// П’ята конференцiя пам’ятi М.Кравчука.  – Київ.– 1996.– Тези доповiдей. с.308.

7. Олийнык Б.В. Сплетения и расширения метрических пространств// Міжнародна алгебраїчна конференція, присвячена пам’яті професора Л.М.Глускіна. Київ.  – 1997.– с.60–61.

АНОТАЦІЇ

Олійник Б.В. Ізоморфні занурення і метрика Громова–Хаусдорфа для скінченних метричних просторів. — Рукопис.

Дисеpтацiя на здобуття наукового ступеня кандидита фiзико-математичних наук за спецiальнiстю 01.01.08 — математична логіка, теорія алгоритмів і дискретна математика. — Київський національний унiвеpситет iменi Таpаса Шевченка, м.Київ, 2002.

Дисертацію присвячено дослідженню ізоморфних занурень скінченних метричних просторів і вивченню властивостей відстані Громова-Хаусдорфа між скінченними метричними просторами.

Запропоновано конструкцію і описано алгоритм ізоморфного занурення довільного скінченного метричного простору у деякий простір Хемінга. Побудовано континуальну родину попарно неізоморфних однорідних локально скінченних метричних просторів, кожен з яких містить ізоморфну копію довільного скінченного метричного простору. Визначено поняття експоненти Громова–Хаусдорфа скінченного метричного простору і досліджено деякі її властивості.

Ключовi слова: простір Хемінга, ізоморфізм, ізоморфне занурення, група ізометрій, відстань Громова-Хаусдорфа, .–экспонента метричного простору.

Олийнык Б.В. Изоморфные погружения и метрика Громова–Хаусдорфа для конечных метрических пространств. — Рукопись.

Диссеpтация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.08 — математическая логика, теория алгоритмов и дискретная математика. — Киевский национальный унивеpситет имени Таpаса Шевченко, г.Киев, 2002.

Диссертация посвящена исследованию изоморфных погружений конечных метрических пространств и изучению свойств метрики Громова-Хаусдорфа между конечными метрическими пространствами.

Доказано, что каждое .–точечное метрическое пространство при фиксированном . изоморфно погружается в пространство Хеминга ., где . зависит только от .. Предложена явная конструкция такого погружения, описан алгоритм погружения и оценена его сложность. Теорема о погружении использована для построения локально конечных метрических пространств, содержащих изоморфные копии произвольных конечных метрических пространств.

Предложены конструкции мозаик над конечными и бесконечными последовательностями конечных метрических пространств, охарактеризовано основные свойства мозаик, описано их групы изометрий. С помощью конструкции мозаики над бесконечной последовательностью конечных метрических пространств построено континуальное семейство попарно неизоморфных локально конечных метрических пространств, обладающих дополнительным свойством однородности, каждое из которых содержит изоморфную копию произвольного конечного метрического пространства. Пространства принадлежащие указаному семейству, определяются как мозаики над последовательностью пространств Хеминга ., где . — возрастающая последовательность натуральных чисел.

При изучении свойств метрики Громова–Хаусдорфа на классе конечных метрических пространств установлено, что расстояние Громова–Хаусдорфа между двумя конечными метрическими пространствами совпадает с растоянием Хаусдорфа между их изометрическими копиями в подходящим образом сконструированом конечном метрическом пространстве. Приведены оценки для наибольших и наименьших значений расстояния Громова–Хаусдорфа между двумя конечными метрическими пространствами. Указаны формулы для нахождения этого расстояния между пространствами некоторых типов. Введено в расмотрение понятие экспоненты Громова–Хаусдорфа конечного метрического пространства, установлен ряд свойств этой конструкции.

Ключевые слова: пространство Хеминга, изоморфизм, изоморфное погружение, група изометрий, расстояние Громова-Хаусдорфа, .–экспонента метрического пространства.

Olijnyk B.V. Isomorphic embeddings and Gromov–Hausdorff metric of finite metric spaces. — Manuscript.

Thesis of a dissertation for obtaining the degree of candidate of sciences in physics and mathematics, speciality 01.01.08 — mathematical logic, algorithms theory and discrete mathematics. — Kyiv Taras Shevchenko University, Kyiv, 2002.

The dissertation is devoted to investigations of isomorphic embeddings of finite metric spaces and studying properties of Gromov–Hausdorff distance between finite metric spaces.

A construction of isomorphic embedding of arbitrary finite metric space into some Hamming space is presented and an algorithm of such embedding is described. A continuum family of such pairwise non-isomorphic homogenous locally finite metric spaces, that each of them contains an isomorphic copy of arbitrary finite metric space, is constructed. A notion of Gromov–Hausdorff exponent of finite metric space is defined and some of its properties are investigated.

Key words: Hamming space, isomorphism, isomorphic embedding, isometry group, Gromov–Hausdorff distance, .–exponent of metric space.