Email this article A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics ℓ1 and ℓ2
- Authors: Bogolyubsky L.I.1, Raigorodskii A.M.2,1,3,4
-
Affiliations:
- Lomonosov Moscow State University
- Moscow Institute of Physics and Technology (State University)
- Adygeya State University
- Buryat State University
- Issue: Vol 105, No 1-2 (2019)
- Pages: 180-203
- Section: Article
- URL: https://journal-vniispk.ru/0001-4346/article/view/151543
- DOI: https://doi.org/10.1134/S000143461901022X
- ID: 151543
Cite item
Open Access
Access granted
Subscription Access
Abstract
A particular class of estimates related to the Nelson–Erdős–Hadwiger problem is studied. For two types of spaces, Euclidean and spaces with metric ℓ1, certain series of distance graphs of small dimensions are considered. Independence numbers of such graphs are estimated by using the linear-algebraic method and combinatorial observations. This makes it possible to obtain certain lower bounds for the chromatic numbers of the spaces mentioned above and, for each case, specify a series of graphs leading to the strongest results.
About the authors
L. I. Bogolyubsky
Lomonosov Moscow State University
Author for correspondence.
Email: lev.bogolubsky@gmail.com
Russian Federation, Moscow, 119991
A. M. Raigorodskii
Moscow Institute of Physics and Technology (State University); Lomonosov Moscow State University; Adygeya State University; Buryat State University
Author for correspondence.
Email: mraigor@yandex.ru
Russian Federation, Dolgoprudnyi, Moscow Oblast, 141701; Moscow, 119991; Maikop, 385016; Ulan-Ude, 670000
Supplementary files
