# Scale-Free Random SAT Instances
## 3 Scale-Free Random Formulas
### Some Properties of the Model
}<k^{j-1}\) and \(R_{k-j}\geq 0\), we have  
\[R_{k}\leq\sum_{i=2}^{k}\sum_{j=2}^{i}i^{j-1}\,P_{j}\leq k\max_{j=2,\ldots,k}k^ {j-1}P_{j}\]  
In our case, assuming \(k=\mathcal{O}(n^{\alpha})\), and replacing the value of \(P_{j}\), we obtain  
\[R_{k}\leq\mathcal{O}(n^{\alpha})\max_{j=2,\ldots,k}\mathcal{O}(n^{\alpha(j-1) }(n^{1-j}+n^{-(1-\beta)j}))=\max_{j=2,\ldots,k}\mathcal{O}(n^{1-(1-\alpha)j}+ n^{-(1-\beta-\alpha)j}))\]  
Assuming \(\alpha\leq 1-\beta<1\), the maximum is obtained for \(j=2\). In this situation, \(R_{k}\leq\mathcal{O}(n^{-(1-2\alpha)}+n^{-1(1-\beta-\alpha)})\). Therefore, it suffices to assume that \(\alpha<\min\{1/2,1-\beta\}\) to ensure that \(R_{k}=o(1)\). Lemma 2: _In a scale-free random formula over \(n\) variables and \(m=C\,n\) clauses of size \(k=\mathcal{O}(1)\), generated with exponent \(0<\beta<1\), the expected number of occurrences of variable \(x_{i}\) is_  
\[\mathrm{E}[K_{i}]\approx C\,k\,(1-\beta)\Big{(}\frac{i}{n}\Big{)}^{-\beta}\]  
Proof: By Lemma 1 and Equation (3), since \(0<\beta<1\) we have  
\[\sum_{i=1}^{n}i^{-1}=\gamma+\log n+\mathcal{O}(n^{-1}) \tag{4}\]0  
The following theorem ensures that the formulas we obtain are scale-free, in the sense that the number of occurrences of variables follow a power-law distribution \(P(K)\sim K^{-\delta}\), for big enough values of \(K\). Theorem 1: _In scale-free random formulas over \(n\) variables, with \(m=C\,n\) clauses of size \(k\), and generated with exponent \(0<\beta<1\), when \(n\) tends to \(\infty\), with \(C\) and \(k\) being constants, the probability that a variable has \(K\) occurrences, where \(K=\Omega(\sqrt{n\log n})\) or \(K=\Omega\bigg{(}(n^{2}\log n)^{\frac{\beta}{2+\beta}}\bigg{)}\), follows a power-law distribution \(P(K)\sim K^{-\delta}\), where \(\delta=1/\beta+1\)._  
Proof: In the limit when \(n\to\infty\), by Lemma 1, \(P(x_{i})\approx\mathfrak{C}\,i^{-\beta}\) is the probability of sampling a variable \(x_{i}\), for some constant \(\mathfrak{C}=1/\sum_{i=1}^{n}j^{-\beta}\approx(1-\beta)\,n^{\beta-1}\) that depends on \(n\). Let \(K_{i}\) be the number of occurrences of variable \(i\) in a randomly generated formula \(F\). We have \(\mathrm{E}[K_{i}]=|F|\,\mathfrak{C}\,i^{-\beta}\). [PERSON]'s or Hoeffding's bounds ensure that, under certain conditions that we will consider later, \(K_{i}\) is approximately \(\mathrm{E}[K_{i}]\). Hence, \(K_{1}>K_{2}>\cdots>K_{n}\) with high probability. Now, we want to approximate the probability \(F(K)=\int_{k=K}^{\infty}P(k)\,\mathrm{d}k\) that a variable occurs at least \(K\) times. Given a value \(K\), let \(i\) be the index of the variable satisfying \(\mathrm{E}[K_{i}]=K\). Under these conditions, all variables with index smaller that \(i\) will have more than \(K\) occurrences, and those with indexes between \(i+1\) and \(n\) have fewer than \(K\) occurrences. Therefore, \(F(K)=i/n\), for the particular \(i\) defined above. From \(\mathrm{E}[K_{i}]=K\) and \(\mathrm{E}[K_{i}]=|F|\,C\,i^{-\beta}\), we obtain  
\[\sum_{i=1}^{n}i^{-1}=\gamma+\log n+\mathcal{O}(n^{-1}) \tag{4}\]1  
Then, the probability \(P(K)\) is  
\[\sum_{i=1}^{n}i^{-1}=\gamma+\log n+\mathcal{O}(n^{-1}) \tag{4}\]2  
Hence, we obtain a discrete power-law distribution with exponent \(\delta=1/\beta+1\). The problem is that \(\mathrm{E}[K_{i}]\) is a good approximation of \(K_{i}\) only when \(i\) is small. For instance, when \(i=\Omega(n)\), we have \(P(x_{i})=\Theta(n^{-1})\) and \(\mathrm{E}[x_{i}]=\Theta(1)\). In this situation, when \(n\to\infty\) being \(C\) and \(k\) constants, the number of occurrences \(K_{i}\) of the variable \(x_{i}\) follows a Poisson distribution with constant variance. This means that, even in the limit \(n\to\infty\), we cannot assume that \(i<j\) implies \(K_{i}>K_{j}\), when \(i=\Omega(n)\). In the following, we will find an upper bound for the index \(i\) of the variable (a lower bound for the value of \(K\)) ensuring that \(\mathrm{E}[K_{i}]\) is a good approximation of \(K_{i}\), when \(n\to\infty\). We will use both [PERSON]'s and [PERSON]'s bounds.