Cristopher Moore
Paper #: 15-03-007
A k-uniform, d-regular instance of Exact Cover is a family of m sets Fn,d,k = {Sj ⊆ {1, . . . , n}}, where each subset has size k and each 1 ≤ i ≤ n is contained in d of the Sj. It is satisfiable if there is a subset T ⊆ {1,…,n} such that | T ∩ Sj | = 1 for all j. Alternately, we can consider it a d-regular instance of Positive 1-in-k SAT, i.e., a Boolean formula with m clauses and n variables where each clause contains k variables and demands that exactly one of them is true. We determine the satisfiability threshold for random instances of this type with k > 2. Letting
we show that Fn,d,k is satisfiable with high probability if d < d⋆ and unsatisfiable with high probability if d > d⋆. We do this with a simple application of the first and second moment methods, boosting the probability of satisfiability below d⋆ to 1 − o(1) using the small subgraph conditioning method.