Recognizing more unstatisfiable etc.

Joel Friedman^{∗} Department of Mathematics University of British Colubmia Vancouver, BC V6T 1Z2 CANADA

          jf@math.ubc.ca

Andreas Goerdt

January 11, 2001

1 Spectral Considerations

In this section we prove a general relationship between the size of an independent set in a graph and the eigenvalues of its adjacency matrix. Then we prove that the graphs G_{F} and H_{F} satisfy certain eigenvalue bounds with high probability. These two results show that with high probability the conclusion of Theorem 1 does not hold.

Let G = (V, E) be an undirected graph, and A = A_{G} the adjacency matrix of G. Let A_{G}’s eigenvalues be ordered λ_{1} ≥ ⋯ ≥ λ_{n}, with n = |V |. We say that G is ν-separated if |λ_{i}| ≤ νλ_{1} for i > 1. We say that G is ϵ-balanced for some ϵ > 0 if there is a real d such that the degree of each vertex is between d(1 − ϵ) and d(1 + ϵ).

Theorem 1.1 If G is ν-separated and ϵ-balanced, then G contains no independent set of size ≥ (n/5) + nf(ν, ϵ) where f(ν, ϵ) tends to 0 as ν, ϵ tend to 0.

∗Research supported in part by an NSERC grant.

We remark that this theorem can probably be greatly improved upon (see below). But this weak theorem does preclude independent sets of size n/4 for small ν, ϵ, and that is all we need here. Proof Let u be a non-negative first eigenvector of A_{G} of unit length. Then

A_{G} = λ_{1}uu^{T} + E,

where E is a matrix of operator norm max_{i>1} |λ_{i}|. Let S be an independent subset of vertices of G, and let T = V \ S. Let χ_{S}, χ_{T} be the characteristic functions of S, T respectively (i.e. taking the value 1 on the set and 0 outside of the set). Then

d(1 − ϵ)|S| ≤ | edges leaving S | = (A_{G}χ_{S}, χ_{T}) = λ_{1}(u^{T}χ_{S})(u^{T}χ_{T}) + χ_{S}^{T}Eχ_{T}

≤ λ_{1}(u^{T}χ_{S})(u^{T}χ_{T}) + (max_{i>1} |λ_{i}|)\sqrt{|S| |T |}

Let α, β be the average values of u on S, T respectively. Since u is a unit vector, Cauchy-Schwarz implies that

α^{2}|S| + β^{2}|T | ≤ ∥u∥^{2} = 1,

and hence, again by Cauchy-Schwarz

2α|S|^{1/2}β|T |^{1/2} ≤ α^{2}|S| + β^{2}|T | ≤ 1

(the weakness of this theorem undoubtedly comes from this pessimistic first inequality, which is only close to the truth when α^{2}|S| is close to β^{2}|T |). It follows that

(u^{T}χ_{S})(u^{T}χ_{T}) = α|S|β|T | ≤ \sqrt{|S| |T |} / 2.

Since λ_{1} is bounded above and below by the max and min degrees, we conclude

d(1 + ϵ)|S| ≤ d(1 − ϵ)\sqrt{|S| |T |} / 2 + νd(1 + ϵ)\sqrt{|S| |T |}.

Setting θ = |S|/n we conclude that

θ ≤ (1/2)(1 + O(ϵ) + O(ν))\sqrt{θ(1 − θ)}

for ϵ, ν small, and squaring both sides and dividing by θ we get

θ ≤ (1/4)(1 + O(ϵ) + O(ν))(1 − θ),

and the theorem follows.

□

We now turn to eigenvalue estimates for the random graphs described in section 1. We shall estimate the lower eigenvalues of G_{F} by the trace method. For two vertices (a_{1}, b_{1}) and (a_{2}, b_{2}) of G_{F}, and for a variable z, let

(a_{1}, b_{1}) ⟶^{(z,1)} (a_{2}, b_{2})

be 1 or 0 according to whether or not both a_{1} ∨ a_{2} ∨ z and b_{1} ∨ b_{2} ∨ ¬z are clauses in F. Similarly, let

(a_{1}, b_{1}) ⟶^{(z,−1)} (a_{2}, b_{2}) = (a_{2}, b_{2}) ⟶^{(z,1)} (a_{1}, b_{1}).

So the number of edges from (a_{1}, b_{1}) to (a_{2}, b_{2}) is the number of pairs (z, e) with z a variable and d ∈ {1, −1} for which

(a_{1}, b_{1}) ⟶^{(z,e)} (a_{2}, b_{2}) = 1.

We shall also say that such an edge has “colour” z.

We now describe the trace method. We fix a positive even integer, k. For vectors of variables, a⃗ = (a_{0}, …, a_{k}), b⃗ = (b_{0}, …, b_{k}), z⃗ = (z_{1}, …, z_{k}), and a vector e⃗ = (e_{1}, …, e_{k}) with each e_{i} ∈ {1, −1}, we set

