and hence,  $$E(S)=\sum_{1\leq i,j\leq en}E(I_{ij})=\sum_{1\leq i,j\leq en}Pr\left\{I_{ij}=1\right\}\in\Omega(n).$$  We now consider the variance of $S$. Since $S=\sum_{1\leq i,j\leq en}I_{ij}$, we have 
$$\operatorname{Let}$$
$$\mathrm{and}$$
$$Var\left(S\right)=\frac{\sum\limits_{i,j}Var\left(I_{ij}\right)+2\sum\limits_{\left(i,j\right)\neq\left(l,m\right)}\left[E\left\{I_{ij}I_{lm}\right\}-E\left\{I_{ij}\right\}E\left\{I_{lm}\right\}\right]}{(E(S))^{2}}.$$  $$A_{1}=\frac{\sum\limits_{i,j}Var\left(I_{ij}\right)}{(E(S))^{2}}$$  $$A_{2}=\frac{2\sum\limits_{\left(i,j\right)\neq\left(l,m\right)}\left[E\left\{I_{ij}I_{lm}\right\}-E\left\{I_{ij}\right\}E\left\{I_{lm}\right\}\right]}{(E(S))^{2}}.$$
It is easy to see that lim A 1 = 0. To prove lim A 2 = 0, we consider two cases:
Case 1: i ̸ = j ̸ = m ̸ = l . In this case, the two random variables I ij and I im are actually independent. It follows that E{IijItm} = E{Iij}E{Itm} = 0.

Case 2: (i,j) ̸= (l,m), but they have one in common, say j = l . In this case, we have

$$E\left\{I_{ij}I_{lm}\right\}-E\{I_{ij}\}E\{I_{lm}\}=Pr\left\{I_{ij}=1\right\}Pr\left\{I_{jm}=1|I_{ij}=1\right\}-\Omega\left(\left(\frac{1}{n}\right)^{2}\right)$$ $$=\Omega\left(\frac{1}{n}\right)Pr\left\{I_{jm}=1|I_{ij}=1\right\}-\Omega\left(\left(\frac{1}{n}\right)^{2}\right)$$  In that $f$ and $f$ can filter with each other, the conditional probability that $f$ and 
Given that f i and f i conflict with each other, the conditional probability that f i and f m conflict with each other is still in Ω( ).

Since there are only C ε n pairs of I ij and I jm satisfying the condition in Case 2, we know that L
[ E {I ij I tm} - E {I ij } E {I tm}] is in Ω (n). And therefore, lim A 2 = 0. It follows
(i,j)=(l,m)
that

$$\operatorname*{lim}_{n\,\rightarrow\,\infty}P r\left\{S=0\right\}\leq\operatorname*{lim}_{n\,\rightarrow\,\infty}{\frac{V a r\left(S\right)}{\left(E(S)^{2}\right)}}=0.$$

Since the event { S > 0} implies that there exists a conflicting pair of local fitness functions, the theorem follows.

口

## 4.2  2-Sat Sub-Problems In N (N, 2,Z) And A Tighter Upper Bound

In this subsection, we establish a tighter upper bound z > 2.837 for the threshold of the fixed ratio model N ( n, 2, z ) by showing that asymptotically N ( n, 2, z ) contains an unsatisfiable 2-SAT sub-problem with probability 1 for any value of z greater than 2.873. This also gives us a polynomial time algorithm which determines that N(n,2,z) is insoluble with probability asymptotic to 1 for z > 2.837.