# Scale-Free Random SAT Instances
## 5 Phase Transition in Scale-Free Random 2-SAT Formulas
### A Criterion for Phase Transition in 2-Sat
[PERSON] and [PERSON] [47] prove that the critical point is at  
\[Q(\lambda)=\sum_{i>0}i(i-2)\lambda_{i}=0 \tag{9}\]  
where \(\lambda_{i}\) is the fraction of nodes with degree \(i\). [PERSON] et al. [49] independently prove (but in a much more informal way) that the critical point is characterized by  
\[\frac{\mathrm{E}[k^{2}]}{\mathrm{E}[k]}=2 \tag{10}\]  
where \(k\) is the degree of a random node, and \(E\) denotes expectation. It is easy to see that both criteria are exactly the same. Interestingly, the criterion depends not only on the expected degree of nodes, but also on the expected square degree of the nodes, and hence on the variability of node's degrees. The variability on the node degrees plays an important role in the location of the percolation threshold. For instance, in the Erdos-Renyi model, the percolation threshold is located at \(m/n=1/2\); hence, the expected degree of nodes is \(1/2\). However, the expected degree of nodes belonging to the same connected component (recall that minimally connected components are trees, where the number of edges is equal to the number of nodes minus one) of size \(r\) is, at least, \((r-1)/r\approx 1\). This discrepancy is only possible if the variability in the node degrees is high. This also explains why, in regular random formulas, where we impose variables to occur exactly the same number of times (instead of the same average number of times), we find distinct phase transition thresholds. [PERSON] et al. [49] starts assuming that loops of connected nodes may be neglected. In this situation, the percolation transition takes place when a node \(i\), connected to a node \(j\) in the connected component, is also connected in average to at least one other node, i.e., when \(\mathrm{E}[k_{i}\mid i\leftrightarrow j]=\sum_{k}k_{i}P(k_{i}\mid i \leftrightarrow j)=2\). [PERSON] and [PERSON] [47] give a more detailed proof that we will try to summarize. Given the list of fixed degrees \(k_{i}\) of every node, they describe a random algorithm that constructs (exposes) all graphs compatible with these degrees with the same probability, exposing connected components one by one:  
Let \(c_{i}\) be the degree of node \(i\) on the partially exposed graph. Initially, set \(c_{i}=0\), for every node. Then, until \(c_{i}=k_{i}\), for all nodes, repeat the following actions. If, for some node \(i\), we have \(0<c_{i}<k_{i}\), then (case A) select it; otherwise, (case B) choose freely a node \(i\) such that \(c_{i}=0\). Then, in both cases, choose another node \(j\
eq i\) with probability \(P(j)\sim k_{j}-c_{j}\). Expose the edge \(i\leftrightarrow j\), and increase \(c_{i}\) and \(c_{j}\). Notice that every time we execute case B, we start the exposition of a new connected component of the graph. Let \(X_{r}\) be the random variable representing the number of _open vertexes_ in partially exposed nodes, i.e., \(X_{r}=\sum_{i>0}k_{i}-c_{i}\), after the \(r\)th edge \(i\leftrightarrow j\) has been exposed. Notice that we execute case B when we have \(X_{r-1}=0\), and we obtain \(X_{r}=k_{i}+k_{j}-2\). When we execute case A, there are two situations: (case A1) if node \(j\) is a partially exposed node (i.e., \(0<c_{j}\)), then \(X_{r}=X_{r-1}-2\), and (case A2) if node \(j\) has never been exposed (i.e., \(c_{j}=0\)), then \(X_{r}=X_{r-1}+k_{j}-2\). Suppose that cases B and A1 do not happen very often. Then, the expected change in \(X_{r}\) is  
\[\mathrm{E}[X_{r}-X_{r-1}]\approx\frac{\sum_{j}k_{j}(k_{j}-2)}{\sum_{j}k_{j}}= \frac{Q(\lambda)}{\mathrm{E}[k]}\]  
and, since \(X_{r}-X_{r-1}\geq-1\), a standard result of random walk theory ensures that if \(Q(\lambda)>0\) then, after \(\Theta(n)\) steps, \(X_{r}\) is almost surely of order \(\Theta(n)\); and if \(Q(\lambda)<0\), then \(X_{r}\) returns to zero fairly quickly. In the first case, we generate a giant connected component of size \(\Theta(n)\), and in the second case, no component is larger than \(\mathcal{O}(\log n)\).