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

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Матем. сб., 2009, том 200, номер 6, страницы 3–22 (Mi msb6359)  

Эта публикация цитируется в 18 научных статьях (всего в 18 статьях)

Оценка хроматических чисел евклидова пространства методами выпуклой минимизации

Е. С. Горская, И. М. Митричева, В. Ю. Протасов, А. М. Райгородский

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

Аннотация: В работе изучаются хроматические числа евклидова пространства $\mathbb R^n$ с $k$ запрещенными расстояниями (т.е. числа, равные минимальным количествам цветов, в которые можно раскрасить все точки $\mathbb R^n$ так, что никакие две точки одного цвета не находятся на запрещенном расстоянии друг от друга). Получены оценки показателей асимптотического роста хроматических чисел при $n\to\infty$. Для этой цели использован разработанный ранее так называемый линейно-алгебраический метод, позволяющий свести задачу оценки хроматических чисел к некоторой экстремальной задаче. Для решения последней задачи в работе применен принципиально новый подход, основанный на теории выпуклых экстремальных задач и выпуклого анализа, что позволило получить искомые оценки для любых $k$. При этом для $k\le20$ эти оценки найдены в явном виде и являются неулучшаемыми в рамках указанного выше метода.
Библиография: 18 названий.

Ключевые слова: хроматическое число, дистанционный граф, выпуклая оптимизация.
Автор для корреспонденции

DOI: https://doi.org/10.4213/sm6359

