The phase transition in random regular exact cover
Cristopher Moore · Annales de l’Institut Henri Poincaré D Combinatorics Physics and their Interactions · 2016
A k -uniform, d -regular instance of EXACT COVER is a family of m sets F_{n,d,k} = \{ S_j \subseteq \{1,\ldots,n\} \} , where each subset has size k and each 1 \le i \le n is contained in d of the S_j . It is satisfiable if there is a subset T \subseteq \{1,\ldots,n\} such that |T \cap 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 d^\star = \frac{\ln k}{(k-1)(- \ln (1-1/k))} + 1 \, , we show that F_{n,d,k} is satisfiable 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.