Новая верхняя оценка хроматического числа случайного подграфа дистанционного графа

Эта работа связана с классической проблемой Нельсона–Хадвигера о нахождении хроматических чисел дистанционных графов в ${\mathbb R}^n$. Мы рассматриваем класс графов $G(n,2s+1,s)=(V(n,2s+1), E(n,2s+1,s))$, определенных следующим образом:
\begin{align*} V(n,2s+1)&=\{x=(x_1,x_2,\dots,x_n): x_i\in \{0,1\}, \, x_1+x_2+\dots+x_n=2s+1\}, \\ E(n,2s+1,s)&=\{\{x,y\}:(x,y)=s\}, \end{align*}
где $(x,y)$ обозначает скалярное произведение. Мы изучаем случайный граф ${\mathcal G}(G(n,2s+1,s),p)$, каждое ребро которого независимо от других ребер берется из множества $E(n,2s+1,s)$ с вероятностью $p$. В данной статье мы докажем новую оценку для хроматического числа такого графа.
Библиография: 36 названий.