Abstract:
The present paper is devoted to the study of the properties of distance graphs in Euclidean space. We prove, in
particular, the existence of distance graphs with chromatic number of exponentially large dimension and without cliques of dimension 6. In addition, under a given constraint on the cardinality of the maximal clique, we search for distance graphs with extremal large values of the chromatic number. The resulting estimates are best possible within the framework of the proposed method, which combines probabilistic techniques with the linear-algebraic approach.
Keywords:distance graph, chromatic number, clique, Stirling's formula, Euclidean space, probability space, random variable, expectation.
Fulltext:
PDF file (563 kB)
