The scaling window of the model \(d\)-\(k\)-CSP (Q890505)

A constraint satisfaction problem (CSP) consists of a set of \(n\) variables where each variable has its domain \(D\) (with size \(|D|=d\)); a set of \(t\) constraints where each constraint binds a subset of variables and has a list of legal tuples of values for these variables. In the paper the authors considered the model \(d-k\)-CSP and \(t=r\cdot {n\ln d\over -\ln p}\), where each constraint binds \(k\) distinct variables and permits \(pd^k\) tuples of values. It is proved that a phase transition of the model occurs at \(r_{\text{c}}=1\) and \(k\ln d= \alpha \ln n\), \(\alpha\in [{k\over 2k-1}+\varepsilon, 1]\), \(\varepsilon>0\) is a sufficiently small constant. The finite-size scaling upon the threshold of the model is determined. The second moment method is used.