On the constraint length of random $$k$$ k -CSP

Consider an instance $$I$$ I of the random $$k$$ k -constraint satisfaction problem ( $$k$$ k -CSP) with $$n$$ n variables and $$t=r\frac{n\ln d}{-\ln (1-p)}$$ t = r n ln d - ln ( 1 - p ) constraints, where $$d$$ d is the domain size of each variable and $$p$$ p determines the tightness of the constraints. Suppose that $$d\ge 2$$ d ≥ 2 , $$r>0$$ r > 0 and $$0 1/2$$ α > 1 / 2 . We prove that $$\begin{aligned} \nonumber \lim _{n\rightarrow \infty }\mathbf{ Pr } [I\ \text{ is } \text{ satisfiable }]=\left\{ \begin{array}{cc} 1 &{}\quad \text{ r } 1. \\ \end{array} \right. \end{aligned}$$ lim n → ∞ Pr [ I is satisfiable ] = 1 r 1 . Similar results also hold for the $$k$$ k - $$hyper$$ h y p e r - $$\mathbf {F}$$ F - $$linear$$ l i n e a r CSP which is obtained by incorporating certain algebraic structures to the domains and constraint relations of $$k$$ k -CSP.