Large components in random induced subgraphs of n-cubes

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=ϵ$, $| C_n^{(1)}|\sim \alpha(\epsilon) \frac{1+\chi_n}{n} 2^n$andfor$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+ϵ}{n}$, our analysis implies that a.s. a unique giant component exists.