# Scale-Free Random SAT Instances
## 5 Phase Transition in Scale-Free Random 2-SAT Formulas
### Scale-Free 2-SAT Formulas  
Recently, [PERSON] et al. [12] proved that scale-free random 2-SAT formulas with exponent \(\delta>3\) and clause/variable ratio \(m/n<\frac{(\delta-1)(\delta-3)}{(\delta-2)^{2}}\) are satisfiable with probability \(1-o(1)\). (In their paper, they write \(\beta\) instead of \(\delta\), but we prefer to use \(\beta\) with the same meaning as in [11].) This gives a lower bound for a possible phase transition point, in terms of \(\delta\). They conjecture that this bound is tight and that this phase transition exists. Replacing \(\delta=1/\beta+1\) (according to Theorem 1) in this inequality, we obtain:  
Scale-free random 2-SAT formulas with exponent \(\beta<1/2\) and clause/variable ratio \(m/n<\frac{1-2\beta}{(1-\beta)^{2}}\) are satisfiable with probability \(1-o(1)\). In the first statement of the following theorem, we prove that when the clause/variable ratio exceeds this value, formulas are almost surely unsatisfiable. **Theorem 4**. : _(1) Scale-free random 2-SAT formulas with exponent \(\beta<1/2\) and clause/variable ratio_  
\[m/n>\frac{1-2\beta}{(1-\beta)^{2}}\]  
_are unsatisfiable with probability \(1-o(1)\). (2) Scale-free random 2-SAT formulas over \(n\) variables, exponent \(\beta=1/2\) and more that_  
\[4\ n\log^{-1}n+\mathcal{O}(n^{1/2}\log^{-1}n)\]  
_distinct clauses, or exponent \(1/2<\beta<1\), and more than_  
\[\frac{1}{(1-\beta)^{2}\zeta(2\beta)}n^{2(1-\beta)}+\mathcal{O}(n^{1-\beta})\]  
_distinct clauses, are unsatisfiable with probability \(1-o(1)\)._  
Proof. : In the case of scale-free formulas, we cannot start the percolation process from the complete formula, since the uniform-random deletion of clauses does not give rise to scale-free formulas. Therefore, we can simply impose the criterion on the original formula. We will do all the computations using the number of occurrences of variables \(K_{x}\), instead of the number of occurrences of the literal \(k_{x}\), and applying Theorem 3. Since \(\beta<1\), by Lemma 1, repetitions of variables in clauses may be neglected, and the probability that a particular literal in the formula corresponds to the variable \(x\) is given by \(P(x)\approx\frac{x^{-\beta}}{\sum_{i=1}^{n}i^{-\beta}}\). Since the election of every variable for every possible literal of the formula is independent, the number of occurrences of \(x\) follows a binomial distribution  
\[P(K_{x}=K)\approx\binom{2m}{K}\binom{x^{-\beta}}{\sum_{i=1}^{n}i^{-\beta}} \binom{K}{1-\frac{x^{-\beta}}{\sum_{i=1}^{n}i^{-\beta}}}^{2m-K}\]  
In the limit \(m\to\infty\), the distribution approaches a Poisson distribution where  
\[ \begin{split}\mathbb{E}[K_{x}]&\approx\frac{x^{- \beta}}{\sum_{i=1}^{n}i^{-\beta}}\,2m\\ \mathbb{E}[K_{x}^{2}]&\approx\left(\frac{x^{- \beta}}{\sum_{i=1}^{n}i^{-\beta}}\,2m\right)^{2}+\frac{x^{-\beta}}{\sum_{i=1}^ {n}i^{-\beta}}\,2m\end{split} \]  
Recall that in scale-free formulas \(K_{x}\) follows a distinct probability distribution for every variable \(x\); therefore, we have to average over all variables  
\[ \begin{split}\mathbb{E}[K]&=\frac{1}{n}\,\sum_{x=1}^ {n}\mathbb{E}[K_{x}]\approx\frac{1}{n}\,\sum_{x=1}^{n}\frac{x^{-\beta}}{\sum_{i =1}^{n}i^{-\beta}}\,2m=\frac{2m}{n}\\ \mathbb{E}[K^{2}]&=\frac{1}{n}\,\sum_{x=1}^{n} \mathbb{E}[K_{x}^{2}]\approx\frac{1}{n}\,\sum_{x=1}^{n}\left[\left(\frac{x^{- \beta}}{\sum_{i=1}^{n}i^{-\beta}}\,2m\right)^{2}+\frac{x^{-\beta}}{\sum_{i=1}^ {n}i^{-\beta}}\,2m\right]\\ &\approx\frac{4m^{2}}{n}\,\frac{\sum_{x=1}^{n}x^{-2\beta}}{\left[ \sum_{i=1}^{n}i^{-\beta}\right]^{2}}+\frac{2m}{n}\end{split} \]  
Imposing the criterion \(\mathbb{E}[K^{2}]/\mathbb{E}[K]=3\), we obtain  
\[m\approx\frac{\left[\sum_{i=1}^{n}i^{-\beta}\right]^{2}}{\sum_{x=1}^{n}x^{-2 \beta}}\]  
Applying Equations (3) and (4), we obtain  
\[m=\left\{