The phase transition in random regular exact cover

Moore, Cristopher

Annales de l’Institut Henri Poincaré D, Tome 3 (2016) no. 3, pp. 349-362.

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

d ☆ = ln k ( k - 1 ) ( - ln ( 1 - 1 / k ) ) + 1 ,

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.

Classification : 68-XX, 05-XX, 82-XX
Mots-clés : Random structures, phase transitions, Boolean formulas, satisfiability, NP-complete problems, second moment method, small subgraph conditioning.