Sudden emergence of a giant \(k\)-core in a random graph (Q1924140)

The \(k\)-core of a graph is the largest subgraph of minimum degree \(\geq k\). Fix \(\delta\in(0,1)\), and let \(k\geq 3\); there is a \(\gamma_k\) and a \(p_k\) such that the following is true. For a random graph of \(n\) edges and \(m\) vertices, when \(m<\gamma_kn-n^{1-\delta}\), the \(k\)-core a. s. has \(o(n)\) vertices, while if \(m>\gamma_k+n^{1-\delta}\), the \(k\)-core a. s. has at least \(p_kn+o(n)\) vertices. And it's unlikely that you'll catch the graph in transition: even if \(|\gamma_kn-m|\leq n^{1-\delta}\), such a graph a. s. has a \(k\)-core of \(o(n)\) edges or \(p_k(n)n+o(n)\) edges. The difficult proof is in two parts. In the first, the authors consider a process that successively deletes edges adjacent to vertices of degree \(<k\); they link this process with a parameter, and show that a random process based on the parameter alone simulates the graph process and is nearly Markov. In the second, they use this process to estimate the size of the \(k\)-cores.