# Scale-Free Random SAT Instances
## 5 Phase Transition in Scale-Free Random 2-SAT Formulas
### A Criterion for Phase Transition in 2-Sat  
Unsatisfiability proofs of 2-SAT formulas are characterized by _bicycles_. Let \(F\) be a 2-SAT formula. Any sequence of literals \(x_{1},\ldots,x_{s}\) satisfying \(\
eg x_{i}\lor x_{i+1}\in F\), for any \(i=1,\ldots,s-1\), is called an _implication sequence_. We say that \(y\)_implies_\(y^{\prime}\), if there exists an implication sequence of the form \(y,x_{1},\ldots,x_{n},y^{\prime}\). Any implication sequence of the form \(x_{1},\ldots,x_{s},x_{1}\) is called a _cycle_. A _bicycle_ is a cycle \(x_{1},\ldots,x_{n},x_{1}\) such that there exists a variable \(a\) satisfying \(\{a,\
eg a\}\subseteq\{x_{1},\ldots,x_{n}\}\). A 2-SAT formula is unsatisfiable if, and only if, it contains a bicycle [35; 46]. We will also consider random graphs with \(n\) nodes and \(m\) edges (We will deal with distinct models of random graphs where every graph has a distinct probability of being chosen. ), and connected components, defined as subsets of nodes such that any pair of them is connected by a path inside the component. A random graph of size \(n\) is said to contain a _giant connected component_ if almost surely (Almost surely means that, in the model of random graphs, as \(n\to\infty\), the probability tends to one.) it contains a connected component with a positive fraction of the nodes. Given a model of random graphs, we say that \(c\) is the percolation threshold if any random graph with \(n\) nodes and more than \(c\,n\) edges almost surely contains a giant component. In a random graph, the degree of a node \(x\), noted as \(k_{x}\), is a random variable. The random variable \(k\) represents the degree of a random node chosen with a uniform probability. (In some of the models of random graphs that we will consider, not all degrees of nodes follow the same probability distribution. Therefore, we will distinguish between \(k\) and \(k_{x}\).) As we commented above, we can represent any 2-SAT formula as a graph where nodes are literals, and clauses \(a\lor b\) are edges between literals \(a\) and \(b\). In classical 2-SAT random formulas, since literals are chosen independently with uniform probability, the generated graph will be an Erdos-Renyi graph following the model \(G(2\,n,m)\). However, a connected component in the graph is not necessarily an unsatisfiability proof of the formula. First, in a random SAT formula, we may have repeated clauses, which means that from \(m\) clauses we will obtain less than \(m\) edges. However, for a linear number of clauses, when \(\beta<1/2\), there are \((1-o(1))\,m\) distinct clauses or edges. In the classical case, in the limit \(n\to\infty\), with a linear number of clauses \(m=\mathcal{O}(n)\), and a quadratic number of possible clauses, the probability of any clause is \(\mathcal{O}(n^{-2})\), and the probability of being repeated \(m\,\mathcal{O}(n^{-2})=\mathcal{O}(n^{-1})\). Therefore, the fraction of repeated clauses is negligible. For scale-free 2-CNF formulas, in Theorem 5, we will see that, if \(\beta<1/2\), then clauses have probability \(o(n^{-1})\). Precisely, the most probable 2-CNF clause is \(x_{1}\lor x_{2}\). This means, that after generating \(\mathcal{O}(n)\) clauses, the probability that a newly generated clause has already been generated previously is bounded by  
\[P(x_{1}\lor x_{2})\,\mathcal{O}(n)\approx\frac{2!\,1\,1^{-\beta}2^{-\beta}}{(2 \sum_{i=1}^{n}i^{-\beta})^{2}}\,\mathcal{O}(n)=\frac{2^{-1-\beta}}{(\zeta( \beta)+\frac{n^{1-\beta}}{1-\beta}+\mathcal{O}(n^{-\beta}))^{2}}\mathcal{O}( n)=\mathcal{O}(n^{2\beta-1})\]  
This probability bounds the value of the fraction of repeated clauses, which is meaningless when \(\beta<1/2\). Second, connected components and cycles have not the same structure. Therefore, the existence of a giant connected component and the existence of a giant cycle are independent facts. [PERSON] and [PERSON] [47; 48] and [PERSON] et al. [49; 50] have studied the existence of giant components in random graphs with heterogeneous and fixed node degrees.