|
Эта публикация цитируется в 25 научных статьях (всего в 25 статьях)
Оценка хроматических чисел евклидова пространства методами выпуклой минимизации
Е. С. Горская, И. М. Митричева, В. Ю. Протасов, А. М. Райгородский Механико-математический факультет
Московского государственного университета им. М. В. Ломоносова
Аннотация:
В работе изучаются хроматические числа евклидова пространства $\mathbb R^n$ с $k$ запрещенными расстояниями (т.е. числа, равные минимальным количествам цветов, в которые можно раскрасить
все точки $\mathbb R^n$ так, что никакие две точки одного цвета не находятся на запрещенном расстоянии друг от друга). Получены оценки показателей асимптотического роста хроматических чисел при $n\to\infty$. Для этой цели использован разработанный ранее так называемый линейно-алгебраический метод, позволяющий свести задачу оценки хроматических чисел к некоторой экстремальной задаче. Для решения последней задачи в работе применен принципиально новый подход,
основанный на теории выпуклых экстремальных задач и выпуклого анализа, что позволило получить искомые оценки для любых $k$. При этом для $k\le20$ эти оценки найдены в явном виде
и являются неулучшаемыми в рамках указанного выше метода.
Библиография: 18 названий.
Ключевые слова:
хроматическое число, дистанционный граф, выпуклая оптимизация.
Поступила в редакцию: 05.05.2008 и 09.12.2008
Образец цитирования:
Е. С. Горская, И. М. Митричева, В. Ю. Протасов, А. М. Райгородский, “Оценка хроматических чисел евклидова пространства методами выпуклой минимизации”, Матем. сб., 200:6 (2009), 3–22; E. S. Gorskaya, I. M. Mitricheva (Shitova), V. Yu. Protasov, A. M. Raigorodskii, “Estimating the chromatic numbers of Euclidean space by convex minimization methods”, Sb. Math., 200:6 (2009), 783–801
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm6359https://doi.org/10.4213/sm6359 https://www.mathnet.ru/rus/sm/v200/i6/p3
|
Статистика просмотров: |
Страница аннотации: | 1042 | PDF русской версии: | 322 | PDF английской версии: | 32 | Список литературы: | 71 | Первая страница: | 24 |
|