On the threshold for \(k\)-regular subgraphs of random graphs (Q2428631)

The random graph model used in this paper is Erdős-Rényi model \(\mathcal{G}(n,p)\). The \(k\)-core of a graph \(G\) is the unique largest subgraph of \(G\) of minimum degree at least \(k\). A \(k\)-factor of a graph is a spanning \(k\)-regular subgraph, and a graph is \(k\)-factor-critical if, whenever one deletes a vertex from the graph, one obtains a graph which has a \(k\)-factor. An event which occurs with probability tending to 1 as \(n \to \infty\) is said to be a.a.s. The following main theorem is proved in this paper. There exists an absolute constant \(k_0\) such that for \(k \geq k_0\) and constant \(c > c_{k+2}\) with \(c < k + 2\sqrt{k \log k}\), the \((k+2)\)-core of a random graph \(\mathcal{G}(n,c/n)\) is a.a.s. nonempty and either contains a \(k\)-factor or is \(k\)-factor-critical. The constant \(c_{k+2}\) was first defined in \textit{B.~Pittel}, \textit{J.~Spencer} and \textit{N.~Wormald} [J. Comb. Theory, Ser. B 67, No. 1, 111--151 (1996; Zbl 0860.05065)]. A corollary of the main theorem is the following statement. There esixts an absolute constant \(k_0\) such that for \(k \geq k_0\), \(\varepsilon > 0\) and any function \(p(n) > c_{k+2}(1+\varepsilon)/n\), the random graph \(\mathcal{G}(n,p)\) a.a.s. has a \(k\)-regular subgraph. Two conjectures are proposed in this paper. (i) There is a sharp threshold for the appearance of a \(k\)-regular graph in \(\mathcal{G}(n,p)\). (ii) The \((k+1)\)-core of a random graph, when it is a.a.s. nonempty, contains a \(k\)-factor or is \(k\)-factor critical a.a.s.