Finite size scaling for the core of large random hypergraphs

DOI10.1214/07-AAP514zbMath1152.05051arXivmath/0702007OpenAlexW4297752150MaRDI QIDQ957528

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

corerandom graphfinite-size scalinglow-density parity-check codesrandom hypergraphXOR-SAT

Mathematics Subject Classification ID

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

Related Items (14)

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

Cites Work

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

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