Хроматические числа метрических пространств и некоторые смежные задачи оптимизации

• Автор: Митричева, Ирина Михайловна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 77 с.

Оглавление
Обозначения
Введение

1 История вопроса, постановки задач и формулировки результатов

1.1 Оценки хроматических чисел пространств (К", /2) и (О71,12) при запрете одного и нескольких расстояний

1.1.1 Постановки задач

1.1.2 Известные безусловные результаты

1.1.3 Известные условные результаты

1.1.4 Новые безусловные результаты

1.1.5 Новые условные результаты

1.2 Оценки хроматических чисел пространств (К", А) и (О71, 1{) при запрете одного и нескольких расстояний
1.3 Изменение нижней оценки величины {а}) при „непрерывном“ изменении метрики ОТ 1 К І2
1.3.1 Известные результаты
1.3.2 Метрика Ді
1.4 Условные нижние оценки величины ук(Жп, 12] {а}) и числа Борсука
2 Доказательства теорем 7 и
2.1 Переформулировки задач на языке теории графов
2.2 Основные шаги доказательства теорем 7 и
2.3 Оптимизация оценок из раздела
2.3.1 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа Є
2.3.2 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа
2.3.3 Асимптотики нижних оценок хроматических чисел графов Є2 и завершение доказательств теорем

3 Доказательства оптимальных нижних оценок величины
Хм(М",/2; к) в случае к >
3.1 Метод получения оценок. Экстремальная задача
3.2 Численные результаты. Оценки хроматических чисел
4 Доказательства новых условных оценок хроматических чисел и комментарии к ним
4.1 Доказательства теорем
4.1.1 Доказательства теорем
4.1.2 Доказательство теоремы
4.2 Комментарии к доказательствам теорем
4.2.1 Несколько замечаний
4.2.2 Общий подход к получению условных оценок
5 Доказательство нижней оценки величины Хц(Мп, к] 2)
5.1 Доказательство теоремы
5.2 Получение нижних оценок величины Хц(Мгг, 1; к) в случае к >
6 Изменение нижней асимптотической оценки при „непрерывном“ изменении метрики ОТ К 2
6.1 Описание метода решения задачи и основная лемма
6.2 Формулировка экстремальной задачи
6.3 Решение экстремальной задачи
6.4 Практическая реализация алгоритма и новые результаты
7 Доказательство условных оценок величины х(Кп, 1%; {а}) и числа Борсука
7.1 Доказательство теоремы

Обозначения
• 1 — глава
• 1.2 — раздел 2 главы
• 1.2.3 — параграф 3 раздела 2 главы
• (Ж", І2) — евклидово пространство со стандартной метрикой
• (Q"j h) — пространство векторов с рациональными координатами с евклидовой метрикой
• (Жп, 1) — евклидово пространство с метрикой 1, где
МХ>У) = |®і -УіН Ь хп - Уп|
• (Q”> 1) — пространство векторов с рациональными координатами с метрикой 1
• < х, у > — скалярное произведение векторов в (Мп,/2)
• х * у — прямое произведение векторов
• а(п) х Ь(п) — существуют такие константы ci,c2 > 0, что при всех п выполнено сЬ(п) < а(п) < с2Ь(п)
• В записях вида
XhlC", к к) > (const + о( 1))п.
будут появляться различные значения константы const. Все они будут обозначаться С,к или
• В записях вида
xq(QV2; &)>(& +отбудут появляться различные значения константы const. Все они будут обозначаться £* или ££.

значение величины £(,1п і'0 4 4 У31п У3 окажется наименьшим. Отметим, что
все это делается „руками“, если числа у'0
2.3.2 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа (2г
Действуем в точности так же, как и в предыдущем параграфе: фиксируем параметры у'0
А'2 = {(АА1А2А3А4) ' А £ (0,1) V*, £д4 -А = 1, + 24 + 3+ 4 = р'2}.
Опять-таки, имеем систему уравнений
1 + 1п £3 + А3 + Л2 = О,
1 + 1п + Л1 + 2Л2 = О,
1 + 1п £3 4- Лг 4- ЗЛ2 — О,
1 + 1п Д + А1 + 4Л2 = О,
1 + 1п £ ц + А3 = О,
А 4” £4 4- 2 4” £3 4- £4 = 1,
£4 + 2 £'2 + З£3 4- 4£ = р2.
Преобразованиями, аналогичными проделанным на шаге 3 параграфа 2.3.1, получаем уравнение

4 3 р2 *1 2 р2 п
х4 + -—4-х3 + -—Цх2 +

' Р‘2
4 - р'2 4 - р'2

которое решаем по формулам Кардано. В результате для каждого вещественного корня х имеем

1 + X + X2 + X3 + Xі X3

1 + X + X2 + X3 + Xі ’

1 4- х 4- х2 4- х3 4- х4 ’ 4 1 4- х + х2 + х3 + х4 ’
У — і _ У
— С1 с2 с3 с4>
и остается выбрать тот х, для которого энтропия минимальна. Снова все это без усилий делается „руками“, и константа

(А)ЧА)ЧА)ЧА)ЧАУ<