Проблемы Борсука и Нелсона-Хадвигера в рациональных пространствах

• Автор: Пономаренко, Екатерина Игоревна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 60 с. : ил.

Оглавление

Список основных обозначений

Введение

Глава 1 Верхняя оценка числа независимости графов

1.1 Теорема Франкла-У ил сона

1.2 Улучшение теоремы Франкла-Уилсона

1.2.1 Формальное доказательство

Схема доказательства

Первый этап
Второй этап
Третий этап
1.2.2 Комментарии к доказательству
1.3 Обобщение теоремы Франкла-Уилсона на случай (—1, 0,1)-векторов и ее улучшение
1.4 Приложения в задаче Нелсона-Эрдеша-Хадвигера
Глава 2 Хроматическое число рационального пространства
2.1 Определение хроматического числа рационального пространства
2.2 Новая нижняя оценка хроматического числа рационального пространства с одним запрещенным расстоянием
2.3 Новая нижняя оценка хроматического числа рационального пространства с двумя запрещенными расстояниями
2.4 Хроматическое число аффинно-рационального пространства
Глава 3 Некоторые аналоги задачи Борсука
3.1 Задача Борсука для вещественного и рационального пространства
3.2 Правильный аналог задачи Борсука для рационального пространства
3.3 Размерности контрпримеров
3.3.1 Случай п ^ 903 (п ^ 946)
3.3.2 Случай п Є [561,757]
3.4 Обобщение на случай метрики 1Р

Заключение
Список литературы

Список основных обозначений
N — множество натуральных чисел;
Q — множество рациональных чисел;
Q[ti, хп — пространство многочленов от п переменных с рациональными коэффициентами;
К — множество действительных чисел;
|Л| — мощность конечного множества Л;
[а] — целая часть числа а;
аЬ — свойство “а делит 6”, т.е. число а является делителем числа Ь;
(х, у) — евклидово скалярное произведение векторов х и у;
|х| — норма вектора х в евклидовом пространстве;
V(G) — множество вершин графа G;
E(G) — множество ребер графа G;
f(N) = o(g(N)) — для любого числа с > 0 существует такое число Nq, что для любого N> N0 выполнено неравенство |/(Л0| ^ с|^(А/-) |;
f(x) д(х) — функции асимптотически равны при х -э со, то есть f(x) = д(х) • (1 + о(1));
г(х, у) — расстояние между точками х, у в метрике г;
1(Х) — индикатор события X. То есть I(X) = 1 в случае, если X выполняется, и 0 — иначе;
а = b( mod к) — а сравнимо с b по модулю к, то есть а и b дают одинаковые остатки при делении на к;

оригинальной статье [89]), которая приводит к оценке

1;4) > x(Gn) > ,
. io'-hW.ia'-U'.

■4 = {(го, *i, iii гз, ч) : *о + Ч + *2 + гз + *4 = n, i + 2ii + Згз + Агц ^ q — 1}.
С помощью численных методов в статье [89] показано, что для оптимизации оценки нужно брать при п —» оо
Но ~ v'0n, Hi ~ v[n, V2 ~ v'2п, Нз ~ Нзгг, Н4 ~ Н4П,
причем,если
Но = 0.020 ..., н( = 0.173 ..., v'2 = 0.420 ..., Н3 = 0.313 ..., v = 0.
то имеем в аккурат
Хк(^"; 4) ^ x{Gn) ^ (Сб + °(1))"-
Итак, пусть {njj+4 — та самая последовательность размерностей и графы GHt отвечают оптимальным параметрам, описанным выше. Тогда по формуле Стирлинга имеем
IKJ = (у + 0(1))”' = (3.674... + о(1)Г.
Зафиксируем один из графов и для краткости обозначим его просто Gn. Рассмотрим новый граф G = (Vn,E), у которого
ЕП = (Iх, У> : Iх — у| € {а2, а3}} = {{Х,У> : (х,у) € {s - 2q,s - 3q}}.
К сожалению, мы не знаем его числа независимости. Но мы можем предположить, что с некоторым р (мы позже выберем это число оптимально) выполнено a(G]г) < рп. Если предположение верно, то, разумеется,
ХК(М»;2)>х(С^-Щт^ (- + 0(1)") ,
®{Gn) Р )
откуда
ЫМП;2) + о(1).

При этом, безусловно.
1; 2) ^ Сз + °(1)>