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.