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\subseteq \{1,...,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,...,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^{☆}=\frac{lnk}{(k-1)(-ln(1-1/k\left)\right)}+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\left(1\right)$ 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.