Large components in random induced subgraphs of n-cubes

Abstract

In this paper we study random induced subgraphs of the binary $n$-cube, $Q_2^n$. This random graph is obtained by selecting each $Q_2^n$-vertex with independent probability ${\lambda }_n$. Using a novel construction of subcomponents we study the largest component for ${\lambda }_n=\frac{1+{\chi }_n}{n}$, where $\epsilon \ge {\chi }_n\ge n^{-1/3+\delta }$, $\delta >0$. We prove that there exists a.s. a unique largest component $C_n^{(1)}$. We furthermore show that ${\chi }_n=\epsilon$, $|C_n^{(1)}|\sim \alpha (\epsilon )\frac{1+{\chi }_n}{n}{2}^n$ and for $o(1)={\chi }_n\ge n^{-1/3+\delta }$, $|C_n^{(1)}|\sim 2{\chi }_n\frac{1+{\chi }_n}{n}{2}^n$ holds. This improves the result of \cite{Bollobas:91} where constant ${\chi }_n=\chi$ is considered. In particular, in case of ${\lambda }_n=\frac{1+\epsilon }{n}$, our analysis implies that a.s. a unique giant component exists.

18 Pages

Cited by in corpus (1)

• Recombination and mutational robustness in neutral fitness landscapes