The scaling window of the model d-k-CSP

Abstract Consider the model d - k -CSP which consists of a set of n variables with the domain size d , and a set of t = r n ln ⁡ d − ln ⁡ p constraints where each constraint binds k distinct variables and permits p d k tuples of values. We prove that the exact phase transition of the model d - k -CSP occurs at r c = 1 as long as k ln ⁡ d = α ln ⁡ n , where α satisfies that 1 2 + 1 2 ( 2 k − 1 ) + e ≤ α ≤ 1 ( e > 0 is a sufficiently small constant). More importantly, we establish the finite-size scaling about this transition. Specifically, let δ > 0 be a given constant, the probability of satisfiability of the model d - k -CSP is greater than 1 − δ if r ≤ 1 − Θ ( 1 n 1 − ν ln ⁡ d ) ( ν is dependent on the control parameters) and is less than δ if r ≥ 1 + Θ ( 1 n ln ⁡ d ) .