О графах расстояний с большим хроматическим числом и без больших клик

Настоящая работа посвящена изучению свойств дистанционных графов в евклидовом пространстве. Удается доказать, в частности, существование графов расстояний c экспоненциально большим по величине размерности хроматическим числом и без клик размера 6. Кроме того, при заданном ограничении на мощность максимальной клики ищутся графы расстояний c экстремально большим хроматическим числом. Полученные оценки неулучшаемы в рамках предложенного метода, в котором вероятностная техника сочетается c линейно-алгебраическим подходом.
Библиография: 19 названий.