# Scale-Free Random SAT Instances
## 5 Phase Transition in Scale-Free Random 2-SAT Formulas
### A Criterion for Phase Transition in 2-Sat
In order to prove that executions of case A1 do not hurt, [PERSON] and [PERSON] prove that the probability of choosing a partially exposed node (a node with \(c_{j}>0\)) is negligible unless we have already exposed a fraction \(\Theta(n)\) of the nodes in the current connected component. Theorems 2 and 3 establish a similar criterion for the existence of a giant set of implied literals from a given one. This almost surely implies the unsatisfiability of the formula. The proof of the theorem resembles [PERSON] and [PERSON]'s and [PERSON] et al. 's proofs. In Theorem 2 we fix the number of occurrences of every literal, whereas in Theorem 3, we fix the number of occurrences of variables. Compared with the definition of \(Q\) in [PERSON] and [PERSON]'s, we observe that in Theorem 3, the 2 is replaced by a 3. In Theorem 2, we combine the number of literals \(k_{i}\) with the number of their negated \(k_{-i}\), and the constant is a 1 instead of a 2. Notice that the condition, in this case, is equal to the condition found by [PERSON] et al. (1977) for the configuration method and prescribed literal degrees. Theorem 2: _Let \(F\) be a 2-CNF formula generated in a random model with variables \(\{x_{1},\ldots,x_{n}\}\), where every literal \(x_{i}\) (resp \(-x_{i}\)) is selected with probability \(p_{i}\) (resp \(p_{-i}\)), and literals in clauses are not correlated (i.e., \(P(x_{i}\lor x_{j})\approx p_{i}\,p_{j}\)). 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 literal \(x_{i}\). Then, if \(\sum_{i=-n}^{n}k_{i}(k_{-i}-1)>0\), then almost surely \(F\) is unsatisfiable._  
Proof: The proof resembles [PERSON]'s proof for the percolation threshold on graphs. This proof is quite long, and our proof does not differ very much. Therefore, we will only sketch it. In our case, we do not deal with connected components. In fact, we do not expose the random formula with our algorithm. We assume that we already have the formula, and we describe in Algorithm 2 how to enumerates the set of literals implied by a given initial literal \(x\). ```
Input:\(F_{x}\)
1 foreachydo
2\(c_{y}=0\); \(o_{y}=false\)
3\(o_{x}=true\);
4 while\((\exists y.o_{\
eg y}=true\wedge c_{y}<k_{y})\wedge\
eg(\exists y.o_{y}=o_{ \
eg y}=true)\)do
5 select \(y\lor z\in F\) such that \(o_{\
eg y}=true\);
6\(o_{z}:=true\);
7\(c_{y}:=c_{y}+1\);
8\(c_{z}:=c_{z}+1\);
9\(F:=F\setminus\{y\lor z\}\)
10 return \(\{z\mid o_{z}=true\}\)
```  
**Algorithm 2**Algorithm for finding literals implied by \(x\)  
The Boolean variable \(o_{y}\) denotes if the literal has been reached from the initial literal \(x\) and the counter \(c_{y}\) denotes the number of clauses containing \(y\) that we have already removed from the formula. Therefore, \(k_{y}-c_{y}\) is the number of clauses containing \(y\) that still remains in \(F\). When \(x\) implies \(y\) and \(\
eg y\), for some variable \(y\), we say that \(x\) implies a contradiction. In this case, \(x\) also implies \(\
eg x\). The algorithm returns the set of literals implied by \(x\) or a contradiction (in this second case, we abort, since we already have \(x\rightarrow\
eg x\) that is what we want to check). Notice also that \(c_{y}>0\) implies \(o_{y}=true\lor o_{\
eg y}=true\). Notice that this algorithm is quite similar to [PERSON] and [PERSON]'s algorithm for exposing connected components of a random graph. Counter \(c_{y}\) has a similar meaning and we only require the Boolean variable \(o_{y}\) to denote the condition of _open vertex_ (expressed as \(c_{y}>0\) in [PERSON] and [PERSON]'s algorithm). The algorithm is deterministic if you consider the formula given. However, for a random formula, the algorithm performs exactly the same steps and can be seen as a random algorithm. Similarly, we can define the random variable \(X_{r}=\sum_{o_{\
eg x}=true}k_{x}-c_{x}\) after iteration \(r\).