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)$.