RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2019 Volume 105, Issue 2, Pages 187–213 (Mi mzm11736)

This article is cited in 25 papers

A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics $\ell_1$ and $\ell_2$

L. I. Bogolubskya, A. M. Raigorodskiibacd

a Lomonosov Moscow State University
b Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
c Buryat State University, Ulan-Ude
d Caucasus Mathematical Center, Adyghe State University, Maikop

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 $\ell_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.

Keywords: chromatic number, chromatic number of a metric space, independence number, linear-algebraic method, distance graph.

UDC: 519.174.7

PACS: -

Received: 05.07.2017
Revised: 01.12.2017

DOI: 10.4213/mzm11736


 English version:
Mathematical Notes, 2019, 105:2, 180–203

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025