- journal article metadata
European Mathematical Society Publishing House
2016-09-19 17:04:49
Annales de l’Institut Henri Poincaré D
Ann. Inst. Henri Poincaré Comb. Phys. Interact.
AIHPD
2308-5827
2308-5835
General
Combinatorics
Quantum theory
10.4171/AIHPD
http://www.ems-ph.org/doi/10.4171/AIHPD
subscribers
European Mathematical Society Publishing House
Zuerich, Switzerland
© European Mathematical Society
3
2016
3
The phase transition in random regular exact cover
Cristopher
Moore
Santa Fe Institute, SANTA FE, UNITED STATES
Random structures, phase transitions, Boolean formulas, satisfiability, NP-complete problems, second moment method, small subgraph conditioning.
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.
Computer science
Combinatorics
Statistical mechanics, structure of matter
349
362
10.4171/AIHPD/31
http://www.ems-ph.org/doi/10.4171/AIHPD/31