An Algorithm for Bounding the Probability of r-core Formation in k-uniform Random Hypergraphs

2019/01/15 by Bissias, George
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1901.04934

Abstract

We present an algorithm for bounding the probability of r-core formation in k-uniform hypergraphs. Understanding the probability of core formation is useful in numerous applications including bounds on the failure rate of Invertible Bloom Lookup Tables (IBLTs) and the probability that a boolean formula is satisfiable.

Related

• Loose cores and cycles in random hypergraphs
• On Thresholds for the Appearance of 2-cores in Mixed Hypergraphs
• The stripping process can be slow: part II
• The core in random hypergraphs and local weak convergence
• Structure of random r-SAT below the pure literal threshold