The phase transition in random regular exact cover
Cristopher Moore
Santa Fe Institute, USA
Abstract
A -uniform, -regular instance of EXACT COVER is a family of sets , where each subset has size and each is contained in of the . It is satisfiable if there is a subset such that for all . Alternately, we can consider it a -regular instance of POSITIVE 1-IN- SAT, i.e., a Boolean formula with clauses and variables where each clause contains variables and demands that exactly one of them is true. We determine the satisfiability threshold for random instances of this type with . Letting
we show that is satisfiable with high probability if and unsatisfiable with high probability if . We do this with a simple application of the first and second moment methods, boosting the probability of satisfiability below to using the small subgraph conditioning method.
Cite this article
Cristopher Moore, The phase transition in random regular exact cover. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 3 (2016), no. 3, pp. 349–362
DOI 10.4171/AIHPD/31