# Scale-Free Random SAT Instances
## 6 Unsatisfiability by Small Cores  
In the proof of Theorem 4 we have already seen that when \(\beta>1/2\) the number of clauses needed to make a 2-SAT formula unsatisfiable is sub-linear. Therefore, the phase transition factor--understood as a constant \(c\) such that, on the limit \(n\to\infty\), formulas with less than \(c\,n\) clauses are satisfiable, and those with more than \(c\,n\) clauses are unsatisfiable--is zero. In this section, we will prove that, when \(\beta\) exceeds a certain bound, scale-free formulas become unsatisfiable due to a small subset of clauses containing variables with small indexes. Moreover, this result holds for clauses of any size. **Theorem 5**. : _A random scale-free formula over \(n\) variables, exponent \(0\leq\beta<1\) and \(\omega(n^{(1-\beta)k})\) clauses of size \(k\) is unsatisfiable with probability \(1-o(1)\)._  
Proof. : The probability of a clause only containing the smallest \(k\) variables is  
\[P(x_{1}\vee\cdots\lor x_{k})\approx\frac{k!\,1^{-\beta}\cdots k^{-\beta}}{ \left(2\,\sum_{i=1}^{n}i^{-\beta}\right)^{k}}\]  
This inequality would be an equality, if we allow tautologies and simplifiable clauses (i.e., repeated variables) in formulas. Using Eqaution (3), we obtain  
\[P(x_{1}\vee\cdots\lor x_{k})\approx\frac{k!\,1^{-\beta}\cdots k^{-\beta}}{ \left(2\,\sum_{i=1}^{n}i^{-\beta}\right)^{k}}=\frac{(k!)^{1-\beta}}{2^{k} \left(\zeta(\beta)+\frac{n!-\beta}{1-\beta}+\mathcal{O}(n^{-\beta})\right)^{k}}\]  
Figure 4: Fraction of satisfiable formulas as a function of \(m/\alpha\), where \(\alpha=\frac{1}{(1-\beta)^{2}\zeta(2\beta)}n^{2(1-\beta)}\) for \(\beta=0.7\), and distinct values of \(n\) between \(2^{10}\) and \(2^{17}\). Every point is computed repeating the experiment for 100 formulas, and checking how many of them are satisfiable. In the limit \(n\to\infty\), the probability of generating the clause \(x_{1}\vee\cdots\lor x_{k}\) after generating \(n^{(1-\beta)k}\) independent clauses is  
\[1-\left(1-\frac{(k!)^{1-\beta}}{2^{k}\left(\frac{n^{1-\beta}}{1-\beta}\right)^{ k}}\right)^{n^{(1-\beta)k}}=1-\left(1-\frac{\left(\frac{1-\beta}{2}\right)^{k}(k!)^{1- \beta}}{n^{(1-\beta)k}}\right)^{n^{(1-\beta)k}}\approx 1-e^{-\left(\frac{1-\beta}{2} \right)^{k}(k!)^{1-\beta}}\]  
Therefore, the probability of generating the clause \(x_{1}\vee\cdots\lor x_{k}\) is \(1-o(1)\) when the number of clauses is \(m=\omega(n^{(1-\beta)k})\). The same applies for other \(2^{k}\) clauses with distinct signs, and, if \(k=\mathcal{O}(1)\), to a refutation of the formula only using these set of clauses. As in classical random formulas, the expected number of truth assignments that satisfy a scale-free random formula is \(2^{n}(1-2^{-k})^{m}\). This imposes a linear upper bound on the number of clauses of satisfiable scale-free formulas, i.e., a random scale-free formula with \(m=c\,n\) clauses of size \(k\) over \(n\) variables such that \(c>2^{k}\,\log 2\) is unsatisfiable with probability \(1-o(1)\). Therefore, the bound in Theorem 5 only _improves_ this other linear bound when \((1-\beta)k<1\), hence when \(\beta>1-1/k\). Figure 5 shows an experimental estimation of how many clauses are needed to make unsatisfiable 50% of the random formulas generated with distinct values of \(\beta\) and \(k=3\), as a function of the number of variables. Theorem 5 predicts that the number of clauses in a satisfiable scale-free 2-SAT formula cannot grow faster than \(\mathcal{O}(n^{2(1-\beta)})\), due to the emergence of small cores. When \(1/2<\beta<1\), the second statement of Theorem 4, predicts exactly the same exponent \(2(1-\beta)\) for the emergence of a giant bicycle. This suggests that, in this range of \(\beta\), the probability of the existence of a small and a giant unsatisfiable core of clauses is similar. However, experimental results (see Figure 4) suggest that the SAT-UNSAT transition is quite smooth, like in classical 1-SAT. This suggests that small cores are, in fact, more prominent.