2007/02/28 by Amir Dembo, Andrea Montanari
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #math.CO #math.PR #msc:05C80 #msc:60F17 #msc:60J10 #msc:68R10 #msc:94A29
paper · pdf · doi:10.1214/07-aap514
published as Annals of Applied Probability 2008, Vol. 18, No. 5, 1993-2040 · Published in at http://dx.doi.org/10.1214/07-AAP514 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
openalex publication_date 2008/10/01 · arxiv created 2008/11/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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ρ vertices and n hyperedges, each consisting of the same fixed number l≥3 of vertices, the size of the core exhibits for large n a first-order phase transition, changing from o(n) for ρ>ρc to a positive fraction of n for ρ<ρc, with a transition window size Θ(n−1/2) around ρc>0. Analyzing the corresponding “leaf removal” algorithm, we determine the associated finite-size scaling behavior. In particular, if ρ is inside the scaling window (more precisely, ρ=ρc+rn−1/2), the probability of having a core of size Θ(n) has a limit strictly between 0 and 1, and a leading correction of order Θ(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.