Полный текст: PDF файл (588 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Sbornik: Mathematics, 2009, 200:6, 783–801

Реферативные базы данных:

УДК: 514.177.2+517.272+519.157
MSC: Primary 52C10, 51K05, 05C15; Secondary 05C12
Поступила в редакцию: 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

Цитирование в формате AMSBIB
\RBibitem{GorMitPro09}
\by Е.~С.~Горская, И.~М.~Митричева, В.~Ю.~Протасов, А.~М.~Райгородский
\paper Оценка хроматических чисел евклидова пространства методами выпуклой минимизации
\jour Матем. сб.
\yr 2009
\vol 200
\issue 6
\pages 3--22
\mathnet{http://mi.mathnet.ru/msb6359}
\crossref{https://doi.org/10.4213/sm6359}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2553072}
\zmath{https://zbmath.org/?q=an:05636162}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2009SbMat.200..783G}
\elib{http://elibrary.ru/item.asp?id=19066134}
\transl
\by E.~S.~Gorskaya, I.~M.~Mitricheva~(Shitova), V.~Yu.~Protasov, A.~M.~Raigorodskii
\paper Estimating the chromatic numbers of Euclidean space by convex minimization methods
\jour Sb. Math.
\yr 2009
\vol 200
\issue 6
\pages 783--801
\crossref{https://doi.org/10.1070/SM2009v200n06ABEH004019}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000269865000008}
\elib{http://elibrary.ru/item.asp?id=15312273}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-70350164286}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/msb6359
  • https://doi.org/10.4213/sm6359
  • http://mi.mathnet.ru/rus/msb/v200/i6/p3

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Kupavskiy A., “On the chromatic number of $\mathbb R^n$ with an arbitrary norm”, Discrete Math., 311:6 (2011), 437–440  crossref  mathscinet  zmath  isi  elib  scopus
    2. А. Б. Купавский, “О раскрасках сфер, вложенных в $\mathbb R^n$”, Матем. сб., 202:6 (2011), 83–110  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. B. Kupavskii, “On the colouring of spheres embedded in $\mathbb R^n$”, Sb. Math., 202:6 (2011), 859–886  crossref  isi
    3. И. М. Митричева, “О хроматическом числе для одной серии метрических пространств”, Матем. заметки, 91:3 (2012), 422–431  mathnet  crossref  mathscinet  elib; I. M. Mitricheva (Shitova), “On the Chromatic Number for a Set of Metric Spaces”, Math. Notes, 91:3 (2012), 399–408  crossref  isi  elib
    4. А. М. Райгородский, Д. В. Самиров, “Хроматические числа пространств с запрещенными одноцветными треугольниками”, Матем. заметки, 93:1 (2013), 117–126  mathnet  crossref  mathscinet  zmath  elib; A. M. Raigorodskii, D. V. Samirov, “Chromatic Numbers of Spaces with Forbidden Monochromatic Triangles”, Math. Notes, 93:1 (2013), 163–171  crossref  isi  elib
    5. Е. Е. Демёхин, А. М. Райгородский, О. И. Рубанов, “Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера”, Матем. сб., 204:4 (2013), 49–78  mathnet  crossref  mathscinet  zmath  adsnasa  elib; E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Sb. Math., 204:4 (2013), 508–538  crossref  isi
    6. А. Б. Купавский, А. М. Райгородский, “О препятствиях к реализации дистанционных графов с большим хроматическим числом на сферах малого радиуса”, Матем. сб., 204:10 (2013), 47–90  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. B. Kupavskii, A. M. Raigorodskii, “Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii”, Sb. Math., 204:10 (2013), 1435–1479  crossref  isi  elib
    7. С. Н. Попова, “Закон нуля или единицы для случайных дистанционных графов с вершинами в $\{-1,0,1\}^n$”, Пробл. передачи информ., 50:1 (2014), 64–86  mathnet; S. N. Popova, “Zero-one law for random distance graphs with vertices in $\{-1,0,1\}^n$”, Problems Inform. Transmission, 50:1 (2014), 57–78  crossref  isi
    8. Д. В. Самиров, А. М. Райгородский, “Новые оценки в задаче о хроматическом числе пространства с запрещенными равнобедренными треугольниками”, Докл. РАН, 456:3 (2014), 280–283  crossref  mathscinet  zmath  elib; D. V. Samirov, A. M. Raigorodskii, “New bounds for the chromatic number of a space with forbidden isosceles triangles”, Dokl. Math., 89:3 (2014), 313–316  crossref  mathscinet  zmath  isi  elib  scopus
    9. А. Е. Звонарёв, А. М. Райгородский, Д. В. Самиров, А. А. Харламова, “О хроматическом числе пространства с запрещенным равносторонним треугольником”, Матем. сб., 205:9 (2014), 97–120  mathnet  crossref  mathscinet  zmath  adsnasa  elib; A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “On the chromatic number of a space with forbidden equilateral triangle”, Sb. Math., 205:9 (2014), 1310–1333  crossref  isi
    10. А. Е. Звонарев, А. М. Райгородский, Д. В. Самиров, А. А. Харламова, “Улучшение теоремы Франкларë для о числе ребер гиперграфа с запретами на пересечения”, Докл. РАН, 457:2 (2014), 144–146  crossref  mathscinet  zmath  elib; A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “Improvement of the Frankl-Rödl theorem on the number of edges in hypergraphs with forbidden cardinalities of edge intersections”, Dokl. Math., 90:1 (2014), 432–434  crossref  mathscinet  zmath  isi  elib  scopus
    11. А. В. Бердников, А. М. Райгородский, “О хроматическом числе евклидова пространства с двумя запрещенными расстояниями”, Матем. заметки, 96:5 (2014), 790–793  mathnet  crossref  mathscinet  zmath  elib; A. V. Berdnikov, A. M. Raigorodskii, “On the Chromatic Number of Euclidean Space with Two Forbidden Distances”, Math. Notes, 96:5 (2014), 827–830  crossref  isi  elib
    12. Е. И. Пономаренко, А. М. Райгородский, “Новая нижняя оценка хроматического числа рационального пространства с одним и двумя запрещенными расстояниями”, Матем. заметки, 97:2 (2015), 255–261  mathnet  crossref  mathscinet  zmath  elib; E. I. Ponomarenko, A. M. Raigorodskii, “New Lower Bound for the Chromatic Number of a Rational Space with One and Two Forbidden Distances”, Math. Notes, 97:2 (2015), 249–254  crossref  isi
    13. С. Н. Попова, “Закон нуля или единицы для случайных подграфов некоторых дистанционных графов с вершинами в $\mathbb Z^n$”, Матем. сб., 207:3 (2016), 153–174  mathnet  crossref  mathscinet  adsnasa  elib; S. N. Popova, “Zero-one law for random subgraphs of some distance graphs with vertices in $\mathbb Z^n$”, Sb. Math., 207:3 (2016), 458–478  crossref  isi
    14. А. В. Бердников, “Оценка хроматического числа евклидова пространства с несколькими запрещенными расстояниями”, Матем. заметки, 99:5 (2016), 783–787  mathnet  crossref  mathscinet  elib; A. V. Berdnikov, “Estimate for the Chromatic Number of Euclidean Space with Several Forbidden Distances”, Math. Notes, 99:5 (2016), 774–778  crossref  isi
    15. С. Н. Попова, “Законы нуля или единицы для случайных графов с вершинами в булевом кубе”, Матем. тр., 19:1 (2016), 106–177  mathnet  crossref  mathscinet  elib; S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75  crossref
    16. А. В. Бердников, “Хроматические числа графов расстояний с несколькими запрещенными расстояниями без клик заданного размера”, Пробл. передачи информ., 54:1 (2018), 78–92  mathnet  elib; A. V. Berdnikov, “Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size”, Problems Inform. Transmission, 54:1 (2018), 70–83  crossref  isi
    17. Е. С. Горская, И. М. Митричева, “О хроматическом числе пространства $(\mathbb R^n, l_1)$”, Матем. сб., 209:10 (2018), 31–49  mathnet  crossref  elib; E. S. Gorskaya, I. M. Mitricheva, “The chromatic number of the space $(\mathbb R^n, l_1)$”, Sb. Math., 209:10 (2018), 1445–1462  crossref  isi
    18. Л. И. Боголюбский, А. М. Райгородский, “Замечание о нижних оценках хроматических чисел пространств малой размерности с метриками $\ell_1$ и $\ell_2$”, Матем. заметки, 105:2 (2019), 187–213  mathnet  crossref  elib; L. I. Bogolubsky, A. M. Raigorodskii, “A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics $\ell_1$ and $\ell_2$”, Math. Notes, 105:2 (2019), 180–203  crossref  isi
  • Математический сборник Sbornik: Mathematics (from 1967)
    Просмотров:
    Эта страница:791
    Полный текст:173
    Литература:41
    Первая стр.:24
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019