Finite size scaling for the core of large random hypergraphs
| dc.creator | Dembo, Amir | |
| dc.creator | Montanari, Andrea | |
| dc.date | 2007-02-01 | |
| dc.date | 2008-11-17 | |
| dc.date.accessioned | 2026-07-07T10:18:55Z | |
| dc.date.available | 2026-07-07T10:18:55Z | |
| dc.description | 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\geq3$ of vertices, the size of the core exhibits for large $n$ a first-order phase transition, changing from $o(n)$ for $ρ>ρ_{\mathrm{c}}$ to a positive fraction of $n$ for $ρ<ρ_{\mathrm{c}}$, with a transition window size $Θ(n^{-1/2})$ around $ρ_{\mathrm{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, $ρ=ρ_{\mathrm{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. | |
| dc.description | 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) | |
| dc.identifier | https://arxiv.org/abs/math/0702007 | |
| dc.identifier | http://arxiv.org/abs/math/0702007 | |
| dc.identifier | Annals of Applied Probability 2008, Vol. 18, No. 5, 1993-2040 | |
| dc.identifier | doi:10.1214/07-AAP514 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/174355 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 05C80, 60J10, 60F17 (Primary) 68R10, 94A29 (Secondary) | |
| dc.title | Finite size scaling for the core of large random hypergraphs | |
| dc.type | text |