Finite size scaling for the core of large random hypergraphs

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

Authors Amir Dembo, Andrea Montanari 

Publication date 27 November 2008

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

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

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)

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.

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

Cites Work

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

Cited In (13)

• 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
• Expected Maximum Block Size in Critical Random Graphs
• Chernoff's distribution and differential equations of parabolic and Airy type
• The set of solutions of random XORSAT formulae
• Random 2 XORSAT phase transition
• Gibbs measures and phase transitions on sparse random graphs
• The set of solutions of random XORSAT formulae
• 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)