Large components in random induced subgraphs of n-cubes

AbstractIn this paper we study random induced subgraphs of the binary n-cube, Q2n. This random graph is obtained by selecting each Q2n-vertex with independent probability λn. Using a novel construction of subcomponents we study the largest component for λn=1+χnn, where ϵ≥χn≥n−13+δ, δ>0. We prove that there exists a.s. a unique largest component Cn(1). We furthermore show that for χn=ϵ, we have |Cn(1)|∼α(ϵ)1+χnn2n and for o(1)=χn≥n−13+δ, |Cn(1)|∼2χn1+χnn2n holds. This improves the result of [B. Bollobás, Y. Kohayakawa, T. Luczak, On the evolution of random boolean functions, Extremal Problems Finite Sets (1991) 137–156] where constant χn=χ is considered. In particular, in the case of λn=1+ϵn, our analysis implies that a.s. a unique giant component exists