RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2017 Volume 53, Issue 4, Pages 3–15 (Mi ppi2249)

This article is cited in 10 papers

Coding Theory

Independence numbers of random subgraphs of some distance graph

N. M. Derevyanko, S. G. Kiselev

Moscow Institute of Physics and Technology (State University), Moscow, Russia

Abstract: The distance graph $G(n,2,1)$ is a graph where vertices are identified with twoelement subsets of $\{1,2,\dots,n\}$, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph $G_p(n,2,1)$ in the Erdős–Rényi model is obtained by selecting each edge of $G(n,2,1)$ with probability p independently of other edges. We find a lower bound on the independence number of the random subgraph $G_{1/2}(n,2,1)$.

UDC: 621.391.1+519.1

Received: 25.02.2017
Revised: 04.05.2017


 English version:
Problems of Information Transmission, 2017, 53:4, 307–318

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025