The convergence of the exploration process for critical percolation on the \(k\)-out graph (Q888448)

This paper studies critical percolation on the \(k\)-out graph \(G_{\mathrm{out}}(n,k)\) of order \(n\) via the analysis of exploration process, which explores open clusters of \(G_{\mathrm{out}}(n,k)\). This graph is undirected, and it can be derived from a directed version, which is constructed by adding uniformly at random \(k\) out-going edges to each vertex. The percolation process is performed by keeping each edge open with probability \(p\) and closed with probability \(1-p\) independently. The critical probability is shown to be \(p_c=1/(k+\sqrt{k^2-k})\). Moreover, the size of the largest component is of order \(O(\log n)\) in the subcritical phase, and \(O(n)\) in the supercritical phase. Some results are reminiscent of the classical random graph \(G(n,p)\).