The phase transition in random regular exact cover

Cristopher Moore

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…