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

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






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


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

О. И. Рубанов

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

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

Аннотация: В этой работе мы изучаем хроматические числа графов расстояний (т.е. таких графов, где вершинам соответствуют точки пространства, а ребра проводятся только если вершины находятся на определенном расстоянии). Как известно, при росте размерности евклидова пространства ${\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
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021