Аннотация:
Рассматривается класс графов $G(n,r,s)=(V(n,r),E(n,r,s))$, определенных следующим образом:
$$
\begin{aligned}
& V(n,r)=\{\boldsymbol x=(x_1, x_2,\dots,x_n)\colon x_i\in\{0,1\},\ x_1+x_2+\dots+x_n=r\},\\
& E(n,r,s)=\{\{\boldsymbol x,\boldsymbol y\}\colon(\boldsymbol x,\boldsymbol y)=s\},
\end{aligned}
$$
где $(x,y)$ – евклидово скалярное произведение. Изучаются случайные подграфы $\mathcal G(G(n,r,s), p)$, ребра в которых выбираются независимо из множества $E(n,r,s)$, каждое с вероятностью $p$. Найдены нетривиальные нижние и верхние оценки кликового числа таких графов.
УДК:
621.391.1+519.1
Поступила в редакцию: 18.12.2017 После переработки: 23.03.2018