# Scale-Free Random SAT Instances
## 5 Phase Transition in Scale-Free Random 2-SAT Formulas
### A Criterion for Phase Transition in 2-Sat
At every iteration, this variable satisfies:  
**(case A)**: \(X_{r}=X_{r-1}-1\), if \(o_{z}=true\) and \(o_{-z}=false\);
**(case B)**: \(X_{r}=X_{r-1}-1+k_{-z}\), if \(o_{z}=o_{-z}=false\);
**(case C)**: \(X_{r}=X_{r-1}-2+k_{-z}-c_{-z}\), if \(o_{z}=false\) and \(o_{-z}=true\). Notice that line 7 decreases \(X_{r}\) in 1, line 8 decreases \(X_{r}\) in 1, when \(o_{-z}=true\), and line 6 increases \(X_{r}\) in \(k_{-z}-c_{-z}\), when \(o_{z}=false\). However, if both \(o_{z}\) and \(o_{-z}\) are false, then \(c_{-z}\) is zero. After case C, we find a contradiction and finish. In case B, the expected gain in \(X_{r}\) is  
\[\mathrm{E}[X_{r}-X_{r-1}]\approx\frac{\sum_{z}k_{z}\left(k_{-z}-1\right)}{ \sum_{z}k_{z}}\]  
In case A, the random variable only decreases by one. Like [PERSON] and [PERSON]'s work, we can also argue that the case A is negligible, unless we have already added to the set of implied literals a constant fraction of them. Therefore, reproducing all the lemmas of [PERSON] and [PERSON]'s proof, we can conclude that, when \(\sum_{z}k_{z}\left(k_{-z}-1\right)>0\), almost surely there exists a constant \(0<c<1\) such that for a fraction \(c\) of initial literals \(x\), the set of literals implied by \(x\) is a fraction \(c\) of all literals or contains a contradiction, and hence, \(X\) implies \(\
eg x\). For a particular variable \(x\), the probability that \(x\) implies \(\
eg x\) and \(\
eg x\) implies \(x\) is at least \(c^{4}\). The probability that the formula is satisfiable is at most \((1-c^{4})^{n}\), which tends exponentially to zero as \(n\) tends to infinity. Theorem 3: _Let \(F\) be a 2-CNF formula generated in a random model with variables \(\{x_{1},\ldots,x_{n}\}\), where every variable \(x_{i}\) is selected with probability \(P_{i}\) and negated with probability \(1/2\), and variables in clauses are not correlated. Assume that \(P_{i}=o(1)\) and \(m=\mathcal{O}(n)\). Let \(K_{i}=2\,m\,P_{i}\) be the expected number of occurrences of variable \(x_{i}\). Then, if \(\sum_{i=1}^{n}K_{i}(K_{i}-3)>0\), then almost surely \(F\) is unsatisfiable._  
_The condition \(\sum_{i=1}^{n}K_{i}(K_{i}-3)>0\) is equivalent to \(\mathrm{E}[K^{2}]/\mathrm{E}[K]>3\)_  
Proof: The proof is, like in Theorem 2, based on the proof of [PERSON] and [PERSON] [47]. In this case, however, the expected gain in the random variable \(X_{r}\) is given by:  
\[\mathrm{E}[X_{r}-X_{r-1}]=\frac{\sum_{i=1}^{n}\frac{K_{i}}{2}\left(\frac{K_{i }-1}{2}-1\right)}{\sum_{i=1}^{n}\frac{K_{i}}{2}}\]  
since \(\frac{K_{i}}{2}\) is the expected value of \(k_{i}\) and \(\frac{K_{i}-1}{2}\) is the expected value of \(k_{-i}\) conditioned to the existence of one positive occurrence of \(x_{i}\). Then, the condition \(\mathrm{E}[X_{r}-X_{r-1}]>0\) is equivalent to \(\sum_{i=1}^{n}K_{i}(K_{i}-3)>0\). For the proof of Theorem 3, we could also use the argument of [PERSON] et al. [49]. In the case of graphs, we obtain a giant connected component when a node \(i\), connected to a node \(j\), is also connected in average to at least one other node. Formally, when the expected degree of \(i\), conditioned to the fact that \(i\) and \(j\) are connected, is \(\mathrm{E}[k_{i}\mid i\leftrightarrow j]=2\). In our case, in order for a giant cycle to emerge, when there is a clause \(x\lor y\), we have to find, at least, another clause containing \(\
eg x\). In this situation, the expected number of other clauses containing \(x\) is 2, that added to the original clause \(x\lor y\), gives a minimum number of 3 clauses containing \(x\). Given a pair of literals \(x\) and \(y\), let \(\pm x\lor y\) express the fact: \(\
eg x\lor y\in F\) or \(\
eg x\lor y\in F\). Formally, our criterion can be written as  
\[\mathrm{E}[K_{x}\mid\pm x\lor y]>3 \tag{11}\]  
This criterion is the necessary and sufficient condition to continue the construction of a set of clauses, ensuring that the probability that this set contains a fraction of the literals tends to one.