The phase transition in random regular exact cover

  • Cristopher Moore

    Santa Fe Institute, USA


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