Finite size scaling for the core of large random hypergraphs

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 }_{\mathrm{c}}$ to a positive fraction of $n$ for $\rho <{\rho }_{\mathrm{c}}$, with a transition window size $\Theta (n^{-1/2})$ around ${\rho }_{\mathrm{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 }_{\mathrm{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.

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)

References in corpus (9)

• The Scaling Window of the 2-SAT Transition
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics
• Structure of large random hypergraphs
• Pairs of SAT Assignment in Random Boolean Formulae
• On the critical exponents of random k-SAT
• Critical random hypergraphs: The emergence of a giant set of identifiable vertices
• Continuous and discontinuous phase transitions in hypergraph processes
• Essential edges in Poisson random hypergraphs

Cited by in corpus (18)

• Networks beyond pairwise interactions: structure and dynamics
• Random hypergraphs and their applications
• Covering Problems and Core Percolations on Hypergraphs
• Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables
• Phase Transition of Random Non-Uniform Hypergraphs
• Dynamics of k-core percolation in a random graph
• Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
• Finite-size critical fluctuations in microscopic models of mode-coupling theory
• The set of solutions of random XORSAT formulae
• Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• The stripping process can be slow: part I
• The core in random hypergraphs and local weak convergence
• Finite-size scaling in random $K$-satisfiability problems
• Parity Queries for Binary Classification
• Finite size scaling of random XORSAT
• Optimized IR-HARQ Schemes Based on Punctured LDPC Codes over the BEC
• Sharp approximation for density dependent Markov chains