Finite size scaling for the core of large random hypergraphs

DOI10.1214/07-AAP514zbMATH Open1152.05051arXivmath/0702007OpenAlexW4297752150MaRDI QIDQ957528FDOQ957528

Authors: Amir Dembo, Andrea Montanari 

Publication date: 27 November 2008

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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=nho$ vertices and $n$ hyperedges, each consisting of the same fixed number $lgeq3$ of vertices, the size of the core exhibits for large $n$ a first-order phase transition, changing from $o(n)$ for $ho>h{o}_{mathrmc}$ to a positive fraction of $n$ for $ho<h{o}_{mathrmc}$, with a transition window size $Theta(n^{-1/2})$ around $h{o}_{mathrmc}>0$. Analyzing the corresponding ``leaf removal algorithm, we determine the associated finite-size scaling behavior. In particular, if $ho$ is inside the scaling window (more precisely, $ho=h{o}_{mathrmc}+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.

Full work available at URL: https://arxiv.org/abs/math/0702007

Recommendations

• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• Structure of large random hypergraphs
• The size of the giant high-order component in random hypergraphs
• Size and connectivity of the \(k\)-core of a random graph
• The phase transition in a random hypergraph
• Component sizes of the random graph outside the scaling window
• Asymptotic normality of the size of the giant component in a random hypergraph
• An elementary approach to component sizes in critical random graphs
• Local limit theorems for the giant component of random hypergraphs

zbMATH Keywords

random graphcorefinite-size scalingrandom hypergraphlow-density parity-check codesXOR-SAT

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (including graph drawing) in computer science (68R10) Source coding (94A29) Functional limit theorems; invariance principles (60F17) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• An approximation of partial sums of independent RV'-s, and the sample DF. I
• Title not available (Why is that?)
• The birth of the giant component
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Sudden emergence of a giant \(k\)-core in a random graph
• Solutions of ordinary differential equations as limits of pure jump markov processes
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Structure of large random hypergraphs
• Cores in random hypergraphs and Boolean formulas
• On the solution-space geometry of random constraint satisfaction problems
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Title not available (Why is that?)
• Efficient erasure correcting codes
• The scaling window of the 2-SAT transition
• The average performance of the greedy matching algorithm
• Satisfiability threshold for random XOR-CNF formulas
• Title not available (Why is that?)
• Strong approximation theorems for independent random variables and their applications
• Pairs of SAT-assignments in random Boolean formulæ
• Critical random hypergraphs: the emergence of a giant set of identifiable vertices
• Stopping Set Distribution of LDPC Code Ensembles
• Essential edges in Poisson random hypergraphs
• Continuous and discontinuous phase transitions in hypergraph processes
• On the critical exponents of random k‐SAT
• Finite-Length Scaling for Iteratively Decoded LDPC Ensembles

Cited In (14)

• Networks beyond pairwise interactions: structure and dynamics
• Maximum matchings in random bipartite graphs and the space utilization of cuckoo hash tables
• Random 2-XORSAT at the Satisfiability Threshold
• Notes on ferromagnetic diluted \(p\)-spin model
• Phase transition of random non-uniform hypergraphs
• Expected Maximum Block Size in Critical Random Graphs
• Chernoff's distribution and differential equations of parabolic and Airy type
• Title not available (Why is that?)
• The set of solutions of random XORSAT formulae
• Random 2 XORSAT phase transition
• Gibbs measures and phase transitions on sparse random graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Core forging and local limit theorems for the \(k\)-core of random graphs
• Loose cores and cycles in random hypergraphs

This page was built for publication: Finite size scaling for the core of large random hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q957528)