Abstract:
We consider a class of graphs $G(n,r,s)=(V(n,r),E(n,r,s))$, defined as follows:
$$
\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}
$$
where $(x,y)$ is the Euclidean scalar product. We study random subgraphs $\mathcal G(G(n,r,s), p)$ with edges independently chosen from the set $E(n,r,s)$ with probability $p$ each. We find nontrivial lower and upper bounds on the clique number of such graphs.
Fulltext:
PDF file (202 kB)
