Core forging and local limit theorems for the \(k\)-core of random graphs (Q2312608): Difference between revisions

This paper provides detailed distributional results for the \(k\)-core of a random graph with a given average degree. The emergence of the \(k\)-core in a random graph, that is, of the maximum subgraph that has minimum degree at least \(k\), has been a topic of intense activity in the theory of random graphs for the last 20 years or so. In [J. Comb. Theory, Ser. B 67, No. 1, 111--151 (1996; Zbl 0860.05065)], \textit{B. Pittel} et al. determined the critical value of the average degree of a random graph above which a (giant) \(k\)-core emerges for \(k>2\). The 2-core exhibits very different behavior as it amounts to the emergence of the first cycle in the random graph. This occurs with probability that is asymptotically bounded away from 0 for any positive but fixed average degree. However, a giant 2-core emerges together with emergence of the giant component. The classical approach to the study of the \(k\)-core has been the analysis of the peeling process in which starting from the random graph, one repeatedly removes from the random graph vertices of degree less than \(k\). The main result the present paper obtains is a bi-variate local limit theorem for the size and the order of the \(k\)-core. The authors use a novel method for the analysis of the \(k\)-core, which is based on the warning propagation algorithm that was introduced by physicists in the context of constrained satisfaction problems. Very briefly, in the present context a directed edge passes the message which indicates whether the source receives at least \(k-1\) other messages. The messages are updated repeatedly and eventually the process stabilises into a configuration of messages where those vertices that receive at least \(k\) edges form the core of the underlying graph. The paper gives a detailed description of the degrees between non-\(k\)-core vertices and \(k\)-core vertices and shows that the repeated message passing process converges to the limiting configuration of messages (which reveals the \(k\)-core) with a certain probability.