Large components in random induced subgraphs of \(n\)-cubes (Q1025930)

In this paper, a random subgraph of the \(n\)-dimensional cube \(Q_{n}\) (vertices all 0-1 vectors with \(n\) components, edges between two such vectors if and only if they differ in exactly one component) is formed by retaining each vertex with probability \(\lambda_{n}\) independently of all other vertices, and then taking the subgraph induced by the retained vertices. (Thus the resulting graph has expected number of vertices \(\lambda_{n}2^{n}\).) Such subgraphs have some applications in biology, described in the paper. The main focus of this paper is on \(C_{n}^{(1)}\), the largest component of this graph (which will, in the situations we are studying, be unique). Let \(\lambda_{n}=(1+\chi_{n})/n\). It had previously been known that if \(\chi>0\) is constant, then there is \(\kappa(\chi)>0\) such that \[ \lim_{n\rightarrow\infty} P(| C_{n}^{(1)}| =(1+o(1))\kappa(\chi) \lambda_{n}2^{n})=1. \] In other words, the largest component with high probability contains a positive proportion of the expected number of vertices. (It had also long been known that for \(\lambda_{n}=(1-\chi)/n\) where \(\chi>0\) is constant, the largest component would be of order \(O(n^{10})\), which is of course polylogarithmic relative to the number of vertices \(2^{n}\)). The main result of the paper somewhat refines the result `inside the phase transition'. In detail, suppose given \(\epsilon>0\) and \(\delta>0\). Suppose that \(\lambda_{n}=(1+\chi_{n})/n\) where \(\epsilon\geq \chi_{n}\geq n^{-1/3+\delta}\). Then there is a function \(\alpha(\epsilon)>0\) such that for \(\chi_{n}=\epsilon\) we have \[ \lim_{n\rightarrow\infty}P\left(| C_{n}^{(1)}| \sim \alpha(\epsilon)\frac{1+\epsilon}{n}2^{n}\text{ and }C_{n}^{(1)}\text{ is unique}\right)=1. \] And for \(o(1)=\chi_{n}\geq n^{-1/3+\epsilon}\), we have \[ \lim_{n\rightarrow\infty}P\left(| C_{n}^{(1)}| \sim 2\chi_{n}\frac{1+\chi_{n}}{n}2^{n}\text{ and }C_{n}^{(1)}\text{ is unique}\right)=1. \] The rough idea of the proof is to show first, using branching processes, that there is a good chance that each vertex of the random subgraph of \(Q_{n}\) is in a component of size at least \(\lfloor n^{2/3}/4\rfloor\), and to get a (smaller, but still decent) probability it is in a rather larger component. One also shows that the number of vertices not in one of these rather larger components is tightly concentrated: this leads, via more branching arguments, to the size of these rather larger components being pinned down asymptotically. A well-known group theoretic lemma shows existence of many short vertex-disjoint paths connecting the vertex boundaries of the rather larger components. These results, together with a process of selecting vertices in two rounds, give the result. The author states that the result generalises to \(n\)-cubes over any finite alphabet, rather than just a 2-letter one.