Cores in random hypergraphs and Boolean formulas

Abstract

Abstract We describe a technique for determining the thresholds for the appearance of cores in random structures. We use it to determine (i) the threshold for the appearance of a k ‐core in a random r ‐uniform hypergraph for all r, k ≥ 2, r + k > 4, and (ii) the threshold for the pure literal rule to find a satisfying assignment for a random instance of r ‐SAT, r ≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005