The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

Annales de l’Institut Henri Poincaré D


Full-Text PDF (160 KB) | Metadata | Table of Contents | AIHPD summary
Volume 3, Issue 3, 2016, pp. 349–362
DOI: 10.4171/AIHPD/31

Published online: 2016-09-14

The phase transition in random regular exact cover

Cristopher Moore[1]

(1) Santa Fe Institute, USA

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$ and unsatisfiable 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.

Keywords: Random structures, phase transitions, Boolean formulas, satisfiability, NP-complete problems, second moment method, small subgraph conditioning.

Moore Cristopher: The phase transition in random regular exact cover. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 3 (2016), 349-362. doi: 10.4171/AIHPD/31