# «Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

The generalization to d-uniform hypergraphs follows by using polynomials of degree d−1 instead of linear functions over Fq. Their use guarantees requirement (i) in Lemma 3.3.

Regarding requirement (ii), the following proof shows that the case d 2 reduces to the case d = 2. For arbitrary d ≥ 2, we fulﬁll requirement (ii) by restricting the coeﬃcient of degree d − 1 to a set that contains no nontrivial arithmetic progressions of length three, namely the set A ⊆ Fq determined in Lemma 4.1.

** Lemma 3.3 (restated).**

For any integers p ≥ d ≥ 2 and t 0 there exists an p-partite d-uniform hypergraph P on O p · max(p, t1/d+o(1) ) vertices such that (i) the hyperedges of P partition into t cliques K1,..., Kt on p vertices each, and (ii) P contains no cliques on p vertices other than the Ki ’s.

Furthermore, for any ﬁxed d, the hypergraph P and the Ki ’s can be constructed in time polynomial in p and t.

Proof (of Lemma 3.3). Let q be the smallest prime such that q ≥ p and |A| · q d−1 ≥ t, where A denotes the set given by Lemma 4.1. We have that q = O(max(p, t1/d+o(1) )) and can compute q and the set A in time polynomial in p and t.

Let V (P ) = [p] × Fq. We consider polynomials of degree at most d − 1 over Fq whose coeﬃcient of xd−1 belongs to A. Note that there are |A| · q d−1 ≥ t such polynomials. For i ∈ [t], let hi denote the ith such polynomial in lexicographic order, and let Ki be the complete d-uniform hypergraph on vertex set V (Ki ) = {(j, hi (j)) | j ∈ [p]}. We deﬁne the d-uniform hypergraph P as the union of the t cliques Ki. The hypergraphs P and Ki can be constructed in time polynomial in p and t.

In order to argue property (i), it suﬃces to observe that every hyperedge of P is contained in at most one of the Ki ’s. This follows because the requirement that a given hyperedge of P belongs to Ki is equivalent to stipulating the value of hi on d distinct values j ∈ [p], which uniquely determines hi as a polynomial of degree at most d − 1 over Fq, and therefore determines i.

In order to argue property (ii), we need to establish the following for any function h : [p] → Fq : If for every subset D ⊆ [p] of size d there exists an i ∈ [t] such that h

4. Packing Edge-disjoint Cliques and hi agree on D, then there exists an i ∈ [t] such that h and hi agree on all of [p]. The property follows by applying the next claim to successive values of j ∈ [p − d], where qk denotes the polynomial hi which the hypothesis gives for the subset D = [j, j + d] \ {k}.

Claim. For each k ∈ [j, j + d], let qk be a polynomial of degree at most d − 1 such that the set of coeﬃcients of degree d − 1 of the qk ’s contains no nontrivial arithmetic progression of length three. If for all k, ∈ [j, j + d], the polynomials qk and q agree on [j, j + d] \ {k, }, then the polynomials qk are all the same.

We prove the claim by induction on d. We already argued the base case d = 2, captured by Figure 4.1b, earlier in Section 4. For the inductive step, assume the claim holds for d−1 and let us prove it for d. Let qj,..., qj+d be polynomials as in the claim. For each k ∈ [j, j + d − 1], deﬁne qk as the diﬀerence quotient ∆j+d (qk ), i.e., qk : [j, j + d − 1] → Fq such that qk (x) = (qk (x) − qk (j + d))/(x − j − d) for x ∈ [j, j + d − 1]. Note that qk is a polynomial of degree at most d − 2 whose coeﬃcient of degree d − 2 equals the coeﬃcient of qk of degree xd−1. Moreover, for k, ∈ [j, j + d − 1], the polynomials qk and q agree on each x ∈ [j, j + d − 1] \ {k, } because the polynomials qk and q agree on both x and j + d. Thus, by the induction hypothesis, all polynomials qk are the same. By the deﬁnition of qk = ∆j+d (qk ) and the fact that the polynomials qk for k ∈ [j, j + d − 1] agree on j + d, this implies that the polynomials qk for k ∈ [j, j + d − 1] are all the same, say q. All that remains to show is that the polynomial qj+d also coincides with q. The latter follows because qj+d is a polynomial of degree at most d − 1 which agrees with the polynomial q of degree at most d − 1 on all d points in [j, j + d − 1].

Related Constructions After we developed our construction we learned about similar applications of high-density subsets of the integers without nontrivial arithmetic progressions of length three.

