|
Problemy Peredachi Informatsii, 2018, Volume 54, Issue 2, Pages 73–85
(Mi ppi2267)
|
|
|
|
Large Systems
Clique numbers of random subgraphs of some distance graphs
A. S. Gusev Department of Mathematical Statistics and Random Processes,
Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
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.
Received: 18.12.2017 Revised: 23.03.2018
Citation:
A. S. Gusev, “Clique numbers of random subgraphs of some distance graphs”, Probl. Peredachi Inf., 54:2 (2018), 73–85; Problems Inform. Transmission, 54:2 (2018), 165–175
Linking options:
https://www.mathnet.ru/eng/ppi2267 https://www.mathnet.ru/eng/ppi/v54/i2/p73
|
Statistics & downloads: |
Abstract page: | 204 | Full-text PDF : | 40 | References: | 35 | First page: | 7 |
|