Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube (Q858140): Difference between revisions

The paper is the 3rd part of the sequel of the same authors on random subgraphs of finite graphs, [Random Struct. Algorithms 27, No. 2, 137--184 (2005; Zbl 1076.05071)] and [Ann. Probab. 33, No. 5, 1886--1944 (2005; Zbl 1079.05087)]. Here the finite graph is the \(n\)-cube, where the number of points \(V=2^n\). The edges of the cube are selected independently with probability \(p\). The main problem is to establish the size of the largest component, \(| \mathcal C_{\max}| \), of the arising subgraph. Earlier studies, \textit{P. Erdős} and \textit{J. Spencer} [Comput. Math. Appl. 5, 33--39 (1979; Zbl 0399.05041)] showed if \(p=n^{-1}(1+\varepsilon)\) and \(\varepsilon <0\) then \(| {\mathcal C}_{\max}| =o(V)\), and conjectured \(| {\mathcal C}_{\max}| =\theta(V)\) for \(\varepsilon >0\). This conjecture was proved by \textit{M. Ajtai, J. Komlos} and \textit{E. Szemerédi} [Combinatorica 2, 1--7 (1982; Zbl 0489.05053)] introducing a method coined as ``sprinkling''. In the present paper the finer behavior of phase transition is sought, using the sprinkling it is shown that \(| {\mathcal C}_{\max}| =2\varepsilon^{-2}\log V(1+o(1))\) a.\ a.\ s.\, when \(\varepsilon \leq -(\log n)^2(\log \log n)^{-1}n^{-1/2}\), and \(| {\mathcal C}_{\max}| =2\varepsilon V(1+o(1))\) a.\ a.\ s.\, when \(\varepsilon \geq 60(\log n)^3 n^{-1}\). (Here a.\ a.\ s.\ stands for the asymptotically almost surely).