RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Узлы и теория представлений
13 мая 2014 г. 18:30, г. Москва, ГЗ МГУ, ауд. 14-03
 


Хроматические числа графов расстояний без больших клик

О. И. Рубанов

Московский государственный университет им. М. В. Ломоносова, механико-математический факультет

Количество просмотров:
Эта страница:23

Аннотация: В этой работе мы изучаем хроматические числа графов расстояний (т.е. таких графов, где вершинам соответствуют точки пространства, а ребра проводятся только если вершины находятся на определенном расстоянии). Как известно, при росте размерности евклидова пространства ${\mathbb R}^n$ его хроматическое число растет экспоненциально ($(1,239+o(1))^n\leqslant \chi({\mathbb R}^n)\leqslant(3+o(1))^n$). Мы показываем, что хроматическое число графов расстояний может расти экспоненциально даже с ограничением на размерность максимальной клики, а именно, существует последовательность графов в ${\mathbb R}^n$, в которых нет клик на 5 вершинах, но размерность которых растет экспоненциально. Мы также находим нижние оценки хроматического числа для графов с запретом на клики большего размера и для графов с несколькими запрещенными расстояниями.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017