On the phase transitions of (k, q)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T_k(V) denote the set of all 2^kn^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T_k(V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂n and let p₀ = ln2/qn^k-1. We prove that lim_{n → ∞ P[I is satisfiable]={1, p ≤(1-ε)p0, 0, p ≥(1-ε)p0.}