Dembo–Montanari-precision finite-size scaling for the $k$-core of sparse random graphs beyond the settled 2-core

Dembo and Montanari proved a sharp finite-size scaling theorem for the 2-core of random $l$-uniform hypergraphs with $l \ge 3$: in a window of width $n^{-1/2}$ around the percolation threshold, the probability that the core is non-empty admits an expansion whose first correction is of order $n^{-1/6}$, governed by the infimum of a two-sided Brownian motion with quadratic drift (Groeneboom's distribution). Their notes state that similar finite-size scaling results are expected for other phase transitions within the same class, naming $k$-core percolation on random graphs (with $k \ge 3$) and the pure literal rule threshold in random $k$-SAT (with $k \ge 3$), and pose as open the exact form of the term beyond $n^{-1/6}$ even in the settled 2-core case. For random graphs, Janson and Luczak resolved only the leading-order part: the emergence window has width $n^{-1/2}$ in the edge density, and the limiting non-emptiness probability is a Gaussian tail. This problem asks for the missing finer layer: the $n^{-1/6}$-level correction term (or a proof that none exists) together with the identification of the governing limiting process for the $k$-core of $G(n, \lambda/n)$ with $k \ge 3$, and, secondarily and optionally, the exact form of the term beyond $n^{-1/6}$ in the settled hypergraph 2-core expansion.

Background

A hypergraph consists of vertices and hyperedges, where each hyperedge is a set of vertices (an ordinary graph is the case of hyperedges of size 2). The 2-core of a hypergraph is its largest subhypergraph in which every vertex belongs to at least two hyperedges; equivalently, it is what remains after iteratively deleting every hyperedge containing a vertex of degree zero or one, a procedure called peeling (also known as leaf removal or stripping). More generally, the $r$-core of a hypergraph is the largest subhypergraph in which every vertex belongs to at least $r$ hyperedges, and for graphs one uses the analogous notion: the $k$-core is the largest induced subgraph of minimum degree at least $k$, again computable by iteratively deleting vertices of degree below $k$. For random graphs $G(n, \lambda/n)$ and random $l$-uniform hypergraphs, this peeling process undergoes an abrupt transition: below a critical density the core is empty with high probability, while above it a linear-size core appears suddenly. Pittel, Spencer and Wormald (1996) located the critical value $c_k$ for graph $k$-cores, and Molloy (2005) did the same for $r$-cores of random hypergraphs. Cores govern, among other things, the behavior of the pure literal rule in satisfiability and the decoding of low-density parity-check (LDPC) codes over the erasure channel, since peeling is exactly the iterative decoder. Finite-size scaling (FSS) asks for the sharp form of this transition for large but finite $n$: how wide is the critical window, and what is the probability law of the outcome inside it. Dembo and Montanari (2008) proved the benchmark FSS theorem for the 2-core of random $l$-uniform hypergraphs ($l \ge 3$): in the window $\rho_n = \rho_d + r n^{-1/2}$, the non-emptiness probability obeys $\Phi(-r\alpha_l) + \beta_l C \Phi'(-r\alpha_l) n^{-1/6} + O(n^{-\eta})$, where $\Phi$ is the standard Gaussian distribution function; the constant $C$ is determined by the distribution of $\inf_t X(t)$ for the limiting process $X(t) = \tfrac{1}{2}\tilde F t^2 + \sqrt{\tilde G}\, W(t)$, a two-sided Brownian motion $W$ with quadratic drift, an object whose zero set is Groeneboom's Brownian excursion process. The striking $n^{-1/6}$ correction (a sixth root of $n$) comes from the cube-root asymptotics of this infimum. In their 2009 lecture notes on Gibbs measures on sparse random graphs, Dembo and Montanari state that 'similar results are expected for other phase transitions within the same class, such as $k$-core percolation on random graphs (with $k \ge 3$), or the pure literal rule threshold in random $k$-SAT (with $k \ge 3$)'. They further state that the exact form of the term beyond $n^{-1/6}$ is an open problem even in the settled 2-core case. For random graphs the best verified result is Janson and Luczak (2008): if $n^{1/2}(\lambda_n - c_k) \to \gamma$ then $P(\mathrm{Core}_k \ne \varnothing) \to \Phi(\hat p^2 \gamma/\sigma)$, so the window width in the edge-density parameter is $n^{-1/2}$ and the leading limit is a Gaussian tail; they also proved a CLT for the edge count at which the core first appears and identified the fluctuation scale of the core order as $n^{3/4}$ at threshold. This resolves the leading order but not the FSS layer: no $n^{-1/6}$-type correction term and no limiting-process description (no analogue of the Brownian-motion-with-drift argument) is known for graph $k$-cores.

Problem Statement

Establish finite-size scaling at the precision of Dembo–Montanari for the $k$-core of sparse random graphs beyond the settled hypergraph 2-core case. Concretely: (1) For the random graph $G(n, \lambda_n/n)$ with fixed $k \ge 3$, writing $c_k$ for the Pittel–Spencer–Wormald threshold, Janson and Luczak proved that $n^{1/2}(\lambda_n - c_k) \to \gamma$ implies $P(\mathrm{Core}_k \ne \varnothing) \to \Phi(\hat p^2 \gamma/\sigma)$. Determine the next layer: prove or disprove that $P(\mathrm{Core}_k \ne \varnothing)$ admits an expansion $\Phi(\hat p^2 \gamma/\sigma) + A_k(\gamma)\, n^{-\theta} + o(n^{-\theta})$ inside the $n^{-1/2}$ window for an explicit exponent $\theta > 0$ and constant $A_k(\gamma)$; in particular decide whether an $n^{-1/6}$ correction with a Groeneboom-type constant, analogous to the hypergraph 2-core case, exists, and identify the limiting process (an analogue of $X(t) = \tfrac{1}{2}\tilde F t^2 + \sqrt{\tilde G}\, W(t)$) that governs it. (2) Secondarily, determine the exact form and order of the term following the $n^{-1/6}$ correction in the 2-core expansion of Dembo–Montanari, which they state to be open. Part (1) is the required deliverable, and a complete solution is given by resolving it. Part (2) is an optional secondary target: it is not required for a complete solution, but a positive resolution of it strengthens the answer. Any answer must be consistent with Janson–Luczak at leading order and must reduce to Dembo–Montanari's theorem in the cases they settled.

References

1. A. Dembo and A. Montanari, 'Gibbs measures and phase transitions on sparse random graphs', arXiv:0910.5460 (2009). DOI: 10.48550/arXiv.0910.5460. URL: https://arxiv.org/abs/0910.5460
2. A. Dembo and A. Montanari, 'Finite size scaling for the core of large random hypergraphs', Annals of Applied Probability 18 (2008). DOI: 10.1214/07-AAP514. arXiv:math/0702007. URL: https://arxiv.org/abs/math/0702007
3. S. Janson and M. J. Luczak, 'Asymptotic normality of the k-core in random graphs', Annals of Applied Probability 18 (2008). DOI: 10.1214/07-AAP478. arXiv:math/0612827. URL: https://arxiv.org/abs/math/0612827
4. B. Pittel, J. Spencer and N. Wormald, 'Sudden emergence of a giant k-core in a random graph', Journal of Combinatorial Theory, Series B 67 (1996) 111-151. DOI: 10.1006/jctb.1996.0036. URL: https://doi.org/10.1006/jctb.1996.0036
5. M. Molloy, 'Cores in random hypergraphs and Boolean formulas', Random Structures & Algorithms 27 (2005) 124-135. DOI: 10.1002/rsa.20061. URL: https://doi.org/10.1002/rsa.20061
6. A. Coja-Oghlan, O. Cooley, M. Kang and K. Skubch, 'Core forging and local limit theorems for the k-core of random graphs', Journal of Combinatorial Theory, Series B 137 (2019) 178-231. DOI: 10.1016/j.jctb.2018.12.005. arXiv:1707.03556. URL: https://doi.org/10.1016/j.jctb.2018.12.005
7. S. Goswami, 'Finite size scaling of random XORSAT', arXiv:1610.07431 (2016). DOI: 10.48550/arXiv.1610.07431. URL: https://arxiv.org/abs/1610.07431