walk(a⃗, b⃗, z⃗, e⃗) = ∏_{i=0}^{k−1}(a_{i−1}, b_{i−1}) ⟶^{(z_{i},e_{i})} (a_{i}, b_{i}).

Clearly

∑ λ_{i}^{k} = Trace(A^{k}) = ∑_{\begin{matrix}a⃗,b⃗,z⃗,e⃗ \\ a_{0}=a_{k},b_{0}=b_{k} \end{matrix}} walk(a⃗, b⃗, z⃗, e⃗).

The “pure” trace method would estimate the expected value of the above trace. However, we shall need to exclude certain rare and pathological graphs before estimating the trace.

For a graph, G_{F}, let d_{max} and d_{min} be the maximum and minimum degrees of G_{F}. Let c_{max} be the maximum number of edges of any one colour incident upon an vertex.

Lemma 1.2 For any constant r > 0 there is a constant M such that for a random G_{F} we have c_{max} ≤ M with probability 1 − O(n^{−r}).

Proof Given a z, the edges incident with a given (a, b) of colour z is the the sum of two products, the first product being the number of variables x with a ∨ x ∨ z a clause times the number of variables y with b ∨ y ∨ ¬z, and the second product similar. The number of such x’s as above, with a and z fixed, is the number of successes of n Bernouli trials with probability n^{−1−γ}. For t ≥ 1, t successes will occur with probability at most

(n − t + 1)\binom{n}{t}(n^{−1−γ})^{t}(1 − n^{−1−γ})^{n−t}≤ n\binom{n}{t}n^{t(−1−γ)} ≤ n(ne/t)^{t}n^{t(−1−γ)}.

Therefore the number of such success is ≥ M_{1} with probability ≤ O(n^{−r−2}), for some constant M_{1}. The so the count on the x variables is ≥ M_{1} for at least one a and one z with probability ≤ O(n^{−r}). We conclude that c_{max} ≤ M with M = 2M_{1}^{2} with probability 1 − O(n^{−r}).

□

Now let ϵ, M > 0 be fixed (as well as an even positive k), and let E be the event that G_{F} has d_{max} ≤ 2n^{1−2γ}(1+ϵ), d_{min} ≥ 2n^{1−2γ}(1−ϵ), and c_{max} ≤ M. Let χ_{E} be the characteristic function of E, i.e. 1 or 0 according to whether or not E holds. Our main theorem on the trace is the following.

Theorem 1.3 For all k ≥ 2 we have that

E(χ_{E}Trace(A^{k})) ≤ (2n^{1−2γ})^{k} + f(ϵ, M, k)n^{k(1−2γ)}n^{− min(1,(k/2)(1−2γ))},

where E denotes expected value and where f is some function.

Proof Let a⃗, b⃗, z⃗, e⃗ be as before with a_{0} = a_{k} and b_{0} = b_{k}. Any z⃗ falls into precisely one of the three following cases: (1) distinct, meaning that all z_{i} are distinct, (2) quasi-distinct, meaning that at least one z_{i} is distinct, but some z_{i}’s are repeated, or (3) duplicated, meaning that no z_{i}’s are distinct. If z⃗ is distinct, then clearly

E(walk(a⃗, b⃗, z⃗, e⃗)) = n^{(−1−γ)2k}.

Hence

∑_{a⃗,b⃗,z⃗,e⃗ a_{0}=a_{k},b_{0}=b_{k} z⃗ distinct} walk(a⃗, b⃗, z⃗, e⃗) ≤ n^{3k}2^{k}n^{(−1−γ)2k} = (2n^{1−2γ})^{k}.

Next consider a quasi-distinct z⃗. Consider the case where z_{k} is distinct. Fix z_{k}, a_{0}, and b_{0}. Since z_{k} is distinct, the random variable

(a_{i−1}, b_{i−1}) ⟶^{(z_{i},e_{i})} (a_{i}, b_{i})

with i = k is 1 with probability n^{−2−2γ} independently of all the other random variables with i ≠ k. Now we let all edges in G_{F} of colour not z_{k} be determined, and view the edges coloured z_{k} as (still undetermined) random variables. We have

∑_{a⃗,b⃗,z⃗,e⃗ a_{0}=a_{k},b_{0}=b_{k},z_{k} fixed z⃗ with z_{k} distinct} E(walk(a⃗, b⃗, z⃗, e⃗)) ≤ N (a_{0}, b_{0}, z_{k})n^{−2−2γ},

where N (a_{0}, b_{0}, z_{k}) denotes the number of walks in G_{F} of length k−1 that do not involve edges of colour z_{k} but that do have at least one repeated colour. We conclude that

∑ E(χ_{E}walk(a⃗, b⃗, z⃗, e⃗))