Back in 1976, Ruzsa and Szemerédi [RS78] constructed dense three-partite graphs whose edges partition into triangles and that contain no other triangles. Their construction corresponds to the case (d, s) = (2, 3) of our Packing Lemma, and appears between any three consecutive columns of our construction for d = 2 and general p. Our geometric derivation of the arithmetic progression condition (4.1), as captured in Figure 4.1b, may be new; all the derivations we have found in the literature work by manipulating equations in a – to us – less intuitive way.

Diﬀerent aspects of the Ruzsa-Szemerédi construction matter for the various applications we know of in the theory of computing. For their soundness analysis of graph tests for linearity, Håstad and Wigderson [HW03] use the interpretation that for each of the q points in the ﬁrst column, the triangles involving that point span an induced matching of q 1−o(1) edges between the other columns.

Another application area is the lower bounds for testing the graph property of being F -free, where F is some ﬁxed graph. An -tester for this property accepts all graphs that are F -free, and rejects all graphs that are at least away from being F -free, i.e., from which at least n2 edges need to be removed to make it F -free [GGR98]. A strategy for proving lower bounds on the number of queries of such a tester is to construct highdensity graphs G with the following properties: (i) the edges of G partition into copies of F, and (ii) G contains few other copies of F so the total number of copies of F in G is signiﬁcantly less than expected in a random graphs of the same density as G [Alo02].

Qualitatively, (i) implies that G is far from being F -free, and (ii) implies that testers with few queries have a small probability of detecting a violation of F -freeness on input G.

Alon and coauthors [Alo02, AS06, AS04, AKKR08, AS05] constructed such graphs G for various F based on the work of Ruzsa and Szemerédi [RS78].

The requirements for our application are similar but not identical to the ones for property testing. On the one hand we only need to consider the cases where F is a clique; on the other hand the graphs G cannot contain any copy of F other than those in which the edges partition. Our actual construction is very similar to the one Alon and Shapira [AS05] develop. Their construction would also work for our purposes. Our proof diﬀers from theirs and makes the arithmetic progression condition more transparent. Our construction slightly improves1 on theirs as we only restrict the highest-order coeﬃcient to the set A, whereas they restrict all coeﬃcients to that set.

Notes The content of this chapter is joint work with Dieter van Melkebeek and appeared in [DvM10].

This allows us to relax the condition q( ) = max{m : (f (m))k ≥ } in Lemma 4.1 of [AS05] to q( ) =

5. Exponential Time Counting Complexity

5.1. Counting Independent Sets In this section, we establish Theorem 1.9, the hardness of counting independent sets and of #2-Sat. For the proof, we make use of the ETH-hardness of the following problem.

Name Unique 3-Sat.

Input 3-CNF formula ϕ with m clauses and at most one satisfying assignment.

Decide Is ϕ satisﬁable?

Calabro et al. [CIKP03] use an isolation lemma for d-CNF formulas to show that solving this problem in subexponential time implies that the (randomized) exponential time hypothesis fails.

** Theorem 5.1 (Corollary 2 of [CIKP03]).**

ETH holds if and only if Unique 3-Sat requires time exp(Ω(m)).

We are now in the position to prove Theorem 1.9.

** Theorem 1.9 (restated).**

Counting independent sets and #2-Sat both require time exp(Ω(m)) under ETH, where m is the number of edges and clauses, respectively.

Proof. Let ϕ be an instance of Unique 3-Sat with m clauses. We construct a graph G with O(m) edges that has an odd number of independent sets if and only if ϕ is satisﬁable.

For each variable x, we introduce vertices x and x, and the edge (xx). This makes sure that any independent set of G chooses at most one of {x, x}, so we can interpret the independent set as a partial assignment to the variables of ϕ. For each clause c = ( 1 ∨ 2 ∨ 3 ) of ϕ, we introduce a clique in G that consists of seven vertices c1,..., c7.

These vertices correspond to the seven partial assignments that assign truth values to the literals 1, 2, and 3 n such a way that c is satisﬁed. Any independent set of G contains at most one ci for each clause c. To ensure that the independent set chooses the variables and partial assignments of the clauses consistently, we add an edge for every ci and every variable x occurring in the clause c: If the partial assignment that corresponds to ci sets x to true, we add (ci x) to G; otherwise, we add (ci x) to G. To ﬁnalize the construction, we introduce guard vertices gx and gc for every variable x and every clause c, along with the edges (gx x), (gx x), and (gc ci ) for i = 1,..., 7.

