The Phase Transition in Random Regular Exact Cover

A k-uniform, d-regular instance of Exact Cover is a family of m sets F_n,d,k = {S_j ⊆ {1, . . . , n}}, where each subset has size k and each 1 ≤ i ≤ n is contained in d of the S_j. It is satisfiable if there is a subset T ⊆ {1,…,n} such that | T ∩ S_j | = 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 F_n,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.