×

Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube. (English) Zbl 1121.05108

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).

MSC:

05C80 Random graphs (graph-theoretic aspects)
82B43 Percolation
PDFBibTeX XMLCite
Full Text: DOI arXiv