We now prove that G has the required properties. First, any independent set contains at most n literal vertices and at most m clause vertices. Good independent sets are those that contain exactly n literal and m clause vertices (and no guard vertex). Good independent sets correspond to the satisfying assignments of ϕ in a natural way. We

** **

**5. Exponential Time Counting Complexity**

now show that the number of bad independent sets is even. For this, let S be a bad independent set, that is, S is disjoint from {x, x} for some x or it is disjoint from {c1,..., c7 } for some clause c. By construction, the neighborhood of either gx or gc is disjoint from S. Let g be the lexicographically ﬁrst guard vertex whose neighborhood is disjoint from S. Both the sets S \ {g} and S ∪ {g} are bad independent sets and S is one of these sets. Formally, we can therefore deﬁne a function that maps these sets onto each other. This function is a well-deﬁned involution on the set of bad independent sets, and it does not have any ﬁxed points. Therefore, the number of bad independent sets is even, and the parity of the number of independent sets of G is equal to the parity of the number of satisfying assignments of ϕ.

The above reduction shows that an exp(o(m))-time algorithm for counting independent sets modulo 2 implies an exp(o(m))-time algorithm for Unique 3-Sat. By Theorem 5.1, this implies that ETH fails.

To establish the hardness of #2-Sat, we reduce from counting independent sets. Let G be a graph. For each vertex v, we introduce a variable v, and each edge (uv) becomes a clause (u ∨ v). The satisfying assignments of the so constructed 2-CNF formula are in one-to-one correspondence with the independent sets of G.

5.2. The Permanent This section contains the proof of Theorem 1.10. With [0, n] = {0, 1,..., n} we establish the reduction chain #3-Sat Perm−1,0,1 Perm[0,n] Perm01 while taking care of the instance sizes.

** Theorem 1.10 (restated).**

(i) Perm−1,0,1 and Perm[0,n] require time exp(Ω(m)) under #ETH.

(ii) Perm01 requires time exp(Ω(m/ log n)) under #ETH.

(iii) Perm01 requires time exp(Ω(m)) under ETH.

Proof. To establish (i), we reduce #3-Sat in polynomial time to Perm−1,0,1 such that 3CNF formulas ϕ with m clauses are mapped to graphs G with O(m) edges. For technical reasons, we preprocess ϕ such that every variable x occurs equally often as a positive literal and as a negative literal x (e.g., by adding trivial clauses of the form (x ∨ x ∨ x)

## ¯ ¯¯

to ϕ). We construct G with O(m) edges and weights w : E → {±1} such that #Sat(ϕ) can be derived from per G in polynomial time. For weighted graphs, the permanent isThe sum above is over all cycle covers C of G, that is, subgraphs (V, C) with an in- and outdegree of 1 at every vertex.

In Figure 5.1, the gadgets of the construction are depicted. For every variable x that occurs in ϕ, we add a selector gadget to G. For every clause c = 1 ∨ 2 ∨ 3 of ϕ, we

add a clause gadget to G. Finally, we connect the edge labelled by a literal in the selector gadget with all occurrences of in the clause gadgets, using equality gadgets.

This concludes the construction of G.

The number of edges of the resulting graph G is linear in the number of clauses. The correctness of the reduction follows along the lines of [Pap94] and [BD07]. The satisfying assignments stand in bijection to cycle covers of weight (−1)i 2j where i (resp. j) is the number of occurrences of literals set to false (resp. true) by the assignment, and all other cycle covers sum up to 0. Since we preprocessed ϕ such that i = j holds and i is constant over all assignments, we obtain per G = (−2)i · #Sat(ϕ).

For the second part of (i), we reduce Perm−1,0,1 in polynomial time to Perm[0,n] by interpolation: On input G, we conceptually replace all occurrences of the weight −1 by a variable x and call this new graph Gx. We can assume that only loops have weight x in Gx because the output graph G from the previous reduction has weight −1 only on loops. Then p(x) = per Gx is a polynomial of degree d ≤ n.

If we replace x by a value a ∈ [0, n], then Ga is a weighted graph with as many edges as G. As a consequence, we can use the oracle to compute per Ga for a = 0,..., d and then interpolate, to get the coeﬃcients of the polynomial p(x). At last, we return the value p(−1) = per G. This completes the reduction, which queries the oracle d+1 graphs that have at most m edges each.