The phase transition in random regular exact cover
C Moore - Annales de l'Institut Henri Poincaré D, 2016 - numdam.org
Annales de l'Institut Henri Poincaré D, 2016•numdam.org
A k-uniform, d-regular instance of EC is a family of m sets Fn; d; k D ¹Sj ¹1;:::; nºº, where each
subset has size k and each 1 in is contained in d of the Sj. It is satis able if there is a subset T
¹1;:::; nº such that jT\Sj j D 1 for all j. Alternately, we can consider it a d-regular instance of P--
k SAT, ie, 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 satis ability
threshold for random instances of this type with k> 2. Letting d? D lnk. k 1/. ln. 1 1= k//C 1; we …
subset has size k and each 1 in is contained in d of the Sj. It is satis able if there is a subset T
¹1;:::; nº such that jT\Sj j D 1 for all j. Alternately, we can consider it a d-regular instance of P--
k SAT, ie, 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 satis ability
threshold for random instances of this type with k> 2. Letting d? D lnk. k 1/. ln. 1 1= k//C 1; we …
Abstract
A k-uniform, d-regular instance of EC is a family of m sets Fn; d; k D ¹Sj ¹1;:::; nºº, where each subset has size k and each 1 in is contained in d of the Sj. It is satis able if there is a subset T ¹1;:::; nº such that jT\Sj j D 1 for all j. Alternately, we can consider it a d-regular instance of P--k SAT, ie, 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 satis ability threshold for random instances of this type with k> 2. Letting d? D lnk
. k 1/. ln. 1 1= k//C 1; we show that Fn; d; k is satis able with high probability if d< d? and unsatis able with high probability if d> d?. We do this with a simple application of the rst and second moment methods, boosting the probability of satis ability below d? to 1 o. 1/using the small subgraph conditioning method.
numdam.org