Abstract
The (two) core of a hypergraph is the maximal collection of hyperedges within which no vertex appears only once. It is of importance in tasks such as efficiently solving a large linear system over GF[2], or iterative decoding of low-density parity-check codes used over the binary erasure channel. Similar structures emerge in a variety of NP-hard combinatorial optimization and decision problems, from vertex cover to satisfiability. For a uniformly chosen random hypergraph of $m=n\rho$ vertices and $n$ hyperedges, each consisting of the same fixed number $l \ge 3$ of vertices, the size of the core exhibits for large $n$ a first-order phase transition, changing from $o(n)$ for $\rho > \rho_c$ to a positive fraction of $n$ for $\rho < \rho_c$, with a transition window size $\Theta(n^{-1/2})$ around $\rho_c > 0$. Analyzing the corresponding “leaf removal” algorithm, we determine the associated finite-size scaling behavior. In particular, if $\rho$ is inside the scaling window (more precisely, $\rho = \rho_c + r n^{-1/2}$), the probability of having a core of size $\Theta(n)$ has a limit strictly between 0 and 1, and a leading correction of order $\Theta(n^{-1/6})$. The correction admits a sharp characterization in terms of the distribution of a Brownian motion with quadratic shift, from which it inherits the scaling with $n$. This behavior is expected to be universal for a wide collection of combinatorial problems.
Introduction
In coding theory and combinatorial optimization, the "core" of a graph represents its structural skeleton. Whether solving massive linear systems or decoding messages over noisy channels, the presence of this core often dictates the success of the algorithm. This paper provides a rigorous mathematical foundation for the emergence of the 2-core in large random hypergraphs, characterizing the transition from a sparse structure to a dense core.
A 2-core is defined as the largest subset of a hypergraph where every vertex appears at least twice. In an infinite system, the size of this core undergoes a first-order phase transition: as the edge-to-vertex ratio $\rho$ crosses a critical threshold $\rho_c$, the core size jumps from zero to a significant fraction of the system. However, practical applications involve finite data blocks, where this transition is smoothed out.
The Scaling Window and Finite-Size Effects
The authors analyze the transition within a narrow "scaling window" of size $\Theta(n^{-1/2})$ around the critical ratio $\rho_c$. Within this window, the probability of a core's existence is neither zero nor one, but follows a specific scaling law.
As shown in the figure above, as the system size $n$ increases, the transition becomes increasingly sharp, converging toward the theoretical threshold $\rho_c \approx 1.2218$ for the $l=3$ case.
A key discovery of this work is the identification of a leading correction term of order $\Theta(n^{-1/6})$. This correction is significantly larger than the $O(n^{-1/2})$ fluctuations typically expected from the Central Limit Theorem, reflecting the unique physics of the core's formation. The probability $P_l(n, \rho_n)$ is characterized by:
$$P_l(n, \rho_n) = \Phi(-r/\alpha_l) + \beta_l \Omega \Phi'(-r/\alpha_l)n^{-1/6} + O(n^{-\eta})$$
where $\Omega$ is a constant defined via Airy functions.
Methodology: Leaf Removal and Brownian Approximation
To derive these results, the authors analyze the "leaf removal" algorithm, which recursively deletes vertices of degree one. By modeling this process as a Markov chain, they show that for large $n$, the algorithm's trajectory concentrates around the solution of an Ordinary Differential Equation (ODE). Near the critical threshold, the fluctuations are modeled using a Brownian motion with a quadratic shift. This approach allows for a precise characterization of the "jump" phenomenon, where the core suddenly appears at a random critical time.
Conclusion and Universality
The refined scaling law matches numerical simulations remarkably well, even for relatively small systems ($n \approx 100$). The authors suggest that this scaling behavior—governed by Brownian motion with quadratic shift—is universal and likely applies to a broad class of problems, including $k$-core percolation and satisfiability thresholds. Future work may extend these techniques to more complex graph models and higher-order correction terms.
Summary updated