Аннотация:
В работе изучаются хроматические числа евклидова пространства Rn с k запрещенными расстояниями (т.е. числа, равные минимальным количествам цветов, в которые можно раскрасить
все точки Rn так, что никакие две точки одного цвета не находятся на запрещенном расстоянии друг от друга). Получены оценки показателей асимптотического роста хроматических чисел при n→∞. Для этой цели использован разработанный ранее так называемый линейно-алгебраический метод, позволяющий свести задачу оценки хроматических чисел к некоторой экстремальной задаче. Для решения последней задачи в работе применен принципиально новый подход,
основанный на теории выпуклых экстремальных задач и выпуклого анализа, что позволило получить искомые оценки для любых k. При этом для k⩽20 эти оценки найдены в явном виде
и являются неулучшаемыми в рамках указанного выше метода.
Библиография: 18 названий.
Образец цитирования:
Е. С. Горская, И. М. Митричева, В. Ю. Протасов, А. М. Райгородский, “Оценка хроматических чисел евклидова пространства методами выпуклой минимизации”, Матем. сб., 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
\RBibitem{GorMitPro09}
\by Е.~С.~Горская, И.~М.~Митричева, В.~Ю.~Протасов, А.~М.~Райгородский
\paper Оценка хроматических чисел евклидова пространства методами выпуклой минимизации
\jour Матем. сб.
\yr 2009
\vol 200
\issue 6
\pages 3--22
\mathnet{http://mi.mathnet.ru/sm6359}
\crossref{https://doi.org/10.4213/sm6359}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2553072}
\zmath{https://zbmath.org/?q=an:05636162}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2009SbMat.200..783G}
\elib{https://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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000269865000008}
\elib{https://elibrary.ru/item.asp?id=15312273}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-70350164286}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm6359
https://doi.org/10.4213/sm6359
https://www.mathnet.ru/rus/sm/v200/i6/p3
Эта публикация цитируется в следующих 25 статьяx:
Л. И. Боголюбский, А. М. Райгородский, “Замечание о нижних оценках хроматических чисел
пространств малой размерности с метриками ℓ1 и ℓ2”, Матем. заметки, 105:2 (2019), 187–213; L. I. Bogolubsky, A. M. Raigorodskii, “A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics ℓ1 and ℓ2”, Math. Notes, 105:2 (2019), 180–203
А. В. Бердников, “Хроматические числа графов расстояний с несколькими запрещенными расстояниями без клик заданного размера”, Пробл. передачи информ., 54:1 (2018), 78–92; 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
Е. С. Горская, И. М. Митричева, “О хроматическом числе пространства (Rn,l1)”, Матем. сб., 209:10 (2018), 31–49; E. S. Gorskaya, I. M. Mitricheva, “The chromatic number of the space (Rn,l1)”, Sb. Math., 209:10 (2018), 1445–1462
С. Н. Попова, “Закон нуля или единицы для случайных подграфов некоторых дистанционных графов с вершинами в Zn”, Матем. сб., 207:3 (2016), 153–174; S. N. Popova, “Zero-one law for random subgraphs of some distance graphs with vertices in Zn”, Sb. Math., 207:3 (2016), 458–478
А. В. Бердников, “Оценка хроматического числа евклидова пространства с несколькими запрещенными расстояниями”, Матем. заметки, 99:5 (2016), 783–787; A. V. Berdnikov, “Estimate for the Chromatic Number of Euclidean Space with Several Forbidden Distances”, Math. Notes, 99:5 (2016), 774–778
С. Н. Попова, “Законы нуля или единицы для случайных графов с вершинами в булевом кубе”, Матем. тр., 19:1 (2016), 106–177; S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75
А. В. Бердников, “Хроматическое число с несколькими запрещенными расстояниями в пространстве с ℓq-метрикой”, Совр. матем. и ее приложения, 100 (2016), 12–18; A. V. Berdnikov, “Chromatic number with several forbidden distances in the space with the ℓq-metric”, Journal of Mathematical Sciences, 227:4 (2017), 395–401
Е. И. Пономаренко, А. М. Райгородский, “Новая нижняя оценка хроматического числа рационального пространства с одним и двумя запрещенными расстояниями”, Матем. заметки, 97:2 (2015), 255–261; 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
Gil Kalai, Surveys in Combinatorics 2015, 2015, 147
С. Н. Попова, “Закон нуля или единицы для случайных дистанционных графов с вершинами в {−1,0,1}n”, Пробл. передачи информ., 50:1 (2014), 64–86; 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
Д. В. Самиров, А. М. Райгородский, “Новые оценки в задаче о хроматическом числе пространства с запрещенными равнобедренными треугольниками”, Докл. РАН, 456:3 (2014), 280–283; 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
А. Е. Звонарёв, А. М. Райгородский, Д. В. Самиров, А. А. Харламова, “О хроматическом числе пространства с запрещенным равносторонним треугольником”, Матем. сб., 205:9 (2014), 97–120; 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
А. Е. Звонарев, А. М. Райгородский, Д. В. Самиров, А. А. Харламова, “Улучшение теоремы Франкларë для о числе ребер гиперграфа с запретами на пересечения”, Докл. РАН, 457:2 (2014), 144–146; 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
А. В. Бердников, А. М. Райгородский, “О хроматическом числе евклидова пространства с двумя запрещенными расстояниями”, Матем. заметки, 96:5 (2014), 790–793; A. V. Berdnikov, A. M. Raigorodskii, “On the Chromatic Number of Euclidean Space with Two Forbidden Distances”, Math. Notes, 96:5 (2014), 827–830
А. М. Райгородский, Д. В. Самиров, “Хроматические числа пространств с запрещенными одноцветными треугольниками”, Матем. заметки, 93:1 (2013), 117–126; A. M. Raigorodskii, D. V. Samirov, “Chromatic Numbers of Spaces with Forbidden Monochromatic Triangles”, Math. Notes, 93:1 (2013), 163–171
Е. Е. Демёхин, А. М. Райгородский, О. И. Рубанов, “Дистанционные графы, имеющие большое хроматическое число
и не содержащие клик или циклов заданного размера”, Матем. сб., 204:4 (2013), 49–78; 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
А. Б. Купавский, А. М. Райгородский, “О препятствиях к реализации дистанционных графов с большим хроматическим числом на сферах малого радиуса”, Матем. сб., 204:10 (2013), 47–90; 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
Д. В. Самиров, А. М. Райгородский, “Новые нижние оценки хроматического числа пространства с запрещенными равнобедренными треугольниками”, Итоги науки и техн. Сер. Соврем. мат. и ее прил. Темат. обз., 125 (2013), 252–268; D. V. Samirov, A. M. Raigorodskii, “New lower bounds for the chromatic number of a space with forbidden isosceles triangles”, J. Math. Sci. (N. Y.), 204:4 (2015), 531–541
Andrei M. Raigorodskii, Thirty Essays on Geometric Graph Theory, 2013, 429
И. М. Митричева, “О хроматическом числе для одной серии метрических пространств”, Матем. заметки, 91:3 (2012), 422–431; I. M. Mitricheva (Shitova), “On the Chromatic Number for a Set of Metric Spaces”, Math. Notes, 91:3 (2012), 399–408
Цитирование в формате AMSBIB
Обратная связь: