# Scale-Free Random SAT Instances
## 5 Phase Transition in Scale-Free Random 2-SAT Formulas
### Classical 2-SAT Formulas  
Theorems 2 and 3 may be used to find the phase transition point in terms of the number of clauses divided by the number of variables. In this subsection, we apply the technique to (classical) random 2-SAT formulas.  
We start with a formula (or graph), not necessarily at the critical threshold. Then, we apply a percolation process where a fraction \(1-p\) of randomly selected clauses (edges) are removed, such that the remaining \(p\) fraction of edges are in the critical threshold. If we start with the complete formula with all possible \(2^{2^{\binom{n}{2}}}\) clauses over \(n\) variables, and remove clauses with uniform probability, this process generates a (classical) random 2-SAT formula in the SAT-UNSAT transition point (except for the lack of repeated clauses).  
If \(k_{x}^{\prime}\) is the number of occurrences of literal \(x\) in the original graph, then, after removing the \((1-p)\) fraction, the new distribution on the number of occurrences is \(P(k_{x})=\sum_{k_{x}=k_{x}}^{\infty}P(k_{x}^{\prime})\binom{k_{x}^{\prime}}{ k_{x}^{\prime}}\,p^{k_{x}}\,(1-p)^{k_{x}^{\prime}-k_{x}}\). Using this binomial distribution we obtain the moments \(\mathrm{E}[k_{x}]=p\,\mathrm{E}[k_{x}^{\prime}]\) and \(\mathrm{E}[k_{x}^{2}]=p^{2}\,\mathrm{E}[(k_{x}^{\prime})^{2}]+p(1-p)\mathrm{E }[k_{x}^{\prime}]\) for any literal \(x\). Since \(K_{x}=k_{x}+k_{\
eg x}\), and \(k_{x}\) and \(k_{\
eg x}\) are independent variables with the same distribution, we have \(\mathrm{E}[K_{x}]=2\,\mathrm{E}[k_{x}]\) and \(\mathrm{E}[k_{x}^{2}]=2\,\mathrm{E}[k_{x}^{2}]+2\,E^{2}[k_{x}]\). If we impose the criterion of Theorem 3 to this new formula, we obtain  
\[\frac{\mathrm{E}[K^{2}]}{\mathrm{E}[K]}=\frac{2\,p^{2}\,\mathrm{E}[(k^{\prime })^{2}]+2\,p(1-p)\mathrm{E}[k^{\prime}]+2\,p^{2}\,E^{2}[k^{\prime}]}{2\,p\, \mathrm{E}[k^{\prime}]}=3\]  
Hence,  
\[p=\frac{2}{\frac{\mathrm{E}[(k^{\prime})^{2}]}{\mathrm{E}[K]}+\mathrm{E}[k^{ \prime}]-1}\]For the complete formula we have \(k_{x}^{\prime}=2(n-1)\) for any literal, therefore \(p=1/(2n-5/2)\). The expected number of clauses in the phase transition threshold is  
\[\mathrm{E}[m]=2^{2}\binom{n}{2}\ p=\frac{2n(n-1)}{2n-5/2}=n+\mathcal{O}(1)\]  
This proves that the clause/variable fraction at the 2-SAT phase transition threshold is at most \(m/n=1\), reproducing the results of [PERSON] and [PERSON] [35].  
For the expected moments, we obtain \(\mathrm{E}[k]\approx 1\) and \(\mathrm{E}[k^{2}]\approx 2\), for the number of occurrences of literals, and \(\mathrm{E}[K]\approx 2\) and \(\mathrm{E}[K^{2}]\approx 6\), for the number of occurrences of variables.  
Now, consider the case of (classical) regular random 2-SAT formulas. These are random formulas where the number of occurrences of a literal minus the number of occurrences of another literal is, at most, one. Assume that all literals have exactly the same number of occurrences \(k_{x}=m/n\). Applying Theorem 2, without any need of percolation process, we obtain \(\sum_{i=-n}^{n}k_{i}(k_{-i}-1)=2n\frac{m}{n}(\frac{m}{n}-1)=0\). Therefore, \(m/n=1\) is an upper bound for the phase transition point, reproducing the results of [PERSON] et al. [51]. Notice that, in this case, the conditions of Theorem 3 are not fulfilled: \(k_{x}\) and \(k_{-x}\) are not independent random variables. If we consider the proof of this Theorem, since in a random regular formula \(k_{x}=k_{-x}\), if this formula contains a clause \(x\lor y\), we only need to require that \(\mathrm{E}[K_{x}\ |\ x\lor y]=2\) in order to ensure that there is another clause containing \(\
eg x\). With this new criterion, and reproducing the proof of Theorem 3, we obtain that the threshold in a regular random formula is \(\frac{\mathrm{E}[K^{2}]}{\mathrm{E}[K]}=2\).