Borgs, Christian; Chayes, Jennifer T.; van der Hofstad, Remco; Slade, Gordon; Spencer, Joel Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube. (English) Zbl 1121.05108 Combinatorica 26, No. 4, 395-410 (2006). 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, P. Erdős and 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 M. Ajtai, J. Komlos and 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). Reviewer: András Pluhár (Szeged) Cited in 2 ReviewsCited in 27 Documents MSC: 05C80 Random graphs (graph-theoretic aspects) 82B43 Percolation Keywords:random graphs; phase transition, \(n\)-cube Citations:Zbl 1076.05071; Zbl 1079.05087; Zbl 0399.05041; Zbl 0489.05053 PDFBibTeX XMLCite \textit{C. Borgs} et al., Combinatorica 26, No. 4, 395--410 (2006; Zbl 1121.05108) Full Text: DOI arXiv