Статья «Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов, "Математический сборник"»

Работа связана с классической задачей Нелсона Хадвигера о поиске хроматического числа дистанционных графов в . В основном мы рассматриваем класс графов , определeнных так: \begin{gather*} V(n, r)=\{\mathbf{x}=(x_1, ,x_n) : x_i\in\{0, 1\}, x_1+ +x_n=r\}, E(n,r,s)=\{\{\mathbf{x}, \mathbf{y}: (\mathbf{x}, \mathbf{y})=s\}\}, \end{gather*} где евклидово скалярное произведение. В частности, хроматическое число недавно было найдено Й. Балогом, А. В. Косточкой, А. М. Райгородским. Мы изучаем случайные подграфы , ребра в которых выбираются независимо из множества каждое с вероятностью . Найдены нетривиальные нижние и верхние оценки числа независимости и хроматического числа таких графов. В случае, когда есть степень простого числа и , удалось установить порядок и .Библиография: 51 название.