Moore, C.
A k-uniform, d-regular instance of EXACTCOVER is a family of m sets F-n,F- d,F- k = {S-j subset of 1 {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 subset of {1, ..., n} such that vertical bar T boolean AND S-j vertical bar = 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 d(star) = ln k/(k - 1)(-ln(1 - 1/k)) + 1, we show that F-n,F- d,F- k is satisfiable with high probability if d < d(star) and unsatisfiable with high probability if d > d(star). We do this with a simple application of the first and second moment methods, boosting the probability of satisfiability below d(star) to 1 - o(1) using the small subgraph conditioning method.