Cores in random hypergraphs and Boolean formulas
Michael S. O. Molloy · Random Structures and Algorithms · 2005
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 ak‐core in a randomr‐uniform hypergraph for allr, k≥ 2,r+k> 4, and (ii) the threshold for the pure literal rule to find a satisfying assignment for a random instance ofr‐SAT,r≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005