Given a $k$-uniform hypergraph $H$ on $n$ vertices, an even cover in $H$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalization of cycles in graphs and are equivalent to linearly dependent subsets of a system of linear equations modulo $2$. As a result, they arise naturally in the context of well-studied questions in coding theory and refuting unsatisfiable $k$-SAT formulas. Analogous to the irregular Moore bound of Alon, Hoory, and Linial [3], Feige conjectured [8] an extremal trade-off between the number of hyperedges and the length of the smallest even cover in a $k$-uniform hypergraph. This conjecture was recently settled up to a multiplicative logarithmic factor in the number of hyperedges [12, 13]. These works introduce the new technique that relates hypergraph even covers to cycles in the associated Kikuchi graphs. Their analysis of these Kikuchi graphs, especially for odd $k$, is rather involved and relies on matrix concentration inequalities.
In this work, we give a simple and purely combinatorial argument that recovers the best-known bound for Feige’s conjecture for even $k$. We also introduce a novel variant of a Kikuchi graph which together with this argument improves the logarithmic factor in the best-known bounds for odd $k$. As an application of our ideas, we also give a purely combinatorial proof of the improved lower bounds [4] on 3-query binary linear locally decodable codes.
]]>A set S of hyperedges in a hypergraph H is an even cover if E*S E := {v * v(H) : v belongs to an odd number of hyperedges in S} = '.
Equivalently, S is an even cover if E*S v E = 0 over F 2 , where v E denotes the characteristic vector of E. In this work, we are interested in understanding the extremal trade-offs between the size of a k-uniform hypergraph H and girth, i.e., the number of hyperedges in the shortest even cover in it.
Even Covers and Linear Dependencies Even covers in k-uniform hypergraphs correspond to linearly dependent subsets of a system of k-sparse (i.e., each equation has exactly k non-zero coefficients) linear equations over F 2 . To see why, let us associate a variable x v for each v * H and the |E|-sparse equation v*E x v = b E for b E * F 2 with each edge E in H. Then, observe that for any even covers S, the left hand sides of the equations corresponding to E * S add up to 0 and are thus linearly dependent. Thus, size vs girth trade-offs for k-uniform hypergraphs correspond to the largest possible size 3 of the minimum linear dependency in a system of linear equations with m equations in n variables.
Such k-sparse linear equations arise naturally as the parity check equations for low-density parity check error correcting codes. The size vs girth trade-offs for k-uniform hypergraphs thus correspond to rate vs distance trade-offs for such codes.
By the equivalence between even covers and linear dependencies, it is clear that every hypergraph with m g n + 1 hyperedges must have an even cover of length at most n + 1 and this is clearly tight. The natural question is then: How does the trade-off between m and the maximum possible girth look as m increases beyond n + 1?
Size vs Girth Trade-offs When H is a 2-uniform hypergraph, an even cover is simply an even subgraph, i.e., a subgraph with all vertices of even degree. Such a subgraph is a union of edge-disjoint cycles in H. An even cover with smallest number of edges must in fact be a simple cycle and thus, its length must be the girth of the graph H. The extremal trade-off between the size of H (i.e., the number of edges in the graph) and its girth was conjectured by Bollóbas and confirmed by Alon, Hoory and Linial [3] who proved the irregular Moore bound -every graph on n vertices with average degree d has girth at most 2+log d21 (n)+. It is an outstanding open problem whether the constant 2 in this bound can be further improved (for the best known constant, see [17]).
For k-uniform hypergraphs with k > 2, the size vs girth trade-offs were first studied by Naor and Verstraete [20] through applications to rate vs distance trade-offs for LDPC codes discussed above. They showed that every H with m g n k/2 log O (1) (n) hyperedges on n vertices must contain an even cover of length O(log n). The log O (1) (n) factor was further improved to a O(log log n)-factor in a subsequent work of Feige [8]. For k = 2, this recovers a coarse version of the irregular Moore bound. For k > 2, however, there is an interesting regime between the two extreme thresholds of m = n + 1 (with maximum possible girth of n + 1) and m > n k/2 log O (1) (n) (with maximum possible girth of O(log n)).
Feige's Conjecture In 2008, Feige [8] formulated a conjecture about this in-between regime that suggests a smooth interpolation between the two extremes noted above.
Conjecture 1.1. Fix any k * N. Then, there exists a sufficiently large C > 0 such that for sufficiently large n * N and every 3 * N, every k-uniform hypergraph H with m g Cn( n 3 ) k/221 hyperedges has an even cover of length at most O(3 log 2 n).
The quantitative behavior above can be verified for random hypergraphs (up to a multiplicative factor of log(n) in m). Indeed, Feige's conjecture was based on the hypothesis that random hypergraphs are approximately extremal for the purpose of avoiding short even covers. The motivation for this conjecture comes from the question of showing existence of (and/or efficiently finding) polynomial size refutation witnesses -easily verifiable witnesses of unsatisfiability of -randomly chosen k-SAT formulas parameterized by the number of clauses. Feige's conjecture implies that the result of Feige, Kim and Ofek [9] -which showed that random 3-SAT formulas with m g O(n 1.4 ) clauses admit a polynomial size refutation witness with high probability -will extend to the significantly more general setting of smoothed 3-SAT formulas, in addition to simplifying the construction and arguments based on the second moment method in [9].
Until recently, not much was known about Feige's conjecture except for the work of Alon and Feige [2] that showed a suboptimal version for the case of k = 3 and that of Feige and Wagner [10] that built an approach to the problem of even covers by viewing them as an instance of generalized girth problems about hypergraphs. In 2022, Guruswami, Kothari and Manohar [12] proved Feige's conjecture up to an additional loss of log 2k (n) multiplicative factor in m via a spectral argument applied to the Kikuchi graph, a graph with an appropriate algebraic structure, built from the given hypergraph. Their argument was simplified and tightened to reduce the loss down to a O(log n) multiplicative factor in m by Hsieh, Kothari and Mohanty in [13]. In this work, as we will soon discuss, we give a substantially simpler, purely combinatorial argument that recovers their result and improves the logarithmic factors for hypergraphs of odd uniformity.
Linear Locally Decodable Codes A binary error correcting code is a map C : {0, 1} m ³ {0, 1} n , where we view the input as a m-bit "message" and the output as an n-bit codeword. By a slight abuse of notation, we use C to also denote the set of all codewords: {y | #x * {0, 1} m , C(x) = y}. We say that C is linear if, when viewing the input and output as F m 2 and F n 2 , respectively, C is a F 2 -linear map. A code C is called (q, •)-locally decodable (LDC) if, in addition, it admits a local decoding algorithm. Such a local decoding algorithm takes as input any target message bit i for 1 f i f m and a corrupted codeword y such that dist(y, C(x)) f • for some x * {0, 1} m , where dist counts the fraction of coordinates that y and C(x) differ. The goal of the algorithm is to access at most q locations in y and output x i correctly with high probability over the choice of the q locations. In other words, the local decoder can decode any bit of the message by reading at most q locations of the received corrupted codeword.
Locally decodable codes are intensely investigated in computer science (see the survey [24] for background and applications) with applications to probabilistically checkable proofs, private information retrieval [23], and worst-case to average-case reductions in computational complexity theory. They also have deep connections with additive combinatorics and incidence geometry [5]. We are typically concerned with codes that are locally decodable with very few queries, such as q = 2 or 3, and the fundamental question is the smallest possible n = n(m) such that there is a (q, •)-binary LDC C : {0, 1} m ³ {0, 1} n . Classical results have essentially completely resolved the case of q = 2 and we know that a blocklength of n f 2 O(m) (for a constant •) can be achieved by Hadamard codes with a matching lower bound [11,15]. The case of q = 3 already presents wide gaps, where until recently, the best known lower bound [11,15] was n g Õ(m 2 ), while the best known construction [7,22] gives a 3-query binary linear code with n f exp(exp(O( : log m log log m))). Recently, using spectral refutations via Kikuchi matrices, Alrabiah et. al. [4] improved the quadratic bound above to obtain a lower bound of n g m 3 /poly log m for 3-query binary, locally decodable codes.
The arguments in the most recent works on Feige's conjecture and locally decodable codes are involved and in particular, require the use of matrix concentration inequalities. Our main contribution is a short, purely self-contained combinatorial argument that recovers their result. This technique might be useful for other similar questions and we illustrate it below, by an application to another well studied problem. Our arguments for Feige's conjecture also utilize Kikuchi graphs introduced in the above prior works. We then introduce a new variant of a Kikuchi graph that, when combined with our combinatorial argument, improves on their results for the case of odd k. Theorem 1.2. For all k, there is a sufficiently large C such that the following holds for all sufficiently large n and k f l f n:
hyperedges contains an even cover of size O(l log n).
We remark that in the above theorem for odd k, we require only a very mild restriction on l that l f n/ log 2 n, which is purely a technical artefact of our proof. In fact, if l g n/100 log n, Feige's conjecture holds trivially from a standard linear algebra argument (see Lemma 2.4). For n/ log 2 n f l f n/100 log n, one can use the some arguments as in the proof of the above theorem (namely Section 4.4) to show the same bound as in part (i) for this range. The ideas we developed to prove the above theorem naturally extend to the setting of linear binary locally decodable codes. We can use an altered version of these arguments to show the following result previously obtained by Alrabiah et. al [4]. As in the above results, their proof involves spectral arguments on signed adjacency matrices of Kikuchi graphs based on matrix concentration inequalities. The proof we give is simple and purely combinatorial. Although the work in [4] deals also with non-linear codes, we remark that all known constructions of locally decodable codes including the ones discussed in the previous section are linear.
Theorem 1.3. Let C : F m 2 ³ F n 2 be a linear map that gives a 3-query locally decodable code with distance • > 0. Then, m f Kn 1/3 log n for K = 10 7 /• 2 .
Finding structures in edge-colored graphs We finally remark that the results in this paper, which we discussed above, are proven by reducing both our results to the one of finding a subgraph, satisfying certain restrictions, in an edge-colored graph. Recall that an edge-colored graph is a graph along with a coloring of the edges so that no vertex has two or more edges of same color incident on it. Finding structures in edge-colored subgraphs is a powerful method in Combinatorics and has been used to study several well-known questions. For example, the famous conjecture of Ringel from 1963 says that the edges of the complete graph K 2n+1 can be decomposed into copies of any tree on n vertices. It was observed by Kötzig that this problem can be reduced to showing that a certain edge-coloring of K 2n+1 contains a rainbow copy of any tree on n vertices. The existence of such rainbow trees was recently established in [19].
Another famous application is the resolution of the Ryser-Brualdi-Stein conjecture which was open for more than 60 years until it was recently solved by Montgomery [18]. It states that every Latin square n × n contains a transversal (i.e., a collection of cells which do not share the same row, column or symbol) of size n 2 1. This can be reduced to finding a rainbow matching missing only one color in any proper edge-coloring of the complete bipartite graph K n,n . Finally, a well-studied problem in additive combinatorics studies the additive dimension of sets with small doubling, in any group. This problem had been solved for abelian groups by Sanders [21]. For general groups, this question was reduced by Alon et. al [1] to a well-known problem (see [14]) of finding a rainbow cycle in a properly edge-colored graph with sufficiently many edges, for which Alon et. al provide an almost tight bound.
Definition 2.1. All logarithms are taken base 2. Given a graph G, we let d(G) denote its average degree. Let H be a hypergraph. We let V (H) denote its vertex set and E(H) its edge-set. Similarly, we let v(H) denote the size of its vertex set and e(H) denote the number of hyperedges. Given a hypergraph H, a bucket is a pair (E, X) where E is a set of hyperedges in H which all contain the set of vertices X ¦ V (H). Given a hypergraph H, an (m, t)-bucket decomposition is a partition of the hyperedges of
In this section, we collect some lemmas which will be useful throughout the paper. The first is the standard tool used for finding subhypergraphs with large minimum degree. Lemma 2.2. Let H be a hypergraph on n vertices and nd hyperedges. Then, there exists an induced sub-hypergraph H 2 ¦ H with at least nd/2 hyperedges and minimum degree at least d/2.
Proof. We perform the following process. Start with H 2 := H, and while it has a vertex v with degree less than d/2 in H 2 , remove v and its incident hyperedges from H 2 . Notice that at any point, H 2 has at least e(H) 2 nd/2 g nd/2 edges and thus, the process must stop. The final H 2 is then a sub-hypergraph with at least nd/2 edges and minimum degree at least d/2.
The next lemma is simply an observation on finding trivial bucket decompositions in hypergraphs.
Lemma 2.3. Let H be a hypergraph on n vertices and nd hyperedges. Then, there exists an induced sub-hypergraph H 2 ¦ H with at least nd/2 hyperedges and a (d/2, 1)-bucket decomposition.
Proof. We do the following process. First, set H 2 := '. While e(H 2 ) < nd/2, consider the hypergraph H \ H 2 ; it has at least nd/2 hyperedges and thus there is a vertex v with degree at least d/2; then, take a a collection E ¦ H \ H 2 of d/2 hyperedges containing v and add them to H 2 . Note that at the end of the process the hypergraph H 2 is as desired since the collections E taken at each step give the (d/2, 1)-bucket decomposition.
The next lemma is a simple application of linear algebra in order to show that hypergraphs with sufficiently many hyperedges contain even covers (with no size restriction).
Lemma 2.4. Let H be an n-vertex hypergraph with at least n + 1 hyperedges. Then, H contains an even cover.
Proof. For each hyperedge E in the hypergraph consider its characteristic vector v E in Z n 2 . Note that since we have at least n + 1 vectors, they must be linearly dependent, thus implying an even cover.
The next lemma concerns finding colored cycles in edge-colored graphs. Although a variant of it already appeared in [14], we include a the proof for sake of completeness.
Lemma 2.5. Let G be an n-vertex graph and C a set of colors so that each edge in G is assigned a set of s colors in C. Suppose that for every vertex v * G and color c * C, the number of edges incident on v whose assigned set of colors contains c is at most d(G)/20s log n. Then, G contains a closed walk, of size at most 2 log n, such that some color appears exactly once.
Proof. Let l := log n and r := d(G)/20s log n. For sake of contradiction, suppose G contains no such closed walk of size 2l. We will double-count the number of rainbow paths in G of size l -by rainbow we mean that no color is assigned to more than one edge of the path. In order to give a lower bound on the number of rainbow paths, note first that Lemma 2.2 implies that G contains a subgraph G 2 ¦ G with minimum degree at least d 2 = d(G)/4. We can then take a vertex v * G 2 and greedily count the number of rainbow paths in G 2 of the form vv 2 v 3 . . . v l+1 . Indeed, we have at least d 2 options for v 2 ; then, given the assumption on G that every color is incident to a vertex in at most r edges and that G has no rainbow cycle of size at most 2l, we have at least d 2 2 sr options for v 3 ; with the same reasoning we have at least d 2 2 2sr options for v 4 and so on. Concluding the number of such rainbow paths is at least
On the other hand, since there is no closed walk as described above, we can upper bound the number of rainbow paths as follows. For each pair of vertices x, y (there are at most n 2 of them), observe that if there is a rainbow path between them using a set of colors S ¢ C, then any other rainbow path between x and y must use the same set of colors S. Now, the set S has size sl and thus, we can upper bound the number of rainbow paths xz 1 z 2 . . . z l y of size l between x and y as follows. Choosing z 1 can be done by choosing a color c 1 * S and then choosing an edge incident on v which contains the color c 1 . By assumption, there are at most slr such choices and the choice of the rest of the vertices z 2 , . . . , z l21 can be done in the same way. Concluding, there are at most (slr) l such paths. Therefore, there are at most n 2 • (slr) l = (4slr) l = (0.8d 2 ) l rainbow paths of size l, which is a contradiction given the previous paragraph.
In this section, we recall standard results that reduce proving a lower bound on the blocklength of a linear locally decodable code to establishing the existence of a special kind of even cover in a properly edge colored hypergraph.
We will use the following standard reduction from any locally decodable code to one in the normal form (with only constant factor differences in the parameters). We direct the reader the monograph [24] for a more general result that holds even for non-linear codes. We use • to denote addition modulo 2 (i.e., over F n 2 ) in the following. Proposition 2.6 (LDCs in normal form, see Theorem 8.1 in [6]). Let C : F m 2 ³ F n 2 be a binary, linear 3-query locally decodable code with distance • > 0. Then, there is a collection of 3-uniform hypergraph matchings H 1 , H 2 , . . . , H m of size g •n/6 one for each message bit, such that for every x * F m 2 , for every i * [m] and every hyperedge e * H i , • j*e C(x) j = x i .
As an immediate corollary of the normal form of a locally decodable code, we obtain the following useful combinatorial characterization:
2 be a binary, linear 3-query locally decodable code with distance • > 0 and let H 1 , H 2 , . . . , H m be the associated matchings as in Proposition 2.6 of size g •n. Then, for any even cover {e 1 , e 2 , . . . , e t } in the multi-hypergraph * if[m] H i , each H i contributes an even number of hyperedges.
Proof. Suppose not and say {e 1 , e 2 , . . . , e t } is an even cover that contains an odd number of hyperedges from, say, H 1 . Then, choose x = (1, 0, . . . , 0) * F m 2 and observe that on the one hand, • ift • j*e i C(x) j = 0 because C i s form an even cover. But, on the other hand,
contributes an odd number of hyperedges to {e 1 , e 2 , . . . , e t } and for every hyperedge e * H 1 , • j*e C(x) j = x 1 . This is a contradiction.
By thinking of each hyperedge in H i as having the color i, the hypergraph * ifm H i is a properly edge colored hypergraph. Thus, in light of Lemma 2.7, Theorem 1.3 is implied by the following theorem that we will establish in this work.
Theorem 2.8. For all sufficiently small ³ > 0, there is K := 10 7 /³ 2 > 0 such that the following holds for all sufficiently large n. Let H be a 3-uniform n-vertex hypergraph which is properly edge-colored with Kn 1/3 log n colors so that each color has at least ³n hyperedges. Then, H contains an even cover such that some color appears exactly once.
3 Even k, and some ideas for odd k
To illustrate our main ideas, we start this section by giving a very short solution of Feige's problem up to a logarithmic factor for all even k. In the next section we will discuss how to use the methods inspired by this proof for the odd values of k.
Proof of Theorem 1.2 (i). Let H be a hypergraph satisfying the assertion of the theorem. By choosing constant C = 10 k we can assume that H has at least 10 k n (n/l) k/221 log n edges. We define an edge-colored graph G, called the Kikuchi graph, as follows.
• The vertex set of G consists of all l-element subsets of the vertex of H, i.e., V (G) := [n] l .
• We define an edge S ± ³ T for two S, T * V if there exists an edge E * H such that S • T = E and |S + E| = |T + E| = k/2. Moreover, we color the edge S ± ³ T in G with color E.
Let us make some important remarks about G. First, note that the coloring of its edges is well-defined and proper. Indeed, the first is the case since the color of the edge S ± ³ T is uniquely defined by S • T . The latter also holds since given S * V and E * H, there exists at most one T * V such that S • T = E. We now show the following claim. Proof. To prove this we apply Lemma 2.5. Note that G has N := n l vertices and each edge E * H creates at least
edges of G, since we need to choose the intersections S + E, T + E (which are disjoint and of size k/2) and then the set
where we used that l f n/ log n by Lemma 2.4 and that l g k. Therefore
Therefore, since G is properly-colored, Lemma 2.5 implies that it contains the desired type of closed walk of size at most 2 log N f 2l log n.
To finish, we can take the closed walk S 1 , S 2 , . . . , S r in G given above and consider the collection C of edges in H which appear an odd number of times as colors in this walk -that is, recalling the definition of G, those edges E * H such that E = S i • S i+1 (the indices being taken modulo r) for an odd number of 1 f i f r. Since 1fifr (S i • S i+1 ) = ', we have that E*C E = ' and so C is an even cover of size at most r = O(l log n), as desired.
We now briefly discuss the methods for proving Theorem 1.2 in full generality. In the previous section, in order to solve Feige's problem for even k, we defined an edge-colored graph G based on the hypergraph H. Crucially, the graph G had the following properties.
1. G has many edges and is properly edge-colored.
Then we just applied Lemma 2.5 to find a the desired even cover in H.
In the case of odd k our general strategy will be similar. We will also want to define an edge-colored graph G based on our hypergraph H such that some appropriate versions of the properties above hold. For this, we will define two different variants of the Kikuchi graph defined in the previous section. The first version is given in Section 4.4 and has already appeared in previous works (see [12] and [13]) and can alone, be used to show a bound as in part (i) of Theorem 1.2 for odd values of k. To get the improved part (ii) of Theorem 1.2 for odd k, another variant is necessary. In Section 6.1, we introduce then the flower Kikuchi graph.
Before using these Kikuchi graphs however, we will need to clean our hypergraph H using the tools in Section 4. Specifically, we will be able to reduce our problem to considering a hypergraph H with a nice bucket decomposition and co-degree assumptions (see Lemma 4.5). Then, based on the outcome of this Lemma, we will either use the Kikuchi graph on H defined in Section 4.4 or the new flower Kikuchi graph.
In the first case, the graph is edge-colored, but each edge receives now a pair of colors (C, C 2 ), where each color C is an edge in H. Due to the additional assumptions we now have on the hypergraph H we can show that the Kikuchi graph contains a subgraph G 2 ¦ G with the following properties similar to the ones before.
1. G 2 has many edges and is such that every vertex is incident to at most d(G 2 )/80 log |G 2 | edges containing a given color.
2. A closed walk in G 2 in which some color appears once implies an even cover in H.
Then, like before, applying Lemma 2.5 implies the desired even cover in H. As mentioned above, finding G 2 is only possible because of the additional assumptions on H. In Proposition 4.9 we state the crucial hypergraph property which implies the existence of such a G 2 . In the second case, the flower Kikuchi graph G is edge-colored, with each edge receiving a color C which is an edge of H. Like in the previous case, we can also then perform a (simpler) cleaning procedure to find a subgraph subgraph G 2 ¦ G with the same properties as those mentioned in the beginning of the section: G 2 has many edges and is properly colored; a closed walk in G 2 in which some color appears once implies an even cover in H. Then, applying Lemma 2.5 implies the desired even cover in H.
The problem of LDCs is very similar. As discussed in the introduction, we can reformulate this problem as finding a special even cover in an edge-colored hypergraph (see Theorem 2.8). The only difference here is that the hyperedges of the hypergraph are properly colored and we want to find an even cover where some color appears exactly once. We again will first clean our hypergraph using Lemma 4.1. Then we will show that the given Kikuchi graph defined in Section 4.4 will satisfy the property in Proposition 4.9 and thus gives the desired even cover in H.
In this section we present two tools for cleaning hypergraphs. As we mentioned in the previous section, the goal is to find hypergraphs with nice bucket decompositions and co-degree conditions. Here and later in the paper we will always assume that k is odd.
First, we need the following simple observation for general hypergraphs. Lemma 4.1. Let H be a k-uniform hypergraph and j f k. Then, for all t and e f e(H), there is a H 2 ¦ H such that one of the following holds.
1. e(H 2 ) g e(H) 2 e and every set R of size t has deg H 2 (R) < m.
2. H 2 has a (m, t)-bucket decomposition and e(H 2 ) g e.
Proof. Starting with H 0 := H, perform the following procedure. While H 0 has a set R of size t with deg H 0 (R) g m, then select m such hyperedges in H 0 which contain R and remove them from H 0 . When this process stops, if e(H 0 ) g e(H) 2 e, then by taking H 2 = H 0 we have the first case. Otherwise by taking H 2 = H 2 H 0 we have the second case.
Next, we will prove a particular statement concerning Feige's problem. This will later allow us to reduce the general problem to considering a hypergraph with some co-degree assumptions.
2 -bucket decomposition by (E 1 , X 1 ), (E 2 , X 2 ), . . . and denote E i as {Y i , Z i }. By the pigeonhole principle we can find some j g k+1 2 such that considering only the buckets with |Y i + Z i | = j, will reduce the size of the hypergraph by at most a 2/k factor. Now, we construct a new 2(k 2 j)-uniform multihypergraph G on the same vertex set as H consisting of the hyperedges Y i • Z i . The key observation which is easy to check from this definition is the following. Observation 4.3. An even cover in G implies an even cover of twice the same size in H.
The above implies that we need only to show that G contains an even cover of size O(l log n). For this, note that 2(k 2 j) is even and e(G)
Thus we can directly imply Theorem 1.2 (i).
The above discussion together with the proof of Lemma 4.1 (applied with j = k+1
2 ) immediately imply the following corollary.
In this section we present a tool for finding a subhypergraph with both a nice bucket decomposition and co-degree assumptions. Given the lemmas in the previous section, we will need only to apply it to k-uniform hypergraphs with odd k in which no two hyperedges share more than k/2 vertices.
Lemma 4.5. Let H be an n-vertex k-uniform hypergraph with nd hyperedges such that no two hyperedges share more than k/2 vertices. Consider any function m : [+k/2+] ³ N + with m(1) f d/4k. Then, there exists a subhypergraph H 0 ¦ H with at least nd/k hyperedges and an index 1 f t f k/2 such that the following hold. 1) For all S ¦ V (H 0 ) with t < |S| f k/2, we have that deg H 0 (S) < m(|S|). 2) If t = 1, then H 0 has minimum degree at least m(1). If t g 2, then H 0 has a (m(t), t)-bucket decomposition. Proof. Set H 2 , . . . , H +k/2+ := ' and H 2 := H and repeat the following procedure as long as possible. Let r * [2, +k/2+] be maximal such that there exists some S ¦ V (H 2 ) with |S| = r with deg H 2 (S) g m(r).
Take exactly m(r) hyperedges in H 2 that contain S, remove them from H 2 and add them to H r . The process stops when such an r does not exist. Now, suppose first that this process goes until e(H 2 ) < e(H)/2. Then, we can stop the process at the first step in which that occurs. Note then that by pigenholing, one of the hypergraphs H r will have at least nd/k hyperedges. We then define H 0 := H r and observe that it satisfies the desired conditions.
Otherwise, the process stops while e(H 2 ) g e(H)/2 = nd/2. Note that since the process stopped, it must be that such an r no longer exists and thus, deg H 2 (S) < m(|S|) for all sets S with |S| g 2. Now, by Lemma 2.2, H 2 has a subgraph, which we take to be H 0 , with at least nd/4 hyperedges and minimum degree at least d/4 g m(1). Clearly, the conditions now are satisfied for t = 1.
We will now introduce the variant of the Kikuchi graph for an edge-colored hypergraph with a given (m, t)-bucket decomposition which we already mentioned in Section 3.2. Definition 4.6. Let H be an n-vertex edge-colored k-uniform hypergraph with an (m, t)-bucket decomposition with buckets {(E i , X i )} 1fifp . Given an l, we define the l-Kikuchi graph of H and this bucket decomposition to be an edge-colored graph G = (V, E) as follows. Let [n] × [2] denote two disjoint copies of [n], whose vertices are labeled 1 and 2 in order to distinguish between these sets. The vertex set V (G) consists of all subsets of [n] × [2] of size l. Each such set S * V is viewed as (S (1) , S (2) ), where S (1) , S (2) ¦ [n] have labels 1 and 2 respectively. For each i * [p] and each ordered pair (C, C 2 ) of hyperedges C, C 2 * E i , let C(1) be C := C \ X i labeled 1 and C2(2) be C2 := C 2 \ X i labeled 2. We add an edge between S, T * V , denoted S 2) and one of the following holds.
Further, the edge S µ T is said to be associated with the hyperedges C, C 2 in H and is colored by the pair (c, c 2 ) where c is the color of C in H and c 2 is the color of C 2 . Note that the Kikuchi graph defined here is more complicated than the one introduced in Section 3.1. We split the vertex set V into two copies of [n]. This is needed because the pairs C, C 2 in our definition of buckets may have intersection larger than t, meaning that |C
Taking C, C2 to be subsets of two different copies of [n] automatically makes C(1) , C2(2) disjoint, so that
Note also that we allow a vertex of the Kikuchi graph S ¦ [n] × [2] to contain two copies of some element in [n] with different labels.
The conditions in Definition 4.6 are such that S (1) and T (1) (the vertices in S, T labeled 1) have symmetric difference C(1) , while S (2) and T (2) (the vertices in S, T labeled 2) have symmetric difference C2 (2) . Moreover, we would like C(1) and C2(2) to be split evenly, but if k 2 t is odd, then we can only split them into k2t 2 and k2t 2 sized sets, and we must ensure that S and T have the same sizes.
Given the above Kikuchi graph, we also define associated hypergraphs H c which will be crucial for our proof. In Proposition 4.9 we will show that if these hypergraphs have hyperedges that are rather uniformly distributed, that is, that there is no set of vertices with too large co-degree, then H must contain an even cover of small size. Definition 4.7. For each color c of H, we define the (k 2 t)-uniform multihypergraph H c with vertex set [n] × [2] as follows: for each c-colored hyperedge C in H belonging to some bucket E i and a hyperedge C 2 = C also in E i , we put in H c all hyperedges F such that one of the following holds.
±22³ T is an edge of the Kikuchi graph G and C, C 2 have colors c, c 2 respectively, then both S and T contain in addition to common part S + T a hyperedge from H c + H c 2 . ±22³ T created by this pair. Then, on the further right are illustrated all hyperedges of H c (where c is the color of the hyperedge C) which are created in Definition 4.7 by the pair (C, C 2 ). Here, red and blue correspond to labels 1 and 2 respectively (recall that S, T ¦ [n] × [2] and H c has vertex set [n] × [2]).
Let us now note two important properties of the l-Kikuchi graph G. Observation 4.8. If G contains a closed walk whose edges are overall associated to a multi-set H 2 of hyperedges in H, then it is such that C*H 2 C = '. In particular, if there is some color which appears an odd number of times in H 2 , then H contains an even cover of size at most e(H 2 ) in which some color appears an odd number of times. Further, G has average degree at least e(H)(m 2 1)
Proof. We will briefly explain the average degree computation. The number of ordered pairs (C, C 2 ) of hyperedges in the same bucket is e(H)(m 2 1). Now, with the pair (C, C 2 ) fixed, choosing an edge
±22³ T can be viewed as a two-step choice. First, we choose the intersections C1 +S (1) , C1 +T (1) , C2 + S (2) , C2 + T (2) so that these intersections sizes are as required in Definition 4.6 -there are k2t
2 such choices. Once those intersections are chosen, the next step is to choose a set S + T = S \ F = T \ F 2 of size l 2 k + t out of 2n 2 2k + 2t vertices. Combining all of these, we get that the number of edges in G is e(H)(m 2 1) • k2t
. Since G has 2n l vertices, we have the desired average degree.
As anticipated by the above observations, we can use Kikuchi graphs to find even covers in hypergraphs.
Proposition 4.9. Let k be odd and H be an edge-colored n-vertex k-uniform hypergraph with nd hyperedges and an (m, t)-bucket decomposition. Let G be the l-Kikuchi graph of H and suppose that the following holds.
• For all colors c, hyperedges F * H c and 0 f j f k 2 t, the number of hyperedges
Then, H contains an even cover of size at most 2 log v(G) in which some color appears an odd number of times.
Proof. Our aim is to use Lemma 2.5. However, we might not be able to apply it directly to the Kikuchi graph G (which by Observation 4.8 would imply an even cover in H). This is because G might not have a well-behaved coloring -it could well be that there are vertices and colors which do not satisfy the condition of Lemma 2.5. Instead, it turns out that we will be able to delete some edges from G and get a subgraph G 2 ¦ G which does satisfy the necessary conditions. Let d(G) denote the average degree of G and for each ordered pair (C, C 2 ) of hyperedges in H with colors c, c 2 , we delete all edges S C,C 2 ±2³ T such that one of S or T is adjacent to more than d(G)/80 log v(G) edges with one of the colors c, c 2 . Let G 2 be the resulting graph. Note that if we can show that d(G 2 ) g d(G)/2, then Lemma 2.5 (with s = 2) implies that G contains a closed walk of size at most 2 log v(G) in which some color appears once. By Observation 4.8, this implies an even cover in H of size at most 2 log v(G) as desired.
The following claim clearly implies that d(G 2 ) g d(G)/2. Let C 1 , C 2 be any two hyperedges of H (with colors c 1 , c 2 respectively) in the same bucket E i . Claim 4.10. At least half of the edges with color-pair
Proof. To prove this claim it is enough to show that a uniformly chosen edge with color pair (C 1 , C 2 ) is deleted with probability at most 1/2. Note that with C 1 , C 2 fixed, choosing a uniformly random edge
±222³ T can be viewed as a two-step uniform choice. First, we choose at random the intersections C1 + S (1) , C1 + T (1) , C2 + S (2) , C2 + T (2) so that these intersections sizes are as required in Definition 4.6. This will, for S (and T ), fix a hyperedge F * H c 1 + H c 2 which is contained in S (and another hyperedge F 2 in H c 1 + H c 2 contained in T ). Secondly, once those intersections are chosen, the next step is to choose a uniformly random set S + T = S \ F = T \ F 2 of size l 2 k + t out of 2n 2 2k + 2t vertices. Now, we will upper bound the probability that such a random edge is not in G 2 . We will deal first with the case that S is incident to more than d(G)/80 log v(G) other edges with the color c 1 (and thus, the edge S µ T will not be in G 2 ) and will show that a random edge has this property with probability at most 1/8. The other four cases (S incident to too many edges of color c 2 , T incident to too many edges of color c 1 and T incident to too many edges of color c 2 ) are analogous and so, we will in the end have a total probability of deletion of at most 4/8 = 1/2. Suppose then that (C 3 , C 4 ) are two other hyperedges both in the same bucket and one of them has color c 1 -without loss of generality, assume it is C 3 . Suppose there exists an edge S C 3 ,C 4 ± 22 ³ T 2 for some other T 2 . Then, S must contain some additional hyperedge in H c 1 -let us denote this by E. For each such possible E, since S \ F is chosen uniformly, the probability that S contains it is at most
using the fact that in all our proofs we can assume that l f n/ log n. Furthermore, by assumption there are at most (d(G)/2000 log v(G)) • (n/l) k2t2j hyperedges of H c 1 with |E + F | = j. Therefore, the expected number of such edges S
Concluding, by Markov's inequality, that the probability that a random edge is deleted because of one of its endpoints and one of its colors is at most 0.1 < 1/8, as desired.
In this section, we will apply the previous tools to prove Theorem 2.8.
Proof of Theorem 2.8. Take K := 10 7 /³ 2 , let H be such a hypergraph and let l := n 1/3 . We can assume without loss of generality that we have d := Kl log n colors, each with precisely ³n hyperedges, so that our hypergraph has ³nd hyperedges. We will want to apply Proposition 4.9 in order to find such a special even cover. For this, let us first note that one of the following holds.
1. There is a H 2 ¦ H with e(H 2 ) g e(H)/2 with a (K log n, 2)-bucket decomposition.
2. There is a hypergraph H 2 ¦ H with e(H 2 ) g e(H)/4 such that it has a (³d/4, 1)-bucket decomposition and every set R of size two has deg
Indeed, this follows directly by applying first Lemma 4.1 with t = 2 and m = K log n. This gives that the first item holds or there is a H 2 ¦ H with e(H 2 ) g e(H)/2 and such that every set R of size two has deg H 2 (R) f K log n. For this second case, we can then apply Lemma 2.3 to find the (³d/4, 1)-bucket decomposition in the second item. Now we will show that in both cases above, Proposition 4.9 holds for the l-Kikuchi graph of the corresponding hypergraph H 2 , which for convenience we redenote as H.
Let us first suppose that (1.) holds and let us consider the l-Kikuchi graph G of H and the given bucket decomposition. Using that K = 10 7 /³ 2 and v(G) = 2n l f (2n) l , by Observation 4.8 (with k = 3 and t = 2), the l-Kikuchi graph G has average degree at least (³nd/2) • (K log n 2 1) • (l/2n) g 8000dl log(2n) g 8000d • log v(G). Also note that for each color c, the multihypergraph H c (from Definition 4.7) is 1-uniform, and thus consists of single vertices in [n] × [2]. Therefore, by Proposition 4.9 we need only to show that given a color c, an F * H c and a 0 f j f 1, the number of
For j = 0, the number of such F 2 is at most four times the number of hyperedges in H c which is 4(K log n)n = 4d • (n/l). To see this, recall that the hypergraph H is properly colored and therefore at each of its vertices there is only one bucket of size K log n containing a hyperedge C of color c -every other hyperedge C 2 in this bucket together with C gives then 4 hyperedges of H c -indeed there are four hyperedges of H c satisfying one of the items in Definition 4.7; these consist of the two labeled copies of the vertex in C \ C 2 and of the vertex in C 2 \ C. For j = 1, let the hyperedge C * E(H) of color c be the one in Definition 4.7 forming F . The hyperedge F 2 * H c with F 2 = F can be obtained in two ways: first from some hyperedge C 2 of H incident to the same vertex as singleton the (uncolored) F ; this gives at most the maximum degree of H, i.e., d hyperedges; we can also obtain F 2 from any hyperedge C 2 * H from the same bucket as C. This gives at most K log n additional hyperedges. So in total d + K log n f 2d. Now assume that (2.) holds and recall that l = n 1/3 , d = Kl log n and v(G) f (2n) l where G is the l-Kikuchi graph of H and the given bucket decomposition. In this case H c is a multigraph for every color c. Observation 4.8 (with k = 3 and t = 1) implies that the l-Kikuchi graph has average degree at least
Hence d(G)/2000 log v(G) g 50K log n. Take F = (u, v) * H c which corresponds (as in Definition 4.7) to a pair of hyperedges C, C 2 of H from some bucket such that C has color c and w.l.o.g contains u and C 2 contains v. We need to verify that for 0 f j f 2 the number of F 2 * H c with |F 2 + F | = j is at most 50K log n(n/l) 22j , i.e., satisfies the condition in Proposition 4.9 (with k = 3 and t = 1). For j = 0, this number is the number of hyperedges in H c , which is at most 8n times the size of each bucket, that is, 8n • (³d/4) = 2³Knl log n f 2K log n(n/l) 2 . This is because each bucket has ³d/4 and so if it contains a hyperedge of color c then it produces ³d/4 pairs of hyperedges with one of color c. Each such pair then contributes 8 hyperedges to H c (see Figure 3). Furthermore, since the coloring of H is proper there are at most n buckets containing a hyperedge of color c.
For j = 1, note that the number of F 2 is at most 16 times the maximum degree of H plus 16 times the size of each bucket which is at most 16d + 16³d/4 f n/l. To see this note that we can get F 2 in two ways; one is by taking the unique hyperedge in H of color c through either u or v and combining it with any other hyperedge from the same bucket (giving a pair of hyperedges for Definition 4.7); the other is by considering any hyperedge of H containing either u or v and combining it with a hyperedge of color c in the same bucket (giving a pair of hyperedges in H for Definition 4.7); like before, in each case, each pair produces 8 hyperedges of H. Finally, for j = 2, note that F 2 * H c with F 2 = F can be obtained by taking a unique hyperedge C of color c through u (or v) and combining it with any hyperedge in the same bucket which contains v. This hyperedge must intersect the vertex of C 2 {u} which is incident to every other hyperedge in the bucket containing C and so, since the codegree of every pair of vertices is at most K log n this gives at most 2K log n options.
In this section, we prove Theorem 1.2 (ii). In this section, we will always consider odd uniformity k. The (log n) 1 k+1 factor improvement (as opposed to log n) follows from a new variant of the Kikuchi graph from Definition 4.6, which we describe next.
We now introduce the flower Kikuchi graph. Let H be an n-vertex k-uniform hypergraph with nd hyperedges and minimum degree • and such that every set of size k 2 1 is contained in at most one hyperedge. Suppose that the hyperedges of H are colored in red and blue. Suppose also that for each vertex v in H, we fix a collection E v of precisely • hyperedges containing v. Definition 6.1. A flower gadget F = (C, P 1 , . . . , P k ) in H is a collection of k + 1 hyperedges in H with a center hyperedge C = {v 1 , . . . , v k } and k petal hyperedges P 1 , . . . , P k which are disjoint and such that each P i is contained in E v i with P i + C = {v i }. F is a good flower gadget if C is blue and all hyperedges P i are red. See Figure 3 for an illustration. Definition 6.2. The flower l-Kikuchi graph G of H has vertex set V := [n] l and its edges are defined and colored as follows. For each good flower gadget F = (C, P 1 , . . . , P k ), define an edge between S, T * V , denoted by S C ± ³ T and colored with C
2 for all i. We first prove the following simple claim. Claim 6.3. An edge S µ T can possibly be created by at most 2 k 3 good flower gadgets.
Proof. To prove this, we only need to use the property that no set of size k 21 is contained in more than one hyperedge of the hypergraph H. Observe that for a good flower gadget {C, P 1 , . . . , P k } to create this edge, it must be that |(S \T )+A| = |(T \S)+A| = k21 2 for all A * {P 1 \{v 1 }, . . . , P k \{v k }}.
, there are at most k(k21)/2 (k21)/2 2k f 2 k 3 ways to define these sets (S \ T ) + A, (T \ S) + A, giving us the sets P 1 \ v 1 , . . . , P k \ v k . Since the hypergraph is such that no set of size k 2 1 is contained in more than one edge, through each of these sets there is a unique edge, giving us P 1 , . . . , P k (up to permutation of names which does not matter). Then the vertex set (P 1 * . . . * P k ) \ (S * T ) gives C.
Given the above claim, we fix the coloring arbitrarily by coloring S C ± ³ T with only one of the at most 2 k 3 possible options. We make note of some other crucial (but simple to check) properties of G just as we did previously in Section 4.4 with Observation 4.8. Observation 6.4. If G contains a closed walk and we denote by {C (j) , P (j) 1 , . . . , P (j) k } the good flower gadgets which create the edges of the walk, then j P (j)
In particular, if there is some (blue) edge which appears an odd number of times among the C (j) , then H contains an even cover whose size is of the same order as the length of the walk. Also, G has N := n l vertices and letting m denote the number of good flower gadgets in H, then G has average degree
.
Proof. We will briefly explain the average degree computation. Each good flower gadget creates at least n2k(k21) l2k(k21)/2 edges since after choosing the intersections S + (P i \ {v i }), T + (P i \ {v i }) we are left choosing S + T which can be any set of size l 2 k(k21) 2 from V (H) \ i (P i \ {v i }), which has size n 2 k(k 2 1). Further, as discussed above, each edge is possibly created by at most 2 k 3 good gadgets, and therefore, G
edges. The last estimate can be verified by considering separately cases when l f k 2 or l > k 2 and recalling that we can assume that l f n/ log n.
We will show an analog of Proposition 4.9, that if the flower l-Kikuchi graph has some 'nice' properties, then the underlying hypergraph contains a small even cover. Since we will not need the full power of such a statement, in the next section, we will only prove a simpler version of it which we use to establish Theorem 1.2 (ii).
Let H be a k-uniform n-vertex hypergraph with nd hyperedges where d g C (n/l) k/221 (log n) 1 k+1 for some sufficiently large constant C which depends on k. We take n large enough so that any fixed power of log n which appears in the proof is bigger than any constant dependent on k appearing. Note first that using Corollary 4.4 we can assume that H is such that every set of more than k21 2 vertices (since k is odd) has co-degree at most 1. Without loss of generality let us now assume that d = C (n/l) k/221 (log n)
2 . This gives us a sub-hypergraph H 0 with at least nd/2k hyperedges and a t f k21 2 with the given properties in the lemma. Let us split the remainder of the proof into the cases t > 1 and t = 1.
In this case, we know that H 0 has an (m(t), t)-bucket decomposition and deg H 0 (S) < m(|S|) for all sets S with |S| > t. We will show that this hypergraph satisfies the conditions of Proposition 4.9, which will immediately give an even cover as desired. Let then G be the l-Kikuchi graph for H 0 and let m := m(t). By Observation 4.8, it has average degree d(G) g e(H 0 )(m 2 1) (l/2n) k2t . Recalling that G has v(G) f 2n l f (2n) l vertices, we have that
Now, let us redefine H as H 0 . View H as an edge-colored hypergraph by coloring each hyperedge with a different color and let us verify the conditions of Proposition 4.9. For each hyperedge C * H, the hypergraph H C is then formed by taking every hyperedge C 2 in the same bucket as C and putting all hyperedges F in H C which satisfy one of the items in Definition 4.7 -in particular, part of F (either + k2t 2 + or + k2t 2 +) will be contained in either C (1) or C (2) and the rest will be contained in either C 2(1) or C 2 (2) . Depending on the parity of k 2 t, each such C 2 contributes to at least 2 k2t
2 and at most
Let us fix a hyperedge C in H, F * H C and 0 f j f k 2t. Let us denote the bucket of H containing C by (X i , E i ). We bound the number of F 2 * H C with |F 2 + F | = j as follows. Since F * H C , there is some hyperedge C 2 in the same bucket as C such that one of the items in Definition 4.7 applies. Let us assume without loss of generality that {| C(1) + F
2 }. Fix a pair j 1 , j 2 with j = j 1 + j 2 and let us consider those F 2 with j 1 = |F 2(1) + F (1)
We first fix for F 2 one of the items in Definition 4.7 which applies. Let us first count those with {| C(1)
} for some hyperedge C 22 in the same bucket as C and C 2 . First, we have at most 2 k options for the choice of F 2 (1) since it must be a subset of C (1) . For the choice of F 2 (2) , note that after choosing an appropriate hyperedge C 22 , we have again at most 2 k options for the choice of C22(2) + F 2 (2) . But now the choice of C 22 is restricted to the fact that X i * (F 2(2) + F (2) ) (which is here considered naturally as a set of vertices in [n] and not in [n] × [2]) must be contained in C 22 and thus, since |X i * (F 2(2) + F (2) )| = t + j 2 , the conditions of Lemma 4.5 imply that there are at most 2 k • max
k+1 choices for such an hyperedge C 22 , where the extra 2 k factor serves as a gross upper bound for the number of possible subsets X i * (F 2(2) + F (2) ) ¦ F . Combining all these consideration, we have at most
options for such F 2 . Notice that we used in the previous inequality that k/2 2 t 2
, since t g 2. Now, the arguments and the upper bound are analogous in the other cases for F 2 (that is, for all possible values of j 1 , j 2 and whether
}). Since there are at most 2k 2 such cases, by using (1) and choosing C large enough as a function of k, we conclude that the number of choices for F 2 is in total at most
as desired, where we used that log n f n/l. Hence, the property of Proposition 4.9 is satisfied and therefore H contains an even cover of size at most 2 log v(G) = O(l log n), as desired. Proof. We show that the number of flower gadgets in H is at least nd k+1 /(20k) k . Then, since each flower gadget is also good with probability 1/2 k+1 then the expected number of good flower gadgets is at least nd k+1 /(100k) k (using 5 k > 2 k+1 ) and further, with positive probability this holds. Now, let us count the number of flower gadgets {C, P 1 , . . . , P k }. We have e(H) g nd/2k options for the hyperedge C = {v 1 , . . . , v k }. Then, since P 1 * E v 1 and it is disjoint to C \ {v 1 }, there are |E v 1 |2|C|•m(2) > d/10k 2km(2) options for the edge P 1 . Subsequently, P 2 must be an edge belonging to E v 2 which is disjoint to (C*P 1 )\{v 2 } and therefore, we have at least |E • l n k(k21)/2 g nd k+1 100 k 3 • l n k(k21)/2 g C k+1 100 k 3 • l log n g C log N . Our aim is now to apply Lemma 2.5 to the graph G. Indeed, by Observation 6.4, a closed walk in G such that some color appears only once implies an even cover in H of the same order. However, it might be that the graph G does not satisfy the conditions of Lemma 2.5 and so, we need to first do a cleaning procedure similar to what was done in the proof of Proposition 4.9. Indeed, we delete all edges S C ± ³ T of G such that one of S or T are incident to another edge of color C. Let G 2 denote the resulting graph and note the following. we use v i to denote the vertex at which P i intersects C. We will show that the probability that S C ± ³ T is deleted is at most 1/2, which gives the desired outcome.
In order for S to be incident to another edge of color C, there must be i * [k] and a hyperedge P = P i in E v i such that |(P \ {v i }) + S| = k21 2 . For each such P , since the intersection S + (P i \ {v i }) = L i is already chosen, and further, the set S 2 := S \((P 1 \{v 1 })*. . . (P k \{v k })) is a uniformly random set of size l 2 k(k21) 2 in V (H) \ ((P 1 \ {v 1 }) * . . . (P k \ {v k })). Therefore, the probability that |(P \ {v i }) + S| = k21 2 is equal to the probability that the set S 2 intersects P \P i in k21 2 2|(P \{v i })+(P i \{v i })| = k21 2 2|P +P i |+1 vertices. Since S 2 is chosen uniformly, this probability is at most
where the 2 k is an upper bound for the number of intersections between S 2 and P \ P i . Now we count for each j g 1, the number of such P with |P + P i | = j. For j = 1, this is clearly at most |E v i | = d/10k = m(1) f (n/l) k/221 • (log n) 121/k 2 . Moreover, for j g 2, this is at most max |X|=j deg H (X) f m(j) f (n/l) k/22j • (log n) 121/k 2 . Further, by the assumption that no two hyperedges in H intersect in more than k/2 vertices, this number is 0 for j g k+1 2 . Hence, combining these observations, the probability of S having other C-colored incident edges is at most
where we used that l f n/(log n) 2 and that n is sufficiently large. Applying the same argument to T gives the desired outcome.
To finish, note that the edge-coloring in G 2 is now a proper edge-coloring and further, it has average degree at least 20 log N and thus, Lemma 2.5 implies that G contains a closed walk of size O(log N ) such that some color appears exactly once. By Observation 6.4, this implies an even cover in H of size O(l log n), as desired.