Asymptotic normality of the \(k\)-core in random graphs (Q930680): Difference between revisions

This article deals with the \(k\)-core \(\text{Core}_{k}\) of a graph, i.e. the largest induced subgraph with minimum degree \(k\) (not the cores encountered in algebraic graph theory). The aim is to consider the \(k\)-core in a random graph \(G(n,\lambda_{n}/n)\) (\(n\) labelled vertices, each possible edge present with probability \(\lambda_{n}/n\) independently of all others) where \(\lim_{n\rightarrow\infty}\lambda_{n}=\lambda\), and investigate the typical order of the \(k\)-core. Recall we say \(G(n,\lambda_{n}/n)\) has some property \textbf{whp} if \(\lim_{n\rightarrow\infty}P(G(n,\lambda_{n}/n)\text{~has~}\wp)=1\). In [\textit{B. Pittel, J. Spencer}, and \textit{N. C. Wormald}, ''Sudden emergence of a giant \(k\)-core in a random graph,'' J. Comb. Theory, Ser. B 67, No.1, 111-151 (1996; Zbl 0860.05065)] it is shown that, letting \(c_{k}=\inf_{\mu>0}/\psi_{k-1}(\mu)\) where \(\psi_{j}(\mu)=P(X\geq j)\) where \(X\) is a Poisson random variable with mean \(\mu\), then for \(\lambda<c_{k}\) \(\text{Core}_{k}\) is \textbf{whp} empty, but for \(\lambda>c_{k}\) the proportion of the vertices in \(\text{Core}_{k}\), \(v(\text{Core}_{k})/n\), \textbf{whp} converges in probability to \(\psi_{k}\mu_{k}(\lambda)\) where \(\mu_{k}(\lambda)>0\) is the largest solution of \(\mu/\psi_{k-1}(\mu)=\lambda\). Similarly \(e(\text{Core}_{k})/n\) converges in probability to \(\mu_{k}(\lambda)\psi_{k-1}(\mu_{k}(\lambda))/2\). The first main theorem of the paper under review, which develops earlier ideas of the authors [\textit{S. Janson} and \textit{M. J. Luczak}, ''A simple solution to the \(k\)-core problem,'' Random Struct. Algorithms 30, No. 1-2, 50-62 (2007; Zbl 1113.05091)], is that above this threshold \(c_{k}\) the joint distribution of the number of vertices and the number of edges have an asymptotically normal distribution. More precisely, if \(k\geq 2\) and \(\lambda>c_{k}\) then \[ n^{-1/2}\left(v(\text{Core}_{k})-\psi_{k}(\hat{\mu}_{n}),e(\text{Core}_{k}-\hat{\mu}_{n}\psi_{k-1}(\hat{\mu}_{n})n/2\right) \rightarrow (Z_{v},Z_{e}) \] the arrow denoting convergence in distribution and \(Z_{v}\) and \(Z_{e}\) being normal random variables with mean 0 and a well-understood, if rather complicated, variance-covariance matrix. Here \(\hat{\mu}_{n}=\mu_{k}(\lambda_{n})\). There is a companion result for what happens at the threshold. Basically, if \(k\geq 3\) and \(\lambda_{n}\rightarrow c_{k}\), then if \(n^{1/2}(\lambda_{n}-c_{k})\rightarrow -\infty\) then \(\text{Core}_{k}\) is \textbf{whp} empty: if \(n^{1/2}(\lambda_{n}-c_{k})\rightarrow \gamma \in (-\infty,\infty)\) then the probability that the core is non-empty tends to a certain value of the distribution function of a standard normal depending on (inter alia) \(\gamma\): and if \(n^{1/2}(\lambda_{n}-c_{k})\rightarrow \infty\) then the \(k\)-core is \textbf{whp} non-empty and suitable normalisations of the numbers of vertices and edges converge to two different multiples of the same standard normal. A vague idea of the complex proof is that the process of finding the core is turned into a balls-in-bins process and results on the convergence of empirical distributions of independent random variables are used to show that key random variables associated with the process are asymptotically Gaussian. A martingale limit theorem from [\textit{J. Jacod} and \textit{A. N. Shiryaev}, Limit Theorems for Stochastic Processes. Grundlehren der Mathematischen Wissenschaften, 288. (Berlin) etc.: Springer-Verlag. (1987; Zbl 0635.60021)] plays an important role. Thereafter, deducing that the normalised orders and sizes of the cores are also Gaussian is \` straightforward although the details are time-consuming\' . There are similar results for random graphs \(G(n,m)\) with \(m\) edges. The authors express hope that their techniques may illuminate other remaining issues about cores in random graphs, e.g. the magnitude of the variations in the size of the first non-empty \(k\)-core.