Finite size scaling for the core of large random hypergraphs
Authors:
- Amir DemboADAmir Dembo
- Andrea MontanariAMAndrea Montanari
Open Access
- 1 October 2008
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 18 (5) , 1993-2040
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ρ 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.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- How to find good finite-length codes: from art towards scienceEuropean Transactions on Telecommunications, 2007
- Critical random hypergraphs: The emergence of a giant set of identifiable verticesThe Annals of Probability, 2005
- Essential edges in Poisson random hypergraphsRandom Structures & Algorithms, 2004
- Continuous and discontinuous phase transitions in hypergraph processesRandom Structures & Algorithms, 2004
- On the critical exponents of randomk-SATRandom Structures & Algorithms, 2002
- Efficient erasure correcting codesIEEE Transactions on Information Theory, 2001
- Analysis of Two Simple Heuristics on a Random Instance ofk-satJournal of Algorithms, 1996
- The Average Performance of the Greedy Matching AlgorithmThe Annals of Applied Probability, 1993
- Asymptotic enumeration by degree sequence of graphs with degreeso(n 1/2)Combinatorica, 1991
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980