I’ve been debugging the proof since I posted the previous version in this blog on 7/1. I tried hard to attack the proof from the opposite side. I found only minor bugs so far, and now start believing it.
I refined the paper and notes accordingly: i) overview sections 4.3 for the monotone case, and 5.2 for the NP-NC construction newly added, ii) some technical proofs in Section 2 are moved to appendices, iii) minor error corrections, and iv) missing proof steps filled in.
Please download the latest pdf files from the link below. I’m adding the 3rd file to provide short overall explanation of the shift method.
Paper Verson 1.11 (1.357MByte)
Explanatory Notes Version 1.11 (4.77MByte)
Overview of the Shift Method (1.086MByte)
(Further small refinement on 9/15/12.)
The claims on the Hamming space in Sections 2 and 3 make the foundation of the shift method. The theory is developed to handle circuit complexity, especially of the clique problem. It has flavors in different areas:
1. Geometry: We want to find how the generated cliques intersect with each other at a node of circuit. (This is one general difficulty of treating circuit complexity.) It is about the topological properties of families of sets whose metric is the Hamming distance. It helps if we consider balls and spheres about an element.
2. Probability: Probabilistic arguments in combinatorics are mainly based on counting, because a considered probability space is discrete. In the Hamming space, sparsity of a family plays a similar role: it is about the ratio of #hits to the total number of elements. We focus on sparsity in relation to discrete topological properties of the Hamming space. It simplifies arguments.
3. Analysis: Theorem 2.1 adds some analytic flavor. We do asymptotic sparsity analysis.
4. Algebra: The operator of the domain is disjoint set union. We introduce the notion of a set generating another based on it. A family of sets generated by more than one generators is similar to ideal in the ring theory. On the other hand, disjoint set union doesn’t allow the closure property well, so it’s not easy to construct the theory in a complete algebraic system. However, it is very helpful to find a generator that generates almost every element in a subspace — it’s the extension generator theorem (Theorem 3.4). It can tell you that an element exists in your target subspace.
5. Extremal Set Theory in Combinatorics: It is important to know how elements in the Hamming space are related, especially intersected, to handle extremal sets. Theorem 3.4 has a strong link to Erdös and Rado’s sunflower lemma. In the previous post, I wrote that extension generators are a generalization of sunflower. To be more precise, Theorem 3.4 with Lemma 2.7 immediately implies the existence of a q-sunflower in most cases covered by the sunflower lemma. I explained it in the paragraph right after Proposition 3.7 in the paper.The theorem claims a stronger statement in such a way that if you extend m-sets into l-sets, almost all the cases of q disjoint l-sets with a small generator contain a q-sunflower.
The mathematical structure of the Hamming space is intriguing. Please take a look at my past findings. Let U be a family of m-sets.
a) Its l-extension Ext(U, l) becomes a majority when m is small and U is not too sparse (please click): The main theorem means that if we remove k edges from an n-clique, almost all l-cliques are gone when lk is asymptotically larger than n2. For example, if k=n5/3, a majority of √n-cliques don’t exist no matther which k edges are eliminated.
b) The Hamming Distance between Two m-Set Families (please click): If the sparsity of U is O( m1-ε ) (ε: small constant), and we have a similar family U’, their Hamming distance is asymptotically smaller than m. The bound O(m / log m) is shown in the paper. There is a way to improve it into O(m / exp( log2 log m) ).