# The phase transition in random regular exact cover

### Cristopher Moore

Santa Fe Institute, USA

## Abstract

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

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.

## Cite this article

Cristopher Moore, The phase transition in random regular exact cover. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 3 (2016), no. 3, pp. 349–362

DOI 10.4171/AIHPD/31