summing over a⃗, b⃗, z⃗, e⃗ is bounded by N_{max}n^{−2−2γ}, where N_{max} is the maximum value of N (a_{0}, b_{0}, z_{k}) over the event E. To estimate N_{max} we note that a vertex will have degree at most d_{max}. The repeated colour occurs for the first two times in ≤ \binom{k}{2} positions (in the order z_{1}, …, z_{k}), and once these positions are fixed then the second time the colour occurs there are at most c_{max} choices for possible edges. It follows that

N_{max} ≤ (d_{max})^{k−2}c_{max} ≤ \binom{k}{2}(2(1 + ϵ)n^{1−2γ})^{k−2}Mn^{−2−2γ}.

Summing over (a_{0}, b_{0}) we conclude

∑_{a⃗,b⃗,z⃗,e⃗ a_{0}=a_{k},b_{0}=b_{k} z_{k} fixed z⃗ with z_{k} distinct} E(χ_{E}walk(a⃗, b⃗, z⃗, e⃗)) ≤ n^{2}\binom{k}{2}(2(1 + ϵ)n^{1−2γ})^{k−2}Mn^{−2−2γ}.

For z_{k} not distinct but z⃗ quasi-distinct, consider that a⃗, b⃗, z⃗, e⃗ represent the existence of a closed walk. So the desired walk exists iff any cyclic rotation of a⃗, b⃗, z⃗, e⃗ has the same. So one of k cyclic rotations rotates z⃗ to have z_{k} distinct, and z_{k} is chosen from one of n variables, and hence

∑_{a⃗,b⃗,z⃗,e⃗ a_{0}=a_{k},b_{0}=b_{k} z⃗ quasi−distinct} E(χ_{E}walk(a⃗, b⃗, z⃗, e⃗)) ≤ nkn^{2}\binom{k}{2}(2(1 + ϵ)n^{1−2γ})^{k−2}Mn^{−2−2γ}

= f_{1}(k, ϵ, M)n^{3+(1−2γ)(k−2)−2−2γ} = f_{1}(k, ϵ, M)n^{(1−2γ)k−1}.

Now we turn to duplicated z⃗. Our argument is very similar (and a bit easier) than it is in the quasi-distinct case. A duplicated z⃗ has ≤ k/2 colours occuring for the first time somewhere in z_{1}, …, z_{k}, and ≥ k/2 colours that are repeats. It follows that the total number of loops of length k involving duplicated z⃗ is therefore

≤ f_{2}(k)d_{max}^{k/2}c_{max}^{k} ≤ f_{3}(k, ϵ, M)n^{(1−2γ)k/2}.

Summing over our three estimates for the three types of z⃗ yields the theorem.

□

Corollary 1.4 For any ϵ, ν > 0 the probability that G_{F} is ν-separated and ϵ-balanced is at least f(ϵ, ν, n), where for fixed ϵ, ν and n → ∞ we have

f(ϵ, ν, n) = 1 − (1 − (1 − ϵ)^{k})(1 + ϵ)^{k}ν^{−k} + o(1).

Proof For fixed ϵ > 0, fixed positive even k, and a fixed sufficiently large M we have that the event E occurs with probability 1 − o(1), according to Corollary 8. If ρ denotes the maximum of |λ_{i}| for i > 1, we have (using the fact that λ_{1} ≥ 2n^{1−2γ}(1 − ϵ))

E(χ_{E}ρ^{k}) ≤ E(χ_{E}(Trace(A^{k}) − λ_{1}^{k})) ≤ (2n^{1−2γ})^{k}(1 − (1 − ϵ)^{k} + o(1)).

It follows that the probability that E occurs and ρ ≥ (2n^{1−2γ})s occurs is at most g(ϵ, s, n), where

g(ϵ, s, n) = 1 − (1 − (1 − ϵ)^{k})s^{−k} + o(1).

Now choose s = ν/(1 − ϵ). Then G_{F} will be ν-separated if ρ ≤ (2n^{1−2γ})s

□

Corollary 1.5 We have that a random G_{F} has an independent set of size ≥ n^{2}/4 with probability ≤ o(1).

Proof Fix a ν > 0 sufficiently small so that in Theorem 1.1 for small ϵ > 0 we have f(ν, ϵ) < 1/20. Then for any small ϵ the above corollary (along with Theorem 1.1) implies that an independent set occurs with size n^{2}/4 with probability

≤ (1 − ϵ)^{k}(1 + ϵ)^{k}ν^{−k} + o(1).

Hence for any ϵ there is an n_{0} such that this probability is less than h(ϵ) for all n ≥ n_{0} = n_{0}(ϵ), where h(ϵ) → 0 as ϵ → 0. In other words, for any δ > 0 there is an ϵ > 0 with h(ϵ) < δ, and hence an idependent set of size n^{2}/4 occurs with probability ≤ δ for n ≥ n_{0}(ϵ). This is just to say that the aforementioned probability is ≤ o(1).

□