Sheaves on Graphs and a Proof of the Hanna Neumann Conjecture

Joel Friedman^{∗}

April 30, 2011

Abstract

The main goal of this paper is to prove the Hanna Neumann Conjecture; in fact, we prove a strengthened form of the conjecture. We study these conjectures using what we have called “sheaves on graphs” in [Fri]. We show that both conjectures are implied by the vanishing of a certain invariant, the “maximum excess,” of certain sheaves that we call ρ-kernels.

Our approach involves “graph Galois theory,” an analogue of classical Galois theory in the graph setting. We use it to construct the ρ-kernels. We use the symmetry in Galois theory to argue that if the Strengthened Hanna Neumann Conjecture is false, then the maximum excess of “most of” these ρ-kernels must be large. We then give an inductive argument to show that this is impossible.

1 Introduction

Howson, in [How54], showed that if K, L are nontrivial, finitely generated subgroups of a free group, F, then K ∩ L is finitely generated, and moreover that

rank(K ∩ L) − 1 ≤ 2 rank(K) rank(L) − rank(K) − rank(L).  (1)

∗Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, CANADA, and Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, CANADA. jf@cs.ubc.ca or jf@math.ubc.ca. Research supported in part by an NSERC grant. Research done in part at the Centre Bernoulli, funded by the Swiss National Science Foundation.

Hanna Neumann, in [Neu56, Neu57] improved this bound to what is now called the Hanna Neumann Bound,

rank(K ∩ L) − 1 ≤ 2 (rank(K) − 1) (rank(L) − 1);  (2)

furthermore, she conjectured that one can remove the factor of 2 in this bound, i.e., that

rank(K ∩ L) − 1 ≤ (rank(K) − 1) (rank(L) − 1);  (3)

this conjecture is now known as the Hanna Neumann Conjecture (or HNC). One goal of this paper is to prove the HNC. Moreover, we shall prove a strengthened form of the conjecture, first studied by Walter Neumann in [Neu90], known as the Strengthened Hanna Neumann Conjecture (or SHNC); we will state the strengthened conjecture in the next section.

Theorem 1.1 The Hanna Neumann Conjecture and the Strengthened Hanna Neumann Conjecture hold.

These conjectures have received considerable attention (see [Bur71, Imr77b, Imr77a, Ser83, Ger83, Sta83, Neu90, Tar92, Dic94, Tar96, Iva99, Arz00, DF01, Iva01, Kha02, MW02, JKM03, Neu07, Eve08, Min10]). However, our proof uses very different methods from the previous papers.

The main new idea in our approach to the SHNC is the notion of “sheaves on a graph,” introduced in [Fri], and their homology groups and related invariants. The SHNC has a well-known reformulation in terms of graph theory, and we will prove this reformulation by proving a stronger theorem about certain sheaves that we call ρ-kernels. We anticipate that the ideas in this paper and [Fri] will have applications to other areas in graph theory, for various reasons; for one thing, sheaves vastly generalize algebraic graph theory (e.g., adjacency matrices, incidence matrices, etc.); for another, sheaves can express new ideas not found in classical graph theory; in particular, sheaf theory sometimes gives “additional morphisms between graphs” that don’t exist in classical graph theory, and such morphisms are crucial to the construction of the ρ-kernels in this paper.

Our sheaf theory on graphs is based on the sheaf theory of Grothendieck (see [sga72a, sga72b, sga73, sga77]), built upon what are now known as Grothendieck topologies. More precisely, we work with sheaves of finite dimensional vector spaces on a finite Grothendieck topology, Top(G), that we associate to a graph, G. In [Fri05] we studied such sheaves over a large class of finite Grothendieck topologies, motivated by complexity theory. While graphs represent a very special case of such finite Grothendieck topologies, the results in [Fri] give stronger results for the special case of graphs, and study new invariants. The HNC and SHNC were our motivation for most of the results in [Fri].

Our proof also makes use of an analogue in graph theory of the classical Galois theory for number fields. This “graph Galois theory” was studied in [Fri93, ST96], with parts of it known earlier in [Gro77]. This theory is crucial in simplifying the SHNC to a problem concerning certain the sheaves we call ρ-kernels.

We use a graph theoretic reformulation of the SHNC that involves a graph theoretic invariant, ρ(G), of a graph, G, that we call its reduced cyclicity. In order to use sheaf theory to study the reduced cyclicity, ρ, one has to extend the definition of ρ to sheaves. A key idea in [Fri] is to realize that ρ is a certain limit of scaled first Betti numbers; this serves both to (1) define ρ on all sheaves, and (2) indicate that ρ should satisfy the same type of relations that all first Betti numbers do. What is remarkable is that this extension of ρ to sheaves, i.e., as a scaled limit, is equal to a what we call the “maximum excess” of a sheaf, that can be defined very simply and without any reference to homology theory. This simple definition makes the maximum excess look like quantities defined in matching theory or expanding graphs. Furthermore the maximum excess has other intriguing properties, such as it scales under pullbacks of covering maps, and it appears difficult to compute in general.

The graph theoretic reformulation of the SHNC amounts to an inequality between the reduced cyclicity of three graphs. We will formulate a stronger, simple conjecture about sheaves, roughly as follows. Relations between (co)homology groups of related spaces or sheaves are often described by (“long”) exact sequences. Recall that any time a vector space in an exact sequence vanishes, the vector space to its right injects into its right neighbour; so a zero Betti number (i.e., dimension of the vector space) in an exact sequence, implies the next two dimensions on the right are nondecreasing. So our idea is to fit the graphs in the SHNC into an appropriate short exact sequence, and deduce the desired inequality by showing that the appropriate homology group vanishes. The maximum excess is only a “limiting” homology group dimension, but, as a limit, it satisfies the same inequalities that Betti numbers do. Using graph Galois theory, we are almost immediately lead to a short exact sequence appropriate for this approach to the SHNC; the short exact sequence involves all the graphs involved in the SHNC, plus a sheaf we are forced to construct, which are the ρ-kernels. Hence the ρkernels, created by necessity in forming certain short exact sequences, are sheaves whose vanishing maximum excess implies the SHNC.

It turns out that some ρ-kernels have nonvanishing maximum excess. However, any graph, L, of interest to us in the SHNC, will have a family of associated ρ-kernels, and we will prove that the generic maximum excess in this family is zero, for each L. To do this we shall use Galois theory and symmetry to argue that if this generic maximum excess does not vanish then it is large, i.e., a multiple of the order of the associated Galois group. Then we will give an inductive argument, showing that if the generic maximum excess of ρ-kernels for L is positive, then the same is true when we remove some edge from L, provided that L has positive reduced cyclicity. The base case of the induction, when L has vanishing reduced cyclicity, is trivial to establish. Hence each L of interest in the SHNC has a ρ-kernel of vanishing maximum excess, and this establishes in SHNC.

We emphasize that our proof also uses the main theorem in [Fri], that shows that the “maximum excess,” which is crucial to this paper, is actually a limiting “twisted” Betti number, and therefore satisfies certain inequalities arising from the long exact sequence(s) associated to any short exact sequence. However, in this paper we use only some of these inequalities, and it is quite possible that one can prove the subset of inequalities we need for this paper more simply and directly, without going through the homological approach of [Fri]; we discuss this a bit further in the conclusion of this paper.

So the proof we give of the SHNC has no direct reference to homology theory or Betti numbers; for this paper, we need only a few simple definitions—a sheaf on a graph and its “Euler characteristic” and “maximum excess”—and then we quote some results from [Fri] whose statement requires no homology theory. However, the proof of these results in [Fri] uses a lot of homology theory, and homology theory does shed more light on the results of this paper. In the concluding section of this paper we will give some optional remarks on how homology theory can help our understanding of the maximum excess and of our proof of the SHNC.

This paper and [Fri] show that the SHNC is not merely an attempt to improve an inequality by a factor of two; our study of the SHNC has lead to new ideas in sheaves on graphs that can be applied to graph theory, some of which appear in [Fri]. This came as a surprise to us at first, although it is perhaps less surprising in retrospect, for a number of reasons. First, the HNC and SHNC seem to describe a fairly fundamental question in group theory (of how rank behaves under intersection). Second, the SHNC can be viewed as a graph theory question involving the reduced cyclicity, which is an interesting graph invariant (e.g. it scales under covering maps). Third, the SHNC, viewed in terms of the Galois theory of graphs (as in [Fri93]), has a simple homological explanation, as implied by the vanishing of a limit homology group. The vanishing of (co)homology groups has a vast literature and importance; the SHNC is an interesting and seemingly difficult result in the family of homology group vanishing theorems. Fourth, Lior Silberman has pointed out to us that the reduced cyclicity is the discrete analogue of L^{2} Betti numbers; the L^{2} Betti number was defined first by Atiyah ([Ati76]), and has been the subject of much surrounding the “Atiyah conjecture” (see [Lüc02]). Mineyev’s article, [Min10], also makes a connection between the SHNC and L^{2} Betti numbers.

At this point we can give more motivation for the use sheaf theory in this paper, i.e., why we do not just use graphs and their homology. Our reformulation of the SHNC begins by searching for a morphism involving the graphs of interest to the SHNC. In order for this morphism to exist, to be surjective, and to have a kernel, we must work with more general objects than graphs. In many topological situations, the topological spaces are sufficiently “robust” that one does not have to generalize the objects. However, in non-Hausdorff spaces, such as graphs or those in algebraic geometry, many geometric notions, such as “connect two points with a path,” “form a cone,” etc., don’t make sense or are very awkward to implement. So for graphs we use sheaf theory, which is a simple (co)homology theory that is adapted to our spaces, but general and expressive enough for appropriate surjections and kernels to exist.

The rest of this paper is organized as follows. In Section 2 we describe the SHNC and previous work on the HNC and SHNC, including some resolved special cases of the SHNC. In Section 3 we give a common graph theoretic reformulation of the SHNC. In Section 4 we give the definition of a sheaf and some of its associated invariants, and state some theorems from [Fri] that we will use in our proof of the SHNC. In Section 5 we describe applications of “graph Galois theory” to simplifying the SHNC in a way that leads to the construction of ρ-kernels. In Section 6 we construct ρ-kernels and prove that if their maximum excesses vanish then the SHNC holds; we also describe what we call “k-th power kernels,” which generalize ρ-kernels and which will be necessary to prove our main theorems about the generic maximum excess of ρ-kernels. In Section 7 we use symmetry to prove that the generic maximum excess of a certain type of k-th power kernel is divisible by the order of a group associated to the class of kernels. In Section 8 we prove some comparison theorems about how the maximum excesses of different classes of k-th power kernels compare; the main theorem that we prove shows that if ρ-kernels associated to a graph, L, have positive generic maximum excess, then the same is true of a graph L′ that consist of L with one edge discarded, provided that ρ(L′) = ρ(L) − 1. In Section 9 we briefly combine a number of theorems of previous sections to argue that if the SHNC does not hold, then for some L we have the class of ρ-kernels associated to L have positive generic maximum excess, which by the results of Section 8 means that the same is true for some L with ρ(L) = 0, which we easily show is impossible. This establishes the SHNC. In Section 10 we make some concluding remarks. In Appendix A we show that vanishing maximum excess of enough ρ-kernels implies the SHNC, but we do so just using elementary graph theory; this shows that a lot of the sheaf theory can be translated into direct graph theoretic terms; it also shows that a simple sheaf theoretic calculation may translate into a much longer graph theoretic calculation.

We wish to thank the following people: Laurant Bartholdi, for conversations and introducing us to this conjecture; Avner Friedman, for comments on a draft of this paper. We thank Luc Illusie, for an inspiring discussion regarding our ideas involving sheaf theory, homology, and the SHNC. We wish to thank for following people for conversations: Goulnara Arjantseva, Warren Dicks, Bernt Everitt, Sadok Kallel, Richard Kent, Igor Mineyev, Pierre Pansu, and Daniel Wise, Finally, we thank Alain Valette and the Centre Bernoulli at the EPFL for hosting us during a programme on limits of graphs, where we met Bartholdi and Pansu and began this work.

2 The Strengthened Hanna Neumann Conjecture

In this section we state the SHNC and comment on previous work, including some established special cases of the SHNC.

Walter Neumann, in [Neu90], showed that the Hanna Neumann Bound, i.e., equation (2), could be strengthened to

σ(K, L) ≤ 2 rk_{−1}(K) rk_{−1}(L),

where rk_{n}(G) denotes max(rank(G) + n, 0), and where

σ(K, L) = ∑_{KxF∈K\F/L} rk_{−1}(K ∩ x^{−1}Lx),

the summation being over the double coset, K\F/L, representatives, x; taking x be the identity in the summation shows that

rk_{−1}(K ∩ L) ≤ σ(K, L),

so that Walter Neumann’s above bound strengthens the Hanna Neumann Bound. Walter Neumann further formulated the conjecture that

σ(K, L) ≤ rk_{−1}(K) rk_{−1}(L),  (4)

now known as the Strengthened Hanna Neumann Conjecture (or SHNC).

The HNC and SHNC have been studied in many papers, including [Bur71, Imr77b, Imr77a, Ser83, Ger83, Sta83, Neu90, Tar92, Dic94, Tar96, Iva99, Arz00, DF01, Iva01, Kha02, MW02, JKM03, Neu07, Eve08, Min10]. For the rest of this section we review previous work on these conjectures.

One collection of results on the problem involves general bounds on σ(K, L) or rk_{1}(K ∩ L). It turns out that all general bounds we know for the HNC, i.e., on rk_{1}(K ∩ L), also are known to hold for σ(K, L). Also, all bounds we know are of the form

σ(K, L) ≤ 2 rank(K) rank(L) + c_{1} rank(K) + c_{2} rank(L) + c_{3}

for ranks K, L sufficiently large, where c_{1}, c_{2}, c_{3} are constants depending on the bound; thus all improvements of Howson’s original bound are in the lower order terms, i.e., in the c_{i}’s. The improved bounds on σ(K, L) after [How54, Neu56, Neu57] include the bound

2 rk_{−1}(K) rk_{−1}(L) − min(rk_{−1}(K), rk_{−1}(L))

of Burns in [Bur71]^{1}, the bound

rk_{−1}(K) rk_{−1}(L) + max(rk_{−2}(K) rk_{−2}(L) − 1, 0)

1Bounds appearing before [Neu90] are stated as bounds on rk_{−1}(K ∩ L), but actually give bounds on σ(K, L) as well.

of Tardos [Tar92, Tar96], and, what is the best bound prior to ours,

rk_{−1}(K) rk_{−1}(L) + rk_{−3}(K) rk_{−3}(L)  (5)

of Dicks and Formanek in [DF01].

Another collection of results concerns special cases of the HNC and SHNC that are resolved. To be precise, say that the “HNC holds for (K, L)” if equation (3) holds, and say that K is universal for the HNC if for any L, the HNC holds for (K, L). Similarly for the SHNC and equation (4). Similar to before, all results we know that resolve special cases of the HNC also resolve those cases of the SHNC. Note that any finitely generated free group, F, is a subgroup of F_{2}, the free group on two generators, so we are free to assume that F = F_{2} in the HNC. Here are some results on special cases of the SHNC that are easy to describe in group theoretic terms:

1. K is universal for the SHNC if it is of rank at most three ([DF01]), in view of equation (5), with rank two settled earlier by Tardos ([Tar92]);

2. K is universal for the SHNC if it is positively generated (see [Kha02, MW02, Neu07]);

3. K is universal for the SHNC for “most” K (see [Neu90, JKM03]);

4. the SHNC holds either for (K, L) or for (K, L′) for any K, L that are subgroups of F_{2}, where L′ is obtained from L by the map taking each generator of F_{2} to its inverse (see [JKM03]).

The result of item (3) on “most” groups, of Walter Neumann ([Neu90]), and some additional results on the SHNC, such as Corollary 3.2 of [MW02], are easier to describe using a graph theoretic formulation of the SHNC that we give in the next section. It is also known that the SHNC is related to the coherence problem in one-relator groups ([Wis05]).

3 Graph Theoretic Formulation of the SHNC

The goal of this section is to describe an equivalent formulation of the HNC and SHNC in graph theoretic terms involving fibre products; this formulation is implicit in [How54], but more explicit in [Imr77b, Imr77a, Ger83, Sta83, Neu90] and other references in [Dic94]. There is another equivalent reformulation of the SHNC by Dicks in [Dic94], known as the “amalgamated graph conjecture,” which we do not discuss here.

We must allow directed graphs to have multiple edges and self-loops; so in this paper a directed graph (or digraph) consists of tuple G = (V_{G}, E_{G}, t_{G}, h_{G}), where V_{G} and E_{G} are sets—the vertex and edge sets—and t_{G}: E_{G} → V_{G} is the “tail” map and h_{G}: E_{G} → V_{G} the “head” map. Throughout this paper, unless otherwise indicated, a graph is assumed to be finite, i.e., the vertex and edge sets are finite.

Recall that a morphism of digraphs, ν: K → G, is a pair ν = (ν_{V} , ν_{E}) of maps ν_{V} : V_{K} → V_{G} and ν_{E}: E_{K} → E_{G} such that t_{G}ν_{E} = ν_{V} t_{K} and h_{G}ν_{E} = ν_{V} h_{K}. We can usually drop the subscripts from ν_{V} and ν_{E}, although for clarity we shall sometimes include them.

Recall that fibre products exist for directed graphs (see, for example, [Fri93], or [Sta83], where fibre products are called “pullbacks”) and the fibre product, K = G_{1} ×_{G} G_{2}, of morphisms ν_{1} : G_{1} → G and ν_{2} : G_{2} → G has

V_{K} = {(v_{1}, v_{2}) | v_{i} ∈ V_{G_{i}}, ν_{1}v_{1} = ν_{2}v_{2}},
E_{K} = {(e_{1}, e_{2}) | e_{i} ∈ E_{G_{i}}, ν_{1}e_{1} = ν_{2}e_{2}},
t_{K} = (t_{G_{1}}, t_{G_{2}}), and h_{K} = (h_{G_{1}}, h_{G_{2}}).

For i = 1, 2, respectively, there are natural digraph morphisms, π_{i}: G_{1} ×_{G} G_{2} → G_{i} called projection onto the first and second component, respectively, given by the set theoretic projections on V_{K} and E_{K}. We say that ν: K → G is a covering map (respectively, étale^{2}) if for each v ∈ V_{K}, ν gives a bijection (respectively, injection) of incoming edges of v (i.e., those edges whose head is v) to those of ν(v), and a bijection (respectively, injection) of outgoing edges of v to those of ν(v). We say that ν: K → G is of degree d or is d-to-1 if the number of preimages of any vertex or edge of G equals d; if so, we write [K: G] for the degree, d; if G is connected and ν is a covering map, then ν is d-to-1 for some d.

By a bicoloured digraph, or simply a bigraph, we mean a directed graph, G, such that each edge is coloured (or labelled) either “1” or “2.” It is also equivalent to giving a directed graph homomorphism ν: G → B_{2}, where B_{2} is the graph with one vertex and two self-loops, one coloured “1” and the other “2.” If, moreover, ν is étale, we call ν or (somewhat abusively) G an étale bigraph, which means that G is a bigraph such that no vertex has two incident edges, both incoming or both outgoing, of the same colour.

2Stallings, in [Sta83], uses the term “immersion.”

Given a digraph, G, we view G as an undirected graph (by forgetting the directions along the edges), and let h_{i}(G) denote the i-th Betti number of G, and χ(G) its Euler characteristic; hence h_{0}(G) is the number of connected components of G, h_{1}(G) is the minimum number of edges needed to be removed from G to leave it free of cycles, and

h_{0}(G) − h_{1}(G) = χ(G) = |V_{G}| − |E_{G}|.

Let conn(G) denote the connected components of G, and let

ρ(G) = ∑_{X∈conn(G)} max(0, h_{1}(X) − 1),  (6)

which we call the reduced cyclicity of G, and

ρ′(G) = max_{X∈conn(G)}(max(0, h_{1}(X) − 1)).

The HNC is equivalent to

ρ′(K ×_{B_{2}} L) ≤ ρ(K)ρ(L)  (7)

for all étale bigraphs K and L; the SHNC is equivalent to

ρ(K ×_{B_{2}} L) ≤ ρ(K)ρ(L)  (8)

for all étale bigraphs K and L (see [How54, Imr77b, Imr77a, Ger83, Sta83, Neu90, Dic94]). We shall work with this form of the SHNC. Again, we say the HNC or SHNC, respectively, holds for a pair of étale bigraphs, (K, L), if equation (7) or (8), respectively, holds; and again, we say that K is universal for the HNC or SHNC, respectively, if for any L the same conjecture holds for (K, L).

Let us briefly explain the connection between the group theoretic formulations of the HNC and SHNC and the graph theoretic formulations. Given generators, g_{1}, g_{2}, for the free group, F_{2}, for each subgroup K ⊂ F_{2}, there is a canonically associated étale bigraph, K; K is given by constructing the Schreier coset graph, Sch(F_{2}, K, {g_{1}, g_{2}}), and letting K be the “core” of Sch(F_{2}, K, {g_{1}, g_{2}}), i.e., its smallest subgraph containing all reduced loops based at the vertex K (see [MW02] or the references in the previous paragraph); Sch(F_{2}, K, {g_{1}, g_{2}}) with directed edges labelled either g_{1} or g_{2} is a (typically infinite degree) covering of B_{2}, and K, a finite subgraph of Sch(F_{2}, K, {g_{1}, g_{2}}), is therefore an étale bigraph. If K, L are subgroups of F_{2}, and K, L the corresponding étale bigraphs, then each component of K ×_{B_{2}} L corresponds to the graph associated to K ∩ x^{−1}Lx ranging over double coset representatives, x.

Theorem 1.1 will be proven by the following equivalent theorem.

Theorem 3.1 The Strengthened Hanna Neumann Conjecture holds. That is, if K → B_{2} and L → B_{2} are two étale bigraphs over B_{2}, then

ρ(K ×_{B_{2}} L) ≤ ρ(K)ρ(L).  (9)

Equation (9) is tight in that if either K or L is a covering of B_{2} (i.e., has all vertices of degree four), then the inequality is satisfied with equality.

4 Sheaves and Maximum Excess

In this section we will define sheaves, some invariants of sheaves, and then the inequalities from [Fri] that we need in this paper.

4.1 Sheaves

Definition 4.1 Let G = (V, E, t, h) = (V_{G}, E_{G}, t_{G}, h_{G}) be a directed graph, and 𝔽 a field. By a sheaf of finite dimensional 𝔽-vector spaces on G, or simply a sheaf on G, we mean the data, F, consisting of

1. a finite dimensional 𝔽-vector space, F(v), for each v ∈ V,

2. a finite dimensional 𝔽-vector space, F(e), for each e ∈ E,

3. a linear map, F(t, e): F(e) → F(te) for each e ∈ E,

4. a linear map, F(h, e): F(e) → F(he) for each e ∈ E,

The vector spaces F(P), ranging over all P ∈ V_{G} ⨿ E_{G} (⨿ denoting the disjoint union), are called the values of F. The morphisms F(t, e) and F(h, e) are called the restriction maps. If U is a finite dimensional vector space over 𝔽, the constant sheaf associated to U, denoted \underline{U}, is the sheaf whose values are U at each vertex and edge, and whose restriction maps are all the identity map. The constant sheaf \underline{𝔽} will be called the structure sheaf of G (with respect to the field, 𝔽), for reasons explained in [Fri].

The field, 𝔽, is arbitrary here; at some later times we may place restrictions on 𝔽, for example, that it be algebraically closed.

To a sheaf, F, on a graph, G, we set

F(E) = ⨁_{e∈E} F(e), F(V) = ⨁_{v∈V} F(v).

We associate a transformation

d_{h} = d_{h,F}: F(E) → F(V)

defined by taking F(e) (viewed as a component of F(E)) to F(he) (a component of F(V)) via the map F(h, e). Similarly we define d_{t}.

Define the Euler characteristic of F to be

χ(F) = dim(F(V)) − dim(F(E)).

For any sheaf, F, on a graph, G, and any morphism ϕ: K → G of directed graphs, we define a “pullback” sheaf ϕ^{∗}F on K via

(ϕ^{∗}F)(P) = F(ϕ(P)) for all P ∈ V_{K} ⨿ E_{K},

and for all e ∈ E_{K},

(ϕ^{∗}F)(h, e) = F(h, ϕ(e)), (ϕ^{∗}F)(t, e) = F(t, ϕ(e)).

If ϕ: K → G is an arbitrary map, and F a sheaf on K, there is a natural sheaf ϕ_{!}F on G defined as follows:

(ϕ_{!}F)(P) = ⨁_{Q∈ϕ^{−1}(P)} F(Q), ∀P ∈ V_{G} ⨿ E_{G},

with the restriction maps induced from those of F, i.e., (ϕ_{!}F)(h, e) is the sum of the maps taking, for e′ ∈ ϕ^{−1}(e), the F(e′) component of (ϕ_{!}F)(e) to the F(he′) component of (ϕ_{!}F)(he) via the map F(h, e′). The reader can now observe that

(ϕ_{!}F)(V_{G}) ≃ F(V_{K}), (ϕ_{!}F)(E_{G}) ≃ F(E_{K}),

that d_{ϕ_{!}F,t} is the same map as d_{F,t} modulo these isomorphisms, and that the same holds with h replacing t. It follows that F and ϕ_{!}F agree on any invariant defined solely in terms of d_{t} and d_{h}.

It turns out (see [Fri]) that ϕ_{!} is the left adjoint of ϕ^{∗}.

If ϕ: K → G is a morphism of digraphs, we will often write \underline{𝔽}_{K} for ϕ_{!}\underline{𝔽}, when confusion is unlikely to arise (which requires ϕ to be understood in context). If K′ → G is another morphism, then we have a natural isomorphism of sheaves over G,

\underline{𝔽}_{K} ⊗ \underline{𝔽}_{K′} ≃ \underline{𝔽}_{K×_{G}K′},  (10)

where K ×_{G} K′ → G is the fibre product of K → G and K′ → G. If L → G is an arbitrary digraph morphism, we have an equality of sheaves on K,

ϕ^{∗}\underline{𝔽}_{L} = \underline{𝔽}_{K×_{G}L}.

Finally, if G′ ⊂ G with j: G′ → G being the inclusion, then j_{!}\underline{𝔽} = \underline{𝔽}_{G′} is the sheaf whose values are 𝔽 on each edge and vertex of G′, and 0 elsewhere, and whose restriction maps with nonzero source and nonzero target, hence from 𝔽 to 𝔽, are the identity maps.

We now define morphisms of sheaves, which are fundamental to many aspects of sheaf theory, including studying sheaf invariants via exact sequences.

Definition 4.2 A morphism of sheaves α: F → G on G is a collection of linear maps α_{v}: F(v) → G(v) for each v ∈ V and α_{e}: F(e) → G(e) for each e ∈ E such that for each e ∈ E we have G(t, e)α_{e} = α_{te}F(t, e) and G(h, e)α_{e} = α_{he}F(h, e).

It is not hard to check that all Abelian operations on sheaves, e.g., taking kernels, taking direct sums, checking exactness, can be done “vertexwise and edgewise,” i.e., F_{1} → F_{2} → F_{3} is exact iff for all P ∈ V_{G} ⨿ E_{G}, we have F_{1}(P) → F_{2}(P) → F_{3}(P) is exact. This is actually well known, since our sheaves are presheaves of vector spaces on a category (see [Fri05] or Proposition I.3.1 of [sga72a]).

If G′ ⊂ G, then there is a natural inclusion of sheaves on G, \underline{𝔽}_{G′} → \underline{𝔽} (but not generally any nonzero morphism from \underline{𝔽} = \underline{𝔽}_{G} to \underline{𝔽}_{G′}).

If ϕ: K → G is a morphism of graphs, and α: F_{1} → F_{2} is a morphism of sheaves on K, then we have natural a natural morphism

ϕ_{!}α: ϕ_{!}F_{1} → ϕ_{!}F_{2},

that make ϕ_{!} a functor on the category of sheaves. Similarly for ϕ_{∗}, and for the pullback, ϕ^{∗} (which acts the other way, from sheaves and their morphisms on G to those on K).

4.2 Maximum Excess of a Sheaf

Let F be a sheaf on a graph, G. For any U ⊂ F(V) we define the head/tail neighbourhood of U, denoted Γ_{ht}(G, F, U), or simply Γ_{ht}(U), to be

Γ_{ht}(U) = ⨁_{e∈E_{G}}{w ∈ F(e) | d_{h}(w), d_{t}(w) ∈ U};

we define the excess of F at U to be

excess(F, U) = dim(Γ_{ht}(U)) − dim(U).

Furthermore we define the maximum excess of F to be

m.e.(F) = max_{U⊂F(V_{G})} excess(F, U).

In [Fri] it is shown that if U ⊂ F(V) attains the maximum excess, then U is compartmentalized, meaning that it is a direct sum over each v ∈ V_{G} of a subspace of F(v) (see [Fri]). In [Fri] it is also shown that the excess is a supermodular function, i.e., for any U_{1}, U_{2} ⊂ F(V) we have

excess(F, U_{1}) + excess(F, U_{2}) ≤ excess(F, U_{1} ∩ U_{2}) + excess(F, U_{1} + U_{2})

(this is easy to show). It follows that the maximizers of F, i.e., the subspaces U ⊂ F(V) on which the excess is maximized, is closed under intersection and addition. In particular, each sheaf F has a unique maximum (or maximal) maximizer (namely the sum of all the maximizers) and unique minimum (or minimal) maximizer (namely the intersection of all the maximizers).

It is not hard to see that

1. for the structure sheaf, \underline{𝔽}, we have

m.e.(\underline{𝔽}) = ρ(G);

2. for sheaves F_{1}, F_{2} we have

m.e.(F_{1} ⊕ F_{2}) = m.e.(F_{1}) + m.e.(F_{2});

and 3. if E is a sheaf that is edge supported, meaning that E(V) = 0, then

m.e.(E) = dim(E(E)) = −χ(E)

(and similarly the maximum excess a vertex supported sheaf, defined similarly, is zero);

the reader can either consult [Fri] or prove these from scratch.

Definition 4.3 A sequence of real numbers, x_{0}, …, x_{r} is a triangular sequence if for any i = 1, …, r − 1 we have

x_{i} ≤ x_{i−1} + x_{i+1}.

The following theorem is a consequence of the main theorem of [Fri].

Theorem 4.4 Let G be a digraph. Consider a “short exact sequence” of sheaves, i.e.,

0 → F_{1} → F_{2} → F_{3} → 0

(in which the kernel of each arrow is the image of the preceding arrow). Then the sequence

0, m.e.(F_{1}), m.e.(F_{2}), m.e.(F_{3}),
m.e.(F_{1}) + χ(F_{1}), m.e.(F_{2}) + χ(F_{2}), m.e.(F_{3}) + χ(F_{3}), 0

is a sequence of non-negative integers that is triangular.

We mention that m.e.(F)+χ(F) can be viewed as a generalization of the “number of acyclic components” of a graph; for example, for the sheaf \underline{𝔽} on G we have

m.e.(\underline{𝔽}) + χ(\underline{𝔽}) = ρ(G) + |V_{G}| − |E_{G}| = h_{0}^{acyclic}(G)

equals the number of “acyclic components” of G, i.e. the number of connected components of G that have no cycles, i.e., that are isolated vertices or trees. A similar remark holds for \underline{𝔽} replaced by \underline{𝔽}_{K} and G replaced by K, for any map K → G.

In [Fri], a number of interesting questions about the properties of the maximum excess, alluded to in the introduction, are discussed, such as trying to find an efficient algorithm to find the maximum excess of a sheaf (the algorithm given there is exponential in the “dimension” of a sheaf).

The last result of [Fri] we shall use (in the subsection there on “contagious vanishing theorems”) is the following observation:

Lemma 4.5 Let F be a sheaf on a digraph, G, of maximum excess zero, and let u: K → G be an étale morphism. Then F ⊗ \underline{𝔽}_{K} has maximum excess zero, where \underline{𝔽}_{K} denotes u_{!}\underline{𝔽}.

Let us mention an alternate interpretation of the maximum excess.

Theorem 4.6 For any sheaf, F, on a digraph, G, the maximum excess of F is the same as

max_{F′⊂F} −χ(F′),

i.e., the maximum value of minus the Euler characteristic over all subsheaves, F′, of F.

Proof Each compartmentalized U ⊂ F(V) along with Γ_{ht}(U) determines a subsheaf F′ whose Euler characteristic is minus the excess of U. Conversely, for any subsheaf F′ ⊂ F we have U = F′(V) satisfies

dim(F′) = dim(U), F′(E) ⊂ Γ_{ht}(H).

Hence the excess of U is at least minus the Euler characteristic of F′.

□

This theorem has a simple graph theoretic analogue, namely that

ρ(G) = max_{H⊂G} −χ(H).

One can easily prove this directly (with ρ(G) = −χ(H) when H consists of all cyclic connected components of G) or use Theorem 4.6.

5 Galois and Covering Theory in the SHNC

In this section we establish a number of important definitions and facts concerning graph coverings and Galois coverings.

There is a collection of facts about number fields that may be called Galois theory; this would include classical Galois theory, but also more recent statements such as if k′ is a Galois extension field of k, then

k′ ⊗_{k} k′ ≃ ⨁_{Aut(k′/k)} k′

(see [Del77], Section I.5.1). Such facts have analogues in graph theory, which one might call “graph Galois theory.” Such facts were described in [Fri93, ST96]; at least some of these some of these facts were known much earlier, in [Gro77]; since these facts are fairly simple and quite powerful, we presume they may occur elsewhere in the literature (perhaps only implicitly). Our main use of Galois theory in the SHNC is to reduce the its study to subgraphs of a Cayley graph. This will later lead us to sheaves we call ρ-kernels. Let us now give definitions and state the main theorems to be developed in this section.

Definition 5.1 By the Cayley bigraph on a group, G, with generators g_{1} and g_{2}, denoted G = Cayley(G; g_{1}, g_{2}), we mean the étale bigraph, G, where V_{G} = G and E_{G} = G × {1, 2} (as sets), such that for each g ∈ G and i = 1, 2, the edge (g, i) has colour i, tail g, and head g_{i}g.

We reduce the SHNC to the special case of subgraphs of a Cayley graph, as follows.

Theorem 5.2 To prove Theorem 3.1, the SHNC, it suffices verify the SHNC on all pairs, (L, L′), such that L, L′ are subgraphs of the same Cayley bigraph. In particular, to prove the SHNC it suffices to show that any subgraph of a Cayley bigraph is universal for the SHNC.

The following simplifications of the SHNC on subgraphs of Cayley graphs will help solidify the connection between the SHNC and ρ-kernels of the next section.

Theorem 5.3 Let L be a subgraph of a Cayley bigraph, G, on a group, G. Then

1. L is universal for the SHNC if for any étale L′ → G we have (L, L′) satisfies the SHNC (with L′ inheriting the edge colouring from G, i.e., from the composition L′ → G followed by G → B_{2});

2. for any étale L′ → G we have

L ×_{B_{2}} L′ ≃ (LG) ×_{G} L′,

where

LG = ∐_{g∈G} Lg.

Before giving Galois theory we quickly describe the remarkable reason for the strong connection between the SHNC and covering and Galois theory. Since its proof is so short, we give it here as well.

Theorem 5.4 For any covering map π: K → G of degree d, we have χ(K) = dχ(G) and ρ(K) = dρ(G).

Proof The claim on χ follows since d = |V_{K}|/|V_{G}| = |E_{K}|/|E_{G}|. To show the claim on ρ, it suffices to consider the case of G connected, the general case obtained by summing over connected components; but similarly it suffices to consider the case of K connected. In this case

ρ(G) = h_{1}(G) − 1 = −χ(G) = −dχ(K) = d(h_{1}(K) − 1) = dρ(K).

□

From this theorem it follows that if K̃ → K and L̃ → L are covering maps of étale bigraphs, then

ρ(K̃ ×_{B_{2}} L̃) − ρ(K̃)ρ(L̃) = [K̃: K] [L̃: L](ρ(K ×_{B_{2}} L) − ρ(K)ρ(L));

hence (K, L) satisfy the SHNC iff (K̃, L̃) do. This means that to study the SHNC, one can always pass to covers of the bigraphs of interest.

For the rest of this section we describe a number of aspects of what we call Galois graph theory and use it for prove Theorems 5.2 and 5.3.

5.1 Galois Theory of Graphs

We shall summarize some theorems of [Fri93]; the reader is referred to there and [ST96] for more discussion. In this article Galois group actions, when written multiplicatively (i.e., not viewed as functions or morphisms) will be written on the right, since our Cayley graphs are written with its generators acting on the left.

Let π: K → G be a covering map of digraphs. We write Aut(π), or somewhat abusively Aut(K/G) (when π is understood), for the automorphisms of K over G, i.e., the digraph automorphisms ν: K → K such that π = πν.

Now assume that K and G are connected. Then it is easy to see ([Fri93, ST96]) that for every v_{1}, v_{2} ∈ V_{K} there is at most one ν ∈ Aut(K/G) such that ν(v_{1}) = v_{2}; the same holds with edges instead of vertices. It follows that |Aut(K/G)| ≤ [K : G], with equality iff Aut(K/G) acts transitively on each vertex and edge fibre of π. In this case we say that π is Galois.

If π: K → G is a covering map but K is not connected, |Aut(K/G)| can be as large as [K: G] factorial (if K is a number of copies of G). So when K is not connected, we say that a covering map π: K → G is Galois provided that we additionally specify a subgroup, G, of Aut(K/G) that acts simply (i.e., a non-identity g ∈ G acts without fixed edges or vertices) and transitively on each of the vertex and edge fibres of π; we declare G to be the Galois group. Allowing for π: K → G to be Galois in this generalized sense, i.e. for K not necessarily connected, does not change any of the theorems below, although some care is required when K is not connected; for example, it does mean that certain π: K → G can be Galois on each component of G without being Galois in our sense (consider G = G_{1} ⨿ G_{2}, and K_{i} = π^{−1}(G_{i}), where G_{1}, G_{2}, K_{1}, K_{2} are connected and the [K_{i}: G_{i}] are relatively prime).

Theorem 5.5 (Normal Extension Theorem) If π: G → B is a covering map of digraphs, there is a covering map μ: K → G such that πμ is Galois.

In this situation we say that K is a normal extension of G (assuming the maps μ and π are understood). By convention, all graphs are finite in the paper unless otherwise specified. Generally speaking, we will not address infinite graphs in the context of Galois theory; however, if the π: G → B in this theorem is a morphism of finite degree, even if G and B are infinite digraphs, then the proof of the Normal Extension Theorem due to Gross is still valid.

Let us outline two proofs of the Normal Extension Theorem. The proof in [Fri93] uses the fact that G corresponds to a subgroup, S, of index n = |V_{G}| of the group π_{1}(B), the fundamental group of B (which is the free group on h_{1}(B) elements). The intersection of xSx^{−1} over a set of coset representatives of π_{1}(B)/S is a normal subgroup, N, of finite size (at worst n^{n}, since there are n cosets and each xSx^{−1} is of index n); π(B)/N then naturally corresponds to a Galois cover K → B of at most n^{n} vertices.

There is a very pretty proof of the Normal Extension Theorem discovered earlier by Jonathan Gross in [Gro77], giving a better bound on the number of vertices of K. For any positive integer k at most n = |V_{G}|, let Ω^{k}(G) be the subgraph of G ×_{B} G ×_{B} ⋯ ×_{B} G (multiplied k times) induced on the set of vertices of the form (v_{1}, …, v_{k}) where v_{i} ≠ v_{j} for all i, j with i ≠ j. Each Ω^{k}(G) admits a covering map to G by projecting onto any one of its components. But Ω^{n}(G), which has edge and vertex fibers of size n!, is Galois by the natural, transitive action of S_{n} (the symmetric group on n elements) on Ω^{n}(G). So Ω^{n}(G) is a Galois cover of degree at most n! over B.

Our next fact is an analogue of a standard and surprisingly useful fact in descent theory (as in [Del77]); it is also surprisingly useful for the SHNC, despite the fact that it is trivial.

Theorem 5.6 Let π: K → G be Galois. Then

K ×_{G} K = ∐_{σ∈Aut(K/G)} K_{σ}

where K_{σ} is the subgraph of K ×_{G} K given via

V_{K_{σ}} = {(v, vg) | v ∈ V_{K}, g ∈ Aut(K/G)},
E_{K_{σ}} = {(e, eg) | e ∈ E_{K}, g ∈ Aut(K/G)}.

Each K_{σ} is isomorphic to K.

(See [Fri93], and compare with the identical formula for fields in [Del77], Section I.5.1).

Corollary 5.7 In Theorem 5.6, let us further assume that we have morphisms K_{1} → K and K_{2} → K. Then

K_{1} ×_{G} K_{2} ≃ ∐_{σ∈Aut(K/G)} K_{1} ×_{K} (K_{2}σ).

Proof

K_{1} ×_{G} K_{2} ≃ (K_{1} ×_{K} K) ×_{G} (K ×_{K} K_{2}) ≃ K_{1} ×_{K} (K ×_{G} K) ×_{K} K_{2}

≃ ∐_{σ}(K_{1} ×_{K} K_{σ} ×_{K} K_{2}) ≃ ∐_{σ}(K_{1} ×_{K} (K_{2}σ)).

□

There are many extensions to this basic theory. We mention one interesting example.

Assume, for simplicity, that G is connected. If K → G is Galois and factors as K → K′ → G, then K → K′ is Galois, with Galois group being the subgroup of Aut(K/G) fixing any vertex or edge fiber of K → K′; hence Aut(K/K′) is a subgroup of Aut(K/G). Conversely, a subgroup of Aut(K/G) divides the vertices and edges of K into orbits, giving a graph K′ (whose vertices and edges are these orbits) and a factorization K → K′ → G. Furthermore, for an intermediate cover K → K′ → G, K → K′ is always Galois (since Aut(K/K′) has the right cardinality), and K′ → G is Galois iff the subgroup of Aut(K/G) fixing K → K′ fibers is a normal subgroup of Aut(K/G). See [ST96] for details.

If K → G is Galois and factors as K → K′ → G,

K ×_{G} K′ = ∐_{g∈Aut(K/G)/Aut(K/K′)} K_{g},  (11)

where

V_{K_{g}} = {(v, [v]g) | v ∈ V_{K}}, E_{K_{g}} = {(e, [e]g) | e ∈ E_{K}},

where [v], [e] respectively denote the images of v, e, respectively, in K′; each K_{g} is isomorphic to K. Special cases of this statement include the trivial case K′ = G and the case K′ = K stated earlier.

5.2 Base Change

There are a number of easy “stability under base change” results; these say that in a digram arising from arbitrary digraph morphisms L → B and M → B,

[figure: L ×_{B} M; M; L; B]

if L → B has a certain property, then so does L ×_{B} M → M. Just from the construction of the fibre product, we easily see that the following classes of morphisms are stable under base change: étale morphisms, covering morphism, and Galois morphisms (and many others that we won’t need, such as open inclusions, morphisms that are d–to–1 for some fixed d, etc.).

5.3 Etale Factorization

In this subsection we shall prove that any étale map factorizes as an open inclusion followed by a covering map. This will easily establish Theorem 5.2.

We define an open inclusion to be any inclusion H → G of a subgraph, H, in a graph, G. We say the inclusion is dense if V_{H} = V_{G}; this agrees with the topological notion, i.e., the closure of G in H is H, under the topological view of G in [Fri].

Lemma 5.8 Let π: G → B be an étale map. Then π factors as an open inclusion, ι: G → G′, followed by a covering map, π′: G′ → B. If the vertex fibres of π (i.e., π^{−1}(v) over all v ∈ V_{B}) are all of the same size, i.e., π_{V} : V_{G} → V_{B} is d-to-1 for some d, then we may assume ι is dense; if in addition G is connected, then we may assume G′ is connected.

A variant of the first sentence of this theorem is called Marshall Hall’s theorem in [Sta83]. Proof By adding isolated vertices to G we may assume π_{V} is d-to-1 for some d. Extend G to G′ and π to π′: G′ → B by completing each π^{−1}(e) to a perfect bipartite matching of the vertices over the tail of e and those over the head of e (for a self-loop we view these two sets of vertices as disjoint). Clearly π′: G′ → B is a covering map. If π_{V} was originally d-to-1 for some d, then G′ is obtained by adding only edges, so G is dense in G′; if furthermore G is connected, then the G′ obtained by adding only edges is, of course, still connected.

□

Here is an easy, but vital, observation.

Lemma 5.9 If S → B_{2} is a Galois map with Galois group, G, then S is isomorphic to a Cayley bigraph on the group G = Gal(S/B_{2}).

Proof Choose any v_{0} ∈ V_{S} to be the “origin.” The association g ↦ v_{0}g sets up an identification of G with V, by definition of a Galois covering map, since there is a unique vertex of B_{2} and hence a singe vertex fibre in S. Since S → B_{2} is a covering map, the vertex v_{0} is the tail of a unique colour 1 edge, e, whose head is v_{0}g_{1} for a unique g_{1} ∈ G. For any g we have eg has tail v_{0}g and head v_{0}g_{1}g. It follows that identifying V with G means that there is an edge (g, g_{1}g) (i.e., whose tail is g and head is g_{1}g) of colour 1 for each g ∈ G. Similarly for edges of colour 2, and this sets up an isomorphism between S and Cayley(G; g_{1}, g_{2}).

□

Proof of Theorem 5.2 Let G → B_{2} and K → B_{2} be étale maps. Let these étale maps factor as open inclusions followed by covering maps as G → G̃ → B and K → K̃ → B. Let S be a Galois cover of G̃×_{B} K̃. Consider G′ = G ×_{G} S, which admits a natural map to G (namely projection onto the first component), and similarly K′ = K ×_{K} S. We claim that G′ → G is a covering map; indeed, by stability under base change (see Subsection 5.2), since K̃ → B_{2} is a covering map, so is G̃ ×_{B} K̃ → G̃; since S → G̃ ×_{B} K̃ is a covering map, so is S → G̃; hence, by base change so is G′ → G. Similarly K′ → K is a covering map. According to Theorem 5.4 and the discussion below, the SHNC is satisfied at (G, K) iff it is satisfied at (G′, K′). But G′, K′ are subgraphs of S, and S is a Galois cover of B_{2}, and therefore a Cayley bigraph.

□

Although we shall not need it, we mention that the idea in this last proof can be extended from G → B_{2} and K → B_{2} to an arbitrary number of étale maps, L_{i} → B_{2}, and gives the following interesting fact.

Theorem 5.10 For any étale bigraphs L_{1}, …, L_{k}, there are covering maps L′_{i} → L_{i} and a Cayley bigraph, S, such that each L′_{i} is a subgraph of S that is dense (i.e., L′_{i} has the same vertex set as S).

5.4 The Proof of Theorem 5.3

We finish this section with the proof of Theorem 5.3.

Claim (1) of the theorem is a simple base change argument: if L is a subgraph of a Cayley bigraph, G, and L′ → B_{2} is any étale bigraph, let L′′ = L′ ×_{B_{2}} G. Then, by base change (see Subsection 5.2), L′′ → G is étale and L′′ → L′ is a covering map. Then (L, L′) satisfies the SHNC iff (L, L′′) does. Hence L is universal for the SHNC iff (L, L′′) satisfies the SHNC for all étale bigraphs, L′′, whose colouring map factor as L′′ → G → B_{2}.

Claim (2) is an immediate consequence of Corollary 5.7, with G, K, K_{1}, K_{2} respectively replaced by B_{2}, G, L, L′, noting that Aut(G/B_{2}) = G.

□

6 ρ-kernels

In this section we introduce a collection of sheaves that are central to our proof of the SHNC. They are called ρ-kernels. Before defining them, we motivate their construction by showing how their study is connected to the SHNC. First we need to set some notation on Cayley graphs.

6.1 Sheaves on Cayley graphs

Let G = Cayley(G; g_{1}, g_{2}) be a Cayley bigraph on a group, G. Recall that since our generators act on the left, e.g., the colour 1 edges are of the form (g, g_{1}g), the Galois group of G is G acting on the right. Now we define a right action of G on sheaves on G. We shall state this in slightly more general terms. This is completely straightforward and mildly tedious, but convenient in this section and vital to Section 7.

Definition 6.1 We say that a group, G, acts on a digraph, G, on the right, if associated to each g ∈ G is an isomorphism π_{g}, of G such that π_{g_{1}g_{2}} = π_{g_{2}}π_{g_{1}} for all g_{1}, g_{2} ∈ G. We will identify g with π_{g} if no confusion can arise. If L is a subgraph of G, we write Lg for the image of L under g (i.e., under π_{g}); similarly if P ∈ V_{G} ⨿ E_{G}, P g denotes the image of P under g.

Of course, if G is a Cayley bigraph on a group, G, then G acts on G on the right.

Theorem 6.2 Let a group, G, act on a digraph, G, on the right. Then each element of G acts naturally as a functor on sheaves, via the association g ↦ π_{g^{−1}}^{∗}, such that

1. G acts on the right, i.e., if we write Fg for π_{g^{−1}}^{∗}F for any sheaf, F, on G, then for any g_{1}, g_{2} ∈ G we have Fg_{1}g_{2} = (Fg_{1})g_{2}, and similarly with the sheaf F replaced by a morphism of sheaves;

2. for each sheaf, F, on G, any g ∈ G, and any P ∈ V_{G} ⨿ E_{G} we have

(Fg)(P) = F(P g^{−1});

and 3. for each subgraph L ⊂ G and field, 𝔽, we have

\underline{𝔽}_{L} g = \underline{𝔽}_{Lg}.

In Section 7 it will be important to use the fact that for each g ∈ G, π_{g^{−1}}^{∗} is a functor, i.e., it acts (compatibly) on morphisms of sheaves as well as on sheaves. Proof For item (1), we recall that for any u: G′ → G, u^{∗} is a functor on sheaves, and for composable morphisms of digraphs, u_{1}, u_{2}, we have (u_{1}u_{2})^{∗} = u_{2}^{∗}u_{1}^{∗}; hence, since G acts on the right, for any g_{1}, g_{2} ∈ G we have

π_{g_{1}^{−1}}^{∗}π_{g_{2}^{−1}}^{∗} = (π_{g_{2}^{−1}}π_{g_{1}^{−1}})^{∗} = (π_{g_{1}^{−1}g_{2}^{−1}})^{∗} = π_{(g_{2}g_{1})^{−1}}^{∗}

and so g ↦ π_{g^{−1}}^{∗} is defines an action on sheaves and morphisms of sheaves that acts on the right.

Item (2) follows immediately from the definition of the pullback. Item (3) follows since for all P ∈ V_{G} ⨿ E_{G} and L ⊂ G and g ∈ G we have

(\underline{𝔽}_{L} g)(P) = \underline{𝔽}_{L}(P g^{−1});

but P g^{−1} ∈ L iff P ∈ Lg, so

\underline{𝔽}_{Lg}(P) = \underline{𝔽}_{L}(P g^{−1}) = (\underline{𝔽}_{L} g)(P).

Hence \underline{𝔽}_{Lg} = \underline{𝔽}_{L} g.

□

Given a sheaf, F, on G we define

FG = ⨁_{g∈G} Fg.

In particular, for L ⊂ G, if we set

LG = ∐_{g∈G} Lg

(akin to the notation in Theorem 5.3) then

\underline{𝔽}_{L} G ≃ \underline{𝔽}_{LG}.

6.2 Kernels and the SHNC

The following theorem summarizes our approach to the SHNC.

Theorem 6.3 Let L be a subgraph of a Cayley bigraph, G. Assume there is an exact sequence

0 → K → \underline{𝔽}_{L}G → \underline{𝔽}^{ρ(L)} → 0  (12)

such that m.e.(K) = 0. Then L is universal for the SHNC.

Proof According to Theorem 5.3, it suffices to show that for each étale u: L′′ → G we have that (L, L′′) satisfies the SHNC. Tensoring equation (12) with 𝔽_{L′′} = u_{!}\underline{𝔽} gives

0 → K ⊗ \underline{𝔽}_{L′′} → \underline{𝔽}_{L}G ⊗ \underline{𝔽}_{L′′} → \underline{𝔽}_{L′′}^{ρ(L)} → 0.  (13)

Since m.e.(K) = 0 and u: L′′ → G is étale, we have

m.e.(K ⊗ \underline{𝔽}_{L′′}) = 0

(this, as we mentioned earlier, is an example of a “contagious vanishing theorem” proven in [Fri]). Since the maximum excess is a first quasi-Betti number, this and equation (13) implies that

m.e.(\underline{𝔽}_{L}G ⊗ \underline{𝔽}_{L′′}) ≤ m.e.(\underline{𝔽}_{L′′}^{ρ(L)}) = ρ(L)ρ(L′′).

But

\underline{𝔽}_{L}G ⊗ \underline{𝔽}_{L′′} ≃ \underline{𝔽}_{(LG)×_{G}L′′} ≃ \underline{𝔽}_{L×_{B_{2}}L′′}

(using equation (10) and Corollary 5.7), and so we have

ρ(L ×_{B_{2}} L′′) = m.e.(\underline{𝔽}_{L×_{B_{2}}L′′}) = m.e.(\underline{𝔽}_{L}G ⊗ \underline{𝔽}_{L′′}) ≤ ρ(L)ρ(L′′).
□

6.3 Definition and Existence of ρ-Kernels and k-th Power Kernels

We begin with some notation to describe the kernels we introduce here and study throughout the rest of this paper.

Let G be a Cayley bigraph on a group, G. For any integer k ≥ 0, let 𝔽^{k×G} be the set of k × |G| matrices with entries m_{ig} ∈ 𝔽 indexed over i = 1, …, k and g ∈ G. If M ∈ 𝔽^{k×G}, then we can view M as a map from 𝔽^{G} to 𝔽^{k}. Then M gives rise to a morphism of constant sheaves

\underline{M}: \underline{𝔽}^{G} → \underline{𝔽}^{k}.

For any L ⊂ G and g ∈ G, we have an inclusion \underline{𝔽}_{Lg} → \underline{𝔽}, which gives us an inclusion

\underline{𝔽}_{L}G → \underline{𝔽}G ≃ \underline{𝔽}^{G}.

Thus we get a monomorphism

ι_{LG}: \underline{𝔽}_{L}G → \underline{𝔽}^{G},

and, for any M ∈ 𝔽^{k×G}, a composite morphism

\underline{M}ι_{LG}: \underline{𝔽}_{L}G → \underline{𝔽}^{k}.

We shall often write ι instead of ι_{LG}, since the subscript LG can be inferred from the source (even if two different ι’s are involved).

Definition 6.4 Let L be a subgraph of a Cayley bigraph, G, on a group, G, and let 𝔽 be a field. For any integer k ≥ 0, we say that M ∈ 𝔽^{k×G} is L-surjective if the map, \underline{M}ι_{LG} is surjective. If so, we that its kernel, K = K_{M}(L, G, G), is a k-th power kernel for (L, G, G); if, in addition, k = ρ(L), we also say that K is a ρ-kernel for (L, G, G).

Note that when kernels are defined in category theory, i.e., for a category with a zero morphism, then a kernel is defined only up to (unique) isomorphism. However, for sheaves on a graph, we can define the kernel of a morphism F_{1} → F_{2} uniquely, as the subsheaf of F_{1} that is the kernel. Hence we will speak of the kernel of a morphism, or its kernel, for convenience; when we say “a kernel” we shall mean the category theory notion, i.e., any morphism K → F_{1} that is the equalizer of F_{1} → F_{2} and the zero morphism.

Note that we could also define k-th power kernels when \underline{M}ι_{LG} is not surjective, as the element of the derived category (see [GM03]) as a single shift of the mapping cone of \underline{M}ι_{LG}; we shall not pursue this here.

The important point to notice is that if k ≤ ρ(L), “most” matrices M ∈ 𝔽^{k×G} are L-surjective. We now demonstrate this, in a rather explicit fashion.

Definition 6.5 We say that M ∈ 𝔽^{k×G} is totally linearly independent (or just totally independent) if every subset G′ of G of size k we have {m^{g}}_{g∈G′} is linearly independent, where m^{g} denotes the column of M corresponding to g ∈ G.

Lemma 6.6 Let L be a subgraph of a Cayley bigraph, G, on a group G. Then the number of vertices of L and the number of edges of either colour in L are all at least ρ(L).

Proof Adding vertices and edges to a graph does not decrease its reduced cyclicity (i.e., its ρ). So if P is an edge of colour 2, let L′ be L union all vertices of G and all edges of colour 1. Then ρ(L′) ≥ ρ(L) and L′ has the same number of edges of colour 2 as L. But if we discard the edges of colour 2 from L′ we are left with a union of cycles, for which ρ = 0, and discarding one edge decreases ρ by at most one (given equation (6)). Hence the number of edges of colour 2 in L′ is at least ρ(L), and so the same is true of the number of colour 2 edges in L.

Similarly L must have at least ρ(L) edges of colour 1. Finally, since each vertex of L is the head of at most one edge of colour 1, the number of vertices is also at least ρ(L).

□

Now we wish to describe ρ-kernels, both as a kernel of a sheaf morphism and, alternatively, by explicitly giving their values and restrictions.

Definition 6.7 Fix a subgraph, L, of a Cayley bigraph, G, on a group, G. Fix an M ∈ 𝔽^{k×G} for an integer k ≥ 0. For a subset T ⊂ G, the T -free subspace of ker(M) we mean the set

Free_{T} = Free_{T} (M) = {a⃗ ∈ ker(M) | ∀g ∉ T, a_{g} = 0}.

A free subspace of ker(M) is a subspace that is T -free for some T ⊂ G. For P ∈ V_{G} ⨿ E_{G}, we set

G_{L}(P) = {g ∈ G | P ∈ Lg}.

In the above definition, if M ∈ 𝔽^{k×G} is totally independent, then for all T ⊂ G we have

dim(Free_{T}) = max(0, |T | − k).  (14)

Lemma 6.8 Let L be a subgraph of a Cayley bigraph, G, on a graph G. Let M ∈ 𝔽^{k×G} be totally independent, for some k ≤ ρ(L). Then

\underline{M}ι: \underline{𝔽}_{L}G → (\underline{𝔽}_{G})^{k}

is surjective. Furthermore, if K_{M} denotes its kernel, then for each P ∈ V_{G} ⨿ E_{G} we have

K_{M}(P) = Free_{G_{L}(P)}(M),

in the notation of Definition 6.7, and the restriction maps for K_{M} are the inclusions. In particular,

dim(K_{M}(P)) = n_{P} − ρ(L),

where n_{P} = |G_{L}(P)|. (We shall sometimes write K_{M} as K_{M}(L) or K_{M}(L, G, G) to emphasize K_{M}’s dependence upon L, G, and G.)

Proof For each g ∈ G we have \underline{𝔽}_{L}g = \underline{𝔽}_{Lg}. Hence for each P ∈ V_{G} ⨿ E_{G}, we have

(\underline{𝔽}_{L}g)(P) = (\underline{𝔽}_{Lg})(P) = \{ \begin{matrix}𝔽 & if P ∈ Lg \\ 0 & if P ∉ Lg \end{matrix}

Hence

(\underline{𝔽}_{L}G)(P) ≃ ⨁_{g∈G_{L}(P)} 𝔽,

and the image of \underline{M}ι in (𝔽_{G})^{k} at P is the span of the subcollection of the n_{P} columns of M corresponding to the elements of G_{L}(P) ⊂ G. Since G is a Cayley bigraph, n_{P} is either the number of vertices, edges of colour 1, or edges of colour 2 in L. By Lemma 6.6 we have n_{P} ≥ ρ(L), and hence this subcollection of n_{P} vectors in M spans 𝔽^{k}. Hence \underline{M}ι is surjective at P, and its kernel, Free_{G_{L}(P)}, is of dimension n_{P} − k. The restriction maps on \underline{𝔽}_{L}G are, component by component, those of the individual \underline{𝔽}_{L}g over all g ∈ G, and those are just inclusions; since K is a subsheaf of \underline{𝔽}_{L}G, we have that K inherits those restriction maps.

□

Note that it is easy to see, even with G = ℤ/3ℤ and L consisting of five edges, that there need not be any graph theoretic surjections LG → G^{ρ(L)}, where G^{ρ(L)} is ρ(L) disjoint copies of G; so in passing from the graphs LG and G^{ρ(L)} to the sheaves \underline{𝔽}_{L}G and 𝔽^{ρ(L)}, there exists a surjection of sheaves that does not arise from any surjection of graphs. So an added benefit of working with sheaves (aside from using them to form kernels useful in studying the SHNC) is that sheaves give “additional surjections” that don’t exist in graph theory.

7 Symmetry and Algebra of the Excess

In this section we make some general observations about the maximum excess of k-th power kernels. The main observation is that given (L, G, G) as usual, the maximum excess of K_{M}(L) for generic M ∈ 𝔽^{k×G} is divisible by |G|, where by “generic” we mean for M in some subset of 𝔽^{k×G} that contains a nonempty, Zariski open subset of 𝔽^{k×G}. Let us outline this argument.

First, in Subsection 7.1, we will show that for any M ∈ 𝔽^{k×G} and g ∈ G we have K_{M}(L)g ≃ K_{Mg}(L) where Mg is obtained by an appropriate action of g on the columns of M. This means that if F is the maximal (or minimal) excess maximizer for K_{M}(L), then Fg is isomorphic to the maximal (or, respectively, minimal) excess maximizer for K_{Mg}(L). It may be helpful, albeit somewhat fanciful, to understand this symmetry via two “observers” looking at the exact sequence

0 → K_{M} → \underline{𝔽}_{L}G ⟶^{\underline{M}ι} \underline{𝔽}^{k} → 0,

one who examines this at P ∈ V_{G} ⨿ E_{G}, and the other at P g, for g fixed and P varying; for example, \underline{𝔽}_{L}G “looks” the same to both observers, except that its summands appear permuted from one observer to the other.

In Subsection 7.2 we discuss the generic maximum excess of K_{M} = K_{M}(L) with L fixed and M ∈ 𝔽^{k×G} variable (and G, G, k fixed). The key to this discussion is considering what we call “dimension profiles,” which we now define.

Definition 7.1 By a dimension profile on a bigraph, G, we mean a function

n: V_{G} ⨿ E_{G} → ℤ_{≥0}.

For any such n, we set

χ(n) = ∑_{v∈V_{G}} n(v) − ∑_{e∈E_{G}} n(e); |n| = ∑_{P ∈V_{G}⨿E_{G}} n(P).

Any sheaf, F, on G determines a dimension profile, dim(F), as the function P ↦ dim(F(P)). For any dimension profile, n, of a Cayley bigraph, G, on a group, G, any subgraph, L ⊂ G, any field, 𝔽, and any k ≥ 0, let

M(n) = M(n, L, G, G, 𝔽, k)

be the set of M ∈ 𝔽^{k×G} for which K_{M} = K_{M}(L, G, G) exists (i.e., M is L-surjective) and has a subsheaf, F, with dim(F) = n.

We easily see that for all n, M(n) is a constructible subset of 𝔽^{k×G}. Let N be the set of n for which M(n) is generic, i.e., contains a Zariski open subset of 𝔽^{k×G}; since M(n) is constructible, it is equivalent to say that its Zariski closure is 𝔽^{k×G}. The generic (in M) value of the maximum excess of K_{M} is the largest value of −χ(n) among those n ∈ N; let N′ be the subset of n ∈ N which attain this largest −χ(n) value. Since G is finite, for any n ∈ N there is a generic set of M such that Mg ∈ M(n) for all g ∈ G. Hence, if n ∈ N′ is chosen with |n| at a maximum value (or minimum value), then by the uniqueness of the maximum (or minimum) maximizer of the excess, the symmetry K_{M}g ≃ K_{Mg} implies that n(P) = n(P g^{−1}) for all P ∈ V_{G} ⨿ E_{G} and g ∈ G. Hence the generic maximum excess of K_{M}, which equals −χ(n) for any n ∈ N′, is divisible by G.

We wish to remark that the generic maximum excess is not generally attained by all M ∈ 𝔽^{k×G}. For example, our approach to the SHNC is based on the fact that the generic maximum excess of a ρ-kernel is zero, i.e., for k = ρ(L) (see Theorem 9.3). However, if M is zero in one column, but totally independent in the others, then M will still be L-surjective provided that L has at least ρ(L) + 1 edges of each colour. (A simple example of such an L can be obtained by deleting one edge of each colour from Cayley(ℤ/mℤ; 1, 1) with m ≥ 2.) In such a situation, the fact that M has a column of zeros implies that K_{M} has 𝔽_{L}g as a subsheaf (more precisely, a direct summand) for some g ∈ G, and hence the maximum excess of K_{M} will be at least ρ(L). Hence any L that has at least ρ(L) + 1 edges of each colour, and for which ρ(L) > 0, has a ρ-kernel of positive maximum excess. Hence it is essential to study the maximum excess of K_{M} with some restrictions on M, i.e., requiring some special properties of M; in our case, these properties restrict M to some generic subset of 𝔽^{ρ(L)×G}.

7.1 Symmetry of k-th Power Kernels

The point of this subsection is to establish the following symmetry of k-th power kernels.

Theorem 7.2 Let L be a subgraph of a Cayley bigraph, G, on a group, G, and let 𝔽 be an arbitrary field. Let k be an arbitrary non-negative integer and M ∈ 𝔽^{k×G}. Let Mg be the matrix (described earlier) whose g′ column, for g′ ∈ G, is the g′g^{−1} column of M. Then M is L-surjective iff Mg is L-surjective, and if so then K_{M}(L)g ≃ K_{Mg}(L).

Proof We begin our discussion of symmetry with a somewhat pedantic, but important, point. If A is a category in which finite direct sums exists, such as an additive category, and {A_{s}}_{s∈S} is a family of objects in the category indexed upon a finite set, S, then their direct sum comes with projections

f_{r}: ⨁_{s∈S} A_{s} → A_{r}

for each r ∈ S. If π: S → S is a permutation, then we have a “component permuting map,” P = P (π), given by

P (π) (⨁_{s∈S} A_{s}) = ⨁_{s∈S} A_{π(s)},

The two direct sums in this last equation are isomorphic, but not equal (e.g., the direct sum on the right-hand-side has the projection f′_{r} whose target is A_{π(r)}, not to A_{r}, for each r ∈ G). We shall need to keep the seemingly unimportant operator P = P (π) in mind in order to make things precise for this subsection. If A_{•} is any direct sum indexed on G, then we easily see P (π_{2})(P (π_{1})A_{•}) = P (π_{2} ∘ π_{1})A_{•}.

Again, let 𝔽 be a field, k ≥ 0 an integer, L a subgraph of a Cayley bigraph, G, on a group, G, and M ∈ 𝔽^{k×G} that is L-surjective. We have an exact sequence.

0 ⟶ K ⟶ ⨁_{g′∈G} \underline{𝔽}_{L} g′ ⟶^{\underline{M}ι} \underline{𝔽}^{k} ⟶ 0.  (15)

For a g ∈ G, applying π_{g^{−1}}^{∗}, of Theorem 6.2, to this sequence gives an exact sequence:

0 ⟶ Kg ⟶ ⨁_{g′∈G} \underline{𝔽}_{L} g′g ⟶^{π_{g^{−1}}^{∗}(\underline{M}ι)} \underline{𝔽}^{k}g ⟶ 0.  (16)

We have \underline{𝔽}g = \underline{𝔽} since \underline{𝔽} is a constant sheaf (note the we mean that the two are equal, not merely isomorphic). Note that π_{g^{−1}}^{∗} acts on sheaves by renaming the vertices of G, so it acts on \underline{M}ι only by permuting sheaf inclusions \underline{𝔽}_{Lg′′} → \underline{𝔽} for various values of g′′; in other words,

π_{g^{−1}}^{∗}(\underline{M}ι_{\underline{𝔽}_{L}G}) = \underline{M}ι′,

where ι′ is ι with the source \underline{𝔽}_{L}Gg. Hence we may write equation (16) as

0 ⟶ Kg ⟶^{j} ⨁_{g′∈G} \underline{𝔽}_{L} g′g ⟶^{\underline{M}ι′} \underline{𝔽}^{k} ⟶ 0,  (17)

where j is an inclusion.

Also, we have

P (π_{g^{−1}}) ( ⨁_{g′∈G} \underline{𝔽}_{L} g′g) = ⨁_{g′∈G} \underline{𝔽}_{L} π_{g^{−1}}(g′)g = ⨁_{g′∈G} \underline{𝔽}_{L} g′ = \underline{𝔽}_{L}G.

Hence from equation (17) we get a sequence

0 ⟶ Kg ⟶^{j} ⨁_{g′∈G} \underline{𝔽}_{L} g′g ⟶^{P (π_{g^{−1}})} \underline{𝔽}_{L}G ⟶^{P (π_{g})} ⨁_{g′∈G} \underline{𝔽}_{L} g′g ⟶^{\underline{M}ι′} \underline{𝔽}^{k} ⟶ 0,

and hence an exact sequence (since P (π_{g}) and P (π_{g^{−1}}) are isomorphisms)

0 ⟶ Kg ⟶^{P (π_{g^{−1}})∘j} \underline{𝔽}_{L}G ⟶^{\underline{M}ι′P (π_{g})} \underline{𝔽}^{k} ⟶ 0,  (18)

with j being the inclusion in equation (17). But clearly

\underline{M}ι′P (π_{g}) = \underline{M}P (π_{g}) ι_{\underline{𝔽}_{L}G} = \underline{Mπ_{g}} ι_{\underline{𝔽}_{L}G},

where π_{g} is viewed as operating vectors in 𝔽^{G} sending α ∈ 𝔽^{G}, viewed as a function α: G → 𝔽 to π_{g}α given by

g′ ↦ α(π_{g}(g′)) = α(g′g).

Hence setting Mg = Mπ_{g}, we get a short exact sequence

0 ⟶ Kg ⟶ \underline{𝔽}_{L}G ⟶^{\underline{Mg} ι} \underline{𝔽}^{k} ⟶^{0} .  (19)

Hence K_{Mg}(L) is, up to isomorphism, just Kg.

To complete the proof of the theorem, it remains to find that permutation that brings the columns of M to those of Mg. If M = {m_{i,g′}} give M’s entries, then for any w ∈ 𝔽^{G}, the i-th component of (Mg)w = M(π_{g}w) is

(M(π_{g}w))_{i} = ∑_{g′∈G} m_{i,g′}(π_{g}w)_{g′} = ∑_{g′∈G} m_{i,g′}w_{g′g} = ∑_{g′′∈G} m_{i,g′′g^{−1}}w_{g′′}.

Hence the i, g′′ entry of Mg is m_{i,g′′g^{−1}}, so the g′′ column of Mg is the g′′g^{−1} of M.

□

We wish to make a few comments on equation (19) and how we derived it. First, kernels, in category theory, are defined only up to isomorphism; this is why we can “forget about” P (π_{g^{−1}})j in equation (18); it is only important to know that this arrow gives an exact sequence there and in equation (19).

Note that the two actions of g ∈ G in equation (19) are right G actions on the exact sequence. To see this, first note that

(Mg)g′ = (Mπ_{g})π_{g′} = Mπ_{gg′} = Mgg′.

Then note that if we take the procedure for going from equation (15) to equation (19) and then do the same procedure with g replaced by g′, then we easily see (paying close attention to the order of the P ’s, the π’s, and the ι’s) that we get the same equation as equation (15) with K replaced by Kgg′ and M replaced by Mgg′.

We wish to comment on something that seems a bit contradictory. The map g ↦ P (π_{g^{−1}}) is a left action, and so it may seem strange that our forgotten monomorphism P (π_{g^{−1}})j in equation (18) involves a left action. But note that if we apply g′ to equation (19) we get

0 ⟶ Kgg′ ⟶^{π_{g′^{−1}}^{∗}(P (π_{g^{−1}})∘j)} \underline{𝔽}_{L}Gg′ ⟶^{π_{g′^{−1}}^{∗}(\underline{M}ι′P (π_{g}))} \underline{𝔽}^{k} ⟶ 0,

and hence an exact sequence

0 ⟶ Kgg′ ⟶^{α} \underline{𝔽}_{L}G ⟶^{β} \underline{𝔽}^{k} ⟶ 0,

where

α = P (π_{g′}^{−1}) ∘ π_{g′^{−1}}^{∗}(P (π_{g^{−1}}) ∘ j) = P (π_{g′}^{−1})P (π_{g^{−1}})j′,
β = π_{g′^{−1}}^{∗}(\underline{M}ι′P (π_{g}))P (π_{g′}),

for an inclusion j′. Examining α we see that P (π_{g′}^{−1}) is applied to the left of P (π_{g^{−1}}), whose product equals P (π_{(gg′)}^{−1}), so that g′ appears to the right of g.

A similar remark applies for the column permuting rule taking M to Mg: g ↦ π_{g^{−1}} is a left action, not a right action. However, if f: G → T is any function from G to a set, T, then defining a function fg via (fg)(g′) = f(g′g^{−1}) defines a right action of G on functions from G to T; indeed, for f: G → T and g, g_{1}, g_{2} ∈ G we have

((fg_{1})g_{2}))(g) = (fg_{1})(gg_{2}^{−1}) = f(gg_{2}^{−1}g_{1}^{−1}) = f(g(g_{1}g_{2})^{−1}) = (f(g_{1}g_{2}))(g).

So the left action g ↦ π_{g^{−1}} turns into a right action when it acts on the argument of a function.

We finish this subsection with a corollary of Theorem 7.2 that is our sole application of the theorem.

Corollary 7.3 Let n be a dimension profile for Cayley bigraph, G, on a group, G. Let L be a subgraph of G, let 𝔽 be a field, and let k ≥ 0 be an integer. Then for any g ∈ G, we have

M(ng, L, G, G, k) = M(n, L, G, G, k)g,

where ng is given by

(ng)(P) = n(P g^{−1})

for all P ∈ V_{G} ⨿ E_{G}.

(We easily check that the action g → ng in this corollary is a right action, similar to the above discussion of the action on functions from G to a set, T.) Proof Let g ∈ G and M ∈ M(n). Then there exists an F ⊂ K_{M} such that dim(F) = n. Then we have Fg ⊂ K_{M}g and we have dim(Fg) = dim(F)g, since

dim((Fg)(P)) = dim(F(P g^{−1}))

for all P ∈ V_{G}⨿E_{G}. But we have an isomorphism ι_{g}: K_{M}g → K_{Mg} of sheaves on G; so on the one hand we have ι_{g}F ⊂ K_{Mg}, and on the other hand, since isomorphisms preserve the dimension profile, we have Mg ∈ M(n′) where

n′ = dim(ι_{g}Fg) = dim(Fg) = ng.

Hence M ∈ M(n) implies that Mg ∈ M(ng). Applying this observation to M replaced with Mg and g replaced with g^{−1} (or simply reversing the argument in this proof) shows the converse. Hence M(n)g = M(ng).

□

7.2 Generic Maximum Excess

If 𝔽 is a field and r ≥ 1 an integer, then by a generic subset of 𝔽^{r} we mean a subset that contains

{(x_{1}, …, x_{r}) ∈ 𝔽^{r} | p(x_{1}, …, x_{r}) ≠ 0}

for some nonzero polynomial, p. Algebraic geometry and generic subsets are most commonly discussed (at least on the most basic level) under the assumption that 𝔽 is algebraically closed. Under this situation, all generic sets are nonempty; this remains true if 𝔽 is infinite, or if the polynomial, p, above is fixed and 𝔽 is finite but sufficiently large.

In order to have a sensible definition of generic and to conform to the algebraic geometric literature, we will freely assume that 𝔽 is algebraically closed. However, the theorems we obtain in this section and the next will be valid for any infinite field or “sufficiently large” finite field, 𝔽, by applying these theorems to the algebraic closure of 𝔽, finding the associated polynomials, p, to the generic sets of interest, and determining how large 𝔽 needs to be so that the generic sets are nonempty. The reader may find it amusing to note that in all our discussion of generic sets and generic conditions, all that we ultimately care about is that certain of these generic sets are nonemtpy (e.g., that there is at least one ρ-kernel for (L, G, G) with vanishing maximum excess).

Let us review some notation in algebraic geometry; see [Har77], Chapter 1, Section 1. Let us assume that 𝔽 is algebraically closed. Let 𝔸^{N} = 𝔸^{N}(𝔽), where N is an integer or a set or a product thereof, denote affine N space over 𝔽, i.e., the set 𝔽^{N}, with its usual Zariski topology. (When we speak of topological notions on 𝔽^{N} we mean those of 𝔸^{N}(𝔽); in the literature 𝔸^{N}(𝔽) connotes 𝔽^{N} viewed as a topological space, or scheme, etc.) Recall that a locally closed set is the intersection of an open and closed set (i.e., a subset of 𝔸^{N} determined as the zeros of some polynomials and complement of the zeros of some other polynomials), and a constructible set on 𝔸^{N} amounts to a finite disjoint union of locally closed sets (see [Har77], Exercise II.3.18).

Lemma 7.4 Let 𝔽 be an algebraically closed field, k ≥ 0 an integer, and L a subgraph of a Cayley bigraph, G, on a group, G. For each n: V_{G}⨿E_{G} → ℤ_{≥0}, M(n) = M(n, L, G, G, k) is a constructible set.

Proof We introduce |n| |G| indeterminates as follows: for each P ∈ V_{P} ⨿E_{P}, and i = 1, …, n(P), let x_{P,i} be a vector of indeterminates indexed on G (there are |n| vector variables x_{P,i}, for a total of |n| |G| indeterminates). We note that M ∈ M(n) precisely when one can find a solution for M and x_{P,i} to the conditions

1. M is L-surjective; i.e., for each P ∈ V_{G} ⨿ E_{G}, 𝔽^{k} is spanned by the columns of M corresponding to the elements of G_{P} (L);

2. for all P and i we have that x_{P,i} has zero components outside of G_{L}(P);

3. for all P and i, Mx_{P,i} = 0;

4. for all P, x_{P,1}, …, x_{P,n_{P}} are linearly independent;

5. for all e ∈ E_{G} and all i we have that x_{e,i}, x_{te,1}, x_{te,2}, …, x_{te,n_{te}} are linearly dependent, and similarly with he replacing te.

The dependence or independence or spanning of vectors reduces to the vanishing or nonvanishing of determinants of the vectors’ coordinates. Hence all the above equations give us a collection of polynomials f_{i} ∈ 𝔽[M, x] (polynomials in the entries of M and the x_{P,i}’s) and f̃_{j} ∈ 𝔽[M, x] such that M ∈ M(n) iff for some x we have (M, x) ∈ C, where C is the set of (M, x) for which f_{i}(M, x) = 0 for all relevant i and f̃_{j}(M, x) ≠ 0 for all relevant j; hence C is constructible. But M ∈ M(n) iff (M, x) ∈ C for some x; hence M(n) is the image of C under the projection

𝔸^{k×G} × 𝔸^{|n|×G} → 𝔸^{k×G}.

But any projection from an affine space to another by omitting some of the coordinates has the property that it takes constructible sets to constructible sets (see Exercise II.3.19 of [Har77] or Theorem 3.16 of [Har92], noting that such a projection is both regular and of finite type). Hence M(n), the image of C, is constructible.

□

We recall that a generic subset, S, of some affine space, 𝔽^{T}, is a subset that contains a nonemtpy Zariski open subset of the space; if S is constructible, then S is generic iff its Zariski closure is the affine space.

Next we claim that M(n) is generic in 𝔽^{k×G} for at least one n, provided that k ≤ ρ(L), and that M(n) = ∅ for all but finitely many n. Indeed, for any totally independent M ∈ 𝔽^{k×G} we have that M is L-surjective (for (L, G, G, 𝔽, k)), and the zero sheaf, Z, has dim(Z) = 0. Hence the Zariski closure of M(0) is 𝔽^{k×G}. Furthermore, K_{M}(P), for any P ∈ V_{G} ⨿ E_{G}, is of dimension at most |G| − k; hence M(n) = ∅ unless |n(P)| ≤ |G| − k for all P ∈ V_{G} ⨿ E_{G}, and there are only finitely many such n.

Definition 7.5 Let L be a subgraph of a Cayley bigraph, G, on a group, G, and let 𝔽 be an algebraically closed field. Let k ≤ ρ(L) be a non-negative integer. We say that n: V_{G}⨿E_{G} → ℤ_{≥0} is generic for (L, G, G, 𝔽, k) if the Zariski closure of M(n) is 𝔸^{k×G}(𝔽). We define the generic maximum excess of (L, G, G, 𝔽, k) to be the largest value of −χ(n) for which n is generic. We define n to be a maximal profile (respectively, minimal profile) of (L, G, G, 𝔽, k) if n is generic, −χ(n) equals the generic maximum excess, and there is no n′ ≠ n which is generic with −χ(n′) = −χ(n) and n′(P) ≥ n(P) (respectively n′(P) ≤ n(P)) for all P ∈ V_{G} ⨿ E_{G}.

Theorem 7.6 Let L be a subgraph of a Cayley bigraph, G, on a group, G. Let 𝔽 be an algebraically closed field, and k ≤ ρ(L) an integer. There is a unique maximal profile and a unique minimal profile for (L, G, G, 𝔽, k). Furthermore, if n is either the maximal or minimal profile, and P ∈ V_{G} ⨿ E_{G}, then ng = n for all g ∈ G (in the notion of Corollary 7.3). In particular −χ(n) is divisible by |G|.

Actually, the proof below shows that the theorem is still true when k > ρ(L), provided that L has at least k edges of each colour, so that a totally independent M ∈ 𝔽^{k×G} is L-surjective. Proof Let n_{1}, n_{2} be two maximal profiles for (L, G, G, 𝔽, k). Let us show that n_{1} = n_{2}. Consider the subset, S, of 𝔽^{k×G}, M, such that M ∈ M(n_{i}) for i = 1, 2 and m.e.(K_{M}) = −χ(n_{1}) = −χ(n_{2}). Clearly

S = M(n_{1}) ∩ M(n_{2}) ∩ ⋂_{n s.t. −χ(n)>−χ(n_{1})} \overline{M(n)},

where \overline{M(n)} denotes the complement of M(n). But if −χ(n) > −χ(n_{1}) then, by assumption, n is not generic, and hence S is the intersection of a finite number of generic subsets of 𝔽^{k×G}; hence S is a generic subset of 𝔽^{k×G}, as well. But any element, M ∈ S, has subsheaves F_{1}, F_{2}, of K_{M} which obtain the maximum excess of K_{M} and with dim(F_{i}) = n_{i} for i = 1, 2. But then F = F_{1} + F_{2} also achieves the maximum excess and has deg(F) ≥ n_{i} for i = 1, 2. Hence

S ⊂ ⋃_{n s.t. −χ(n)=−χ(n_{1}), n≥N} M(n),

where N = max(n_{1}, n_{2}). Since the union on the right-hand-side is a finite union of constructible sets, the closure of one of these sets is 𝔽^{k×G}. Hence there is an n with −χ(n) = −χ(n_{1}) and n ≥ N = max(n_{1}, n_{2}) such that n is generic; but if n_{1} ≠ n_{2}, then n does not equal either of them and is at least as big as either, which contradicts the maximality of the n_{i}, i = 1, 2. Hence n_{1} = n_{2}, and the maximal profile is unique.

We argue similarly for the minimal profile, replacing F_{1}+F_{2} with F_{1}∩F_{2}. Let n be the maximal profile for (L, G, G, 𝔽, k) (now known to be unique).

Since M(n) is a generic subset of 𝔽^{k×G}, so is M(ng) = M(n)g for any g ∈ G. But then ng is also a maximal profile, since clearly χ(n) = χ(ng) and |n| = |ng|. Hence n = ng for all g ∈ G. The same is true of the minimal profile.

It follows that the maximal (or minimal) profile, n, is invariant under G, and hence has the same value on all the vertices, on all the edges of colour 1, and on all the edges of colour 2. Hence −χ(n) is divisible by |G| for the maximal (or minimal) profile, and hence the generic maximum excess of (L, G, G, 𝔽, k) is divisible by |G|.

□

8 Variability of k-th Power Kernels

The main goal of this section is to prove the following theorem.

Theorem 8.1 Let L be a subgraph of a Cayley bigraph, G, on a group G. Let 𝔽 be an algebraically closed field, and let k ≤ ρ(L) be a positive integer. Then the generic maximum excess of (L, G, G, 𝔽, k) is at most that of (L, G, G, 𝔽, k − 1), and we have equality iff both excesses are zero.

As a consequence we get the following theorem.

Theorem 8.2 Let L be a subgraph of a Cayley bigraph, G, on a group G. Let 𝔽 be an algebraically closed field, and let k ≤ ρ(L) be a positive integer. Let L′ be obtained from L by removing a single edge. Then the generic maximum excess of (L′, G, G, 𝔽, k − 1) is at least that of (L, G, G, 𝔽, k).

(As before, this theorem is also true if k > ρ(L), provided that L has at least k edges of each colour, so that a totally independent M ∈ 𝔽^{k×G} is L-surjective.)

A second goal of this section is to establish some general relations between kernels K = K_{M}(L) as M and L vary. We shall derive two interesting, short exact sequences. First we establish a short exact sequence

0 → K_{M}(L) → K_{M′}(L) → \underline{𝔽} → 0,  (20)

for any M ∈ 𝔽^{k×G} and M′ obtained from M by deleting the last row. Second we establish a short exact sequence

0 → K_{M′}(L′) → K_{M′}(L) → E → 0,  (21)

with L, L′ as in Theorem 8.2, M′ ∈ 𝔽^{(k−1)×G} such that K_{M′}(L′) exists (i.e., M′ is L′-surjective), and E a sheaf with E(V) = 0 and E(E) of dimension |G|.

Equation (21) will be used along with Theorem 7.6 to show that Theorem 8.1 implies Theorem 8.2.

Theorem 8.1 will not be proven with short exact sequences, but rather with a careful analysis of the unique minimal maximizer of the excess of K_{M}(L) and of that of K_{M′}(L). The sequence in equation (20) gives a relationship between K_{M}(L) and K_{M′}(L), but we don’t know how to directly use this to conclude anything interesting about the two sheaves, such as the result of Theorem 8.1.

At this point we will divide our discussion into subsections. In Subsection 8.1, we will discuss the exact sequences related to our proof. In Subsection 8.2 we give the main observation of how the maximum excess changes in passing to subsheaves, and give an intuitive reason why the generic maximum excess of K_{M′}(L), as above, should be strictly greater than that of K_{M}(L) provided that these numbers don’t both vanish. In Subsection 8.3 we mimic the notation of Section 7 to include a discussion of K_{M′}(L) as above and make our arguments precise, finishing the proof of Theorem 8.1; this will easily yield Theorem 8.2.

8.1 Variability as Exact Sequences

Let L be a subgraph of a Cayley bigraph, G, on a group, G. For any nonnegative integer, k ≤ ρ(L), we have that a generic M ∈ 𝔽^{k×G} gives rise to a short exact sequence

0 → K_{M}(L) → \underline{𝔽}_{L}G → \underline{𝔽}^{k} → 0.  (22)

First we considering the variance of this equation in M; in other words, fix an M ∈ 𝔽^{k×G} such that

\underline{M}ι: \underline{𝔽}_{L}G → \underline{𝔽}^{k}

is surjective. Then we have an exact sequence given in equation (22); if M′ ∈ 𝔽^{(k−1)×G} is M with its last row deleted, we have a similar exact sequence

0 → K_{M′}(L) → \underline{𝔽}_{L}G → \underline{𝔽}^{k−1} → 0.  (23)

Notice that this discussion and everything below will remain essentially the same if, more generally, M′ is taken to be M followed by any surjective map 𝔽^{k} → 𝔽^{k−1}. In any event, we get a digram:

[figure: 0; K_{M}(L); \underline{𝔽}_{L}G; \underline{M}ι; \underline{𝔽}^{k}; 0; 0; K_{M′}(L); \underline{𝔽}_{L}G; ≃; \underline{M′}ι; \underline{𝔽}^{k−1}; 0]

where the dotted arrow from K_{M′}(L) to K_{M}(L) is inferred from the solid arrows; furthermore, given that the solid horizontal arrows consist of an isomorphism and epimorphism, we infer that the dotted arrow is a monomorphism.

We then complete the diagram to obtain a diagram

0

0  0  \underline{𝔽}^{}

[figure: 0; K_{M}(L); \underline{𝔽}_{L}G; \underline{M}ι; \underline{𝔽}^{k}; 0]

[figure: 0; K_{M′}(L); \underline{𝔽}_{L}G; \underline{M′}ι; \underline{𝔽}^{k−1}; 0]

[figure: K_{M′}(L)/K_{M}(L); 0; 0]

0^{}

A simple diagram chase shows that the nonzero upper right sheaf, \underline{𝔽}, and the nonzero lower left sheaf, K_{M′}(L)/K_{M}(L), are isomorphic. Hence we obtain the short exact sequence in equation (20).

An analogous exact sequence can be obtained by varying L in equation (22). Let L′ ⊂ L be a subgraph of L. Fix an M ∈ 𝔽^{k×G} that induces a surjection \underline{𝔽}_{L′}G → \underline{𝔽}^{k}. Then we get a diagram:

[figure: 0; K_{M}(L′); \underline{𝔽}_{L′}G; \underline{𝔽}^{k}; 0; 0; K_{M}(L); \underline{𝔽}_{L}G; \underline{𝔽}^{k}; ≃; 0]

Since \underline{𝔽}_{L′}G → \underline{𝔽}_{L}G is an injection, and the last vertical arrow is an isomorphism, the inferred dotted arrow is an injection. We therefore add a bottom row to the diagram and infer from the 3 × 3 Lemma that

K_{M}(L)/K_{M}(L′) ≃ (\underline{𝔽}_{L}/\underline{𝔽}_{L′})G.

In particular, if L′ is obtained from L by removing m edges, then we infer equation (21) (with M here replaced by M′, and k implicit here replaced by k − 1), where E is a sheaf with E(V) = 0 and E(E) being of dimension m|G|.

8.2 Maximum Excess and Subsheaves

The goal of this section is to explain the main idea we will use to prove Theorem 8.1; the formal proof will be given in the subsection after this one.

The following theorem gives a number of ways of demonstrating whether or not a sheaf and one of its subsheaves have the same maximum excess.

Theorem 8.3 Let F′ ⊂ F be sheaves on a digraph, G. Let U ⊂ F(V) be the minimal maximizer of the excess of F, and let U′ ⊂ F′(V) be the minimal maximizer of the excess of F′. Then

m.e.(F′) ≤ m.e.(F),  (24)

with equality iff U = U′ and

Γ_{ht}(F, U′) = Γ_{ht}(F′, U′).

We already know equation (24) is true, since the maximum excess is a quasi-Betti number; the novelty of this theorem is that we have a simple condition to characterize when equality holds. Proof Since U′ ⊂ F(V) and

Γ_{ht}(F′, U′) ⊂ Γ_{ht}(F, U′),

we have that

m.e.(F′) = excess(F′, U′) ≤ excess(F, U′) ≤ m.e.(F);

hence equality holds in equation (24) iff

excess(F′, U′) = excess(F, U′) = m.e.(F).

The first equality holds iff

Γ_{ht}(F, U′) = Γ_{ht}(F′, U′).

The second equality holds iff U′ is also a maximizer for F. But since U is the minimal maximizer for F, this implies that U ⊂ U′; but this means that U ⊂ U′ ⊂ F′(V), so U is a maximizer for F′, and hence U′ ⊂ U (since U′ is the minimal maximizer for F′). Hence U = U′.

□

Theorem 8.3 gives us a number of ways to conclude that equation (24) holds with strict inequality in certain situations. For example, consider a subgraph, L, of a Cayley bigraph, G, on a group, G, and consider a value, k for which

m.e.(K_{M}(L)) > 0

for a generic M ∈ 𝔽^{k×G}. Let M′ be obtained from M by removing its bottom row, and consider the minimal maximizer, U = U(M′) ⊂ K_{M′}(L)(V) of the excess of K_{M′}(L). We have that K_{M} ⊂ K_{M′}, and hence

m.e.(K_{M}(L)) = m.e.(K_{M′}(L))

implies that U(M′), which is generically nonzero, lies entirely in K_{M}(L)(V). But if w ∈ K_{M′}(L)(V) is any nonzero vector supported on v ∈ V_{G}, then we may identify w with the corresponding element of K_{M′}(L)(v), and so

w ∈ (\underline{𝔽}_{L}G)(v) ≃ ⨁_{g∈G_{L}(v)} 𝔽_{g},

where 𝔽_{g} denotes a copy of 𝔽. In other words, w is given by its G components, which are (zero outside of G_{L}(v) and are) elements of 𝔽. Hence, if we add a generic extra row to M′ on the bottom, to form M, the row, m⃗ = (m_{g})_{g∈G} will (generically in m⃗) satisfy

∑_{g∈G} w_{g}m_{g} ≠ 0.  (25)

Hence w ∉ K_{M}(L)(V) generically, and therefore the minimal maximizers for K_{M}(L) and K_{M′}(L) will generically be different. Hence, by Theorem 8.3, we have

m.e.(K_{M′}(L)) ≥ 1 + m.e.(K_{M}(L))

for generic M (and M′ obtained from M by deleting its bottom row). This argument will establish Theorem 8.1; all we need to do is to make this rigourous.

8.3 Proof of Theorems 8.1 and 8.2

In this subsection we precisely state the idea in the last subsection as Theorem 8.5 and use it to prove Theorem 8.1. We then easily conclude Theorem 8.2.

Let 𝔽 be a field, G a group, and k ≥ 1 an integer. If M′ ∈ 𝔽^{(k−1)×G} and m⃗ ∈ 𝔽^{G}, we define merge(M′, m⃗) to be the element of 𝔽^{k×G} whose first k − 1 rows consist of M′ and whose k-th row consists of m⃗.

Definition 8.4 Let L be a subgraph of a Cayley bigraph, G, on a group, G. Let 𝔽 be an algebraically closed field. Let M′ ∈ 𝔽^{(k−1)×G} be a matrix, for some integer k ≥ 1, that is L-surjective and whose kernel, K_{M′}(L), has nonzero maximum excess. Define the redundancy of M′, denoted redund(M′), to be the subset of 𝔽^{G} consisting of m⃗ such that M = merge(M′, m⃗) is L-surjective, and such that

m.e.(K_{M′}(L)) = m.e.(K_{M}(L)).

Theorem 8.5 Let L be a subgraph of a Cayley bigraph, G, on a group, G. Let 𝔽 be an algebraically closed field and k a positive integer. Let M′ ∈ 𝔽^{(k−1)×G} be a matrix that is L-surjective, and whose kernel, K_{M′}(L), has nonzero maximum excess. Then the redundancy of M′ lies in a proper subspace of 𝔽^{G}.

Proof This follows the argument of the last subsection. If U is the minimal maximizer of K_{M′}(L), then U is nonzero because the maximum excess is nonzero. Hence there exists a w ∈ U supported at v ∈ V_{G} with w ≠ 0. So if merge(M′, m⃗) is L-surjective, we have w ∉ K_{M}(L) if equation (25) holds. Since w ≠ 0, equation (25) holds for all m⃗ outside of a proper subspace of 𝔽^{G}.

□

Proof of Theorem 8.1 If the generic maximum excesses were equal, then for a nonempty Zariski open subset, U, of 𝔽^{k×G}, we would have for all M ∈ U the maximum excess of K_{M}(L) is the same as that of K_{M′}(L), where M′ is obtained from M by discarding its bottom row. Since U is nonempty and Zariski open, we have a polynomial, p = p(M′, m⃗) such that

p(M′, m⃗) ≠ 0

implies that (M′, m⃗) ∈ U. Write

p(M′, m⃗) = ∑_{n∈ℤ_{≥0}^{G}} q_{n}(M′)m^{n},

and fix any n such that q_{n} ≠ 0. Then q_{n}(M′) ≠ 0 for all M′ ∈ U′ for a nonempty Zariski open subset, U′, of 𝔽^{(k−1)×G}. For any fixed M′ ∈ U′ we have p(M′, m⃗) is a nonzero polynomial in m⃗; hence for fixed M′ ∈ U′ we have that (M′, m⃗) ∈ U for a Zariski open subset of m⃗ in 𝔽^{G}.

On the other hand, assuming that the maximum excesses in Theorem 8.1 are not both zero, the generic maximum excess of (L, G, G, 𝔽, k−1) is positive. Hence K_{M′}(L) has positive maximum excess for all M′ in some nonempty, Zariski open subset, U′′, of 𝔽^{(k−1)×G}. But by Theorem 8.5, for any M′ ∈ U′′ we have that (M′, m⃗) ∉ U for m⃗ outside of a proper subspace of 𝔽^{G}. But U′ and U′′ must intersect (being two nonempty, Zariski open subsets of an irreducible variety), which gives a contradiction.

□

Proof of Theorem 8.2 Let the generic maximum excess of (L, G, G, 𝔽, k) be m_{k}, that of (L, G, G, 𝔽, k − 1) be m_{k−1}, and that of (L′, G, G, 𝔽, k − 1) be m′_{k−1}. Since k ≤ ρ(L) and hence k − 1 ≤ ρ(L′) (we can see ρ(L′) ≥ ρ(L) − 1 from equation (6)), we have that m_{k}, m_{k−1}, m′_{k−1} are all multiples of |G|. The theorem is immediate if m_{k} = 0, so we may assume m_{k} > 0. In this case Theorem 8.1 implies that m_{k−1} > m_{k}, and since these numbers are both multiples of |G|, we have

m_{k−1} ≥ m_{k} + |G|.  (26)

But the exact sequence in equation (21) shows that for any M′ ∈ 𝔽^{(k−1)×G} we have

m.e.(K_{M′}(L′)) ≥ m.e.(K_{M′}(L)) − |G|.  (27)

Let U, U′, respectively, are the subsets of M′ ∈ 𝔽^{(k−1)×G} at which K_{M′}(L), K_{M′}(L′), respectively, attain their generic value; hence U, U′ are generic, and therefore so is U ∩ U′. Then applying equation (27) to any M′ ∈ U ∩ U′ implies that

m′_{k−1} ≥ m_{k−1} − |G|.

Combining this with equation (26) gives m′_{k−1} ≥ m_{k}, which proves the theorem.

□

9 Proof of the SHNC

In this section we prove the SHNC. At this point we have all the tools we need, except for one small detail.

Lemma 9.1 Let L be an arbitrary étale bigraph with ρ(L) > 0. Then there exists an edge, e ∈ E_{L}, such that the graph, L′, obtained by removing e from L has ρ(L′) = ρ(L) − 1.

Proof For each F ∈ E_{L} let L_{F} denote the subgraph of L obtained by removing the edges in F from L. It is easy to see that for each e ∈ E_{L} we have that ρ(L_{{e}}) is either ρ(L) or ρ(L)−1; this can be seen from equation (6), since removing e from its connected component of L leaves h_{1} the same or reduces it by one; alternatively, we can see this from the exact sequence

0 → \underline{𝔽}_{L_{\{e\}}} → \underline{𝔽}_{L} → \underline{𝔽}_{L/L_{\{e\}}} → 0,

using the fact that L/L_{{e}} is (edge supported and) of maximum excess one. For any two subgraphs, L′, L′′, of L we have an exact sequence

0 → \underline{𝔽}_{L′∩L′′} → \underline{𝔽}_{L′} ⊕ \underline{𝔽}_{L′′} → \underline{𝔽}_{L′∪L′′} → 0.

Hence

ρ(L′ ∩ L′′) ≥ ρ(L′) + ρ(L′′) − ρ(L′ ∪ L′′).

Taking F′, F′′ to be disjoint subsets of E_{L}, we see that if ρ(L_{F′}) = ρ(L_{F′′}) = ρ(L), then setting L′ = L_{F′}, L′′ = L_{F′′} yields

ρ(L_{F′∪F′′}) ≥ ρ(L),

and so ρ(L_{F′∪F′′}) = ρ(L). Hence, if ρ(L_{F}) = ρ(L) for all F ⊂ E_{L} of size one, then by induction we can show this holds for F ⊂ E_{L} of any size, which is impossible (since removing all the edges of a graph leaves it with ρ = 0). Hence there is at least one e ∈ E_{L} for which ρ(L_{{e}}) = ρ(L) − 1.

□

Of course, one can give a purely graph theoretic proof of Lemma 9.1; we now sketch such a proof. From equation (6), it suffices to show that if L is connected with h_{1}(L) ≥ 2 then we can remove an edge from L and reduce h_{1} by one. We claim that it suffices to take any edge that remains after we repeatedly prune the leaves of L.

Definition 9.2 Let L be a subgraph of a Cayley bigraph, G on a group, G. Let 𝔽 be an algebraically closed field. Then by the generic maximum excess of the ρ-kernel of type (L, G, G, 𝔽) we mean the generic maximum excess of (L, G, G, 𝔽, ρ(L)).

Theorem 9.3 Let L be a subgraph of a Cayley bigraph, G on a group, G. Let 𝔽 be an algebraically closed field. Then the generic maximum excess of the ρ-kernel of type (L, G, G) is zero.

Proof Fix G and G and let us prove the theorem for all L by induction on ρ(L). The base case ρ(L) = 0 follows by definition, since the exact sequence

0 → K → \underline{𝔽}_{L}G → \underline{𝔽}^{0} → 0

implies

m.e.(K) ≤ m.e.(\underline{𝔽}_{L}G) = ∑_{g∈G} ρ(Lg) = 0

(since ρ(Lg) = ρ(L) = 0 for all g ∈ G). The inductive step of our induction on ρ(L) is immediate from Theorem 8.2 applied to any L′ obtained from L by removing a single edge so that ρ(L′) = ρ(L) − 1; the existence of such an L′ is given by Lemma 9.1.

□

Proof of Theorem 1.1, the SHNC By the graph theoretic reformulation of the SHNC, it suffices to show Theorem 3.1. By Theorem 5.2 it suffices to show that any subgraph, L, of a Cayley bigraph, G, on a group, G, is universal for the SHNC. But by Theorem 9.3, there exists a ρ-kernel, K = K_{M}(L) for (L, G, G, 𝔽) with vanishing maximum excess, for any algebraically closed 𝔽. Hence we apply Theorem 6.3 to conclude that L is universal for the SHNC.

□

10 Concluding Remarks

We finish this paper with a few concluding remarks.

In this paper we have made no explicit reference to homology theories. In [Fri] we have used the twisted homology to prove that the maximum excess is a first quasi-Betti number; hence the theorems in this paper ostensibly rely on homology theories. However, we think it quite possible that one may able to prove that the maximum excess is a first quasi-Betti number directly, or give a direct proof of the inequalities we made use of in this paper. For example, if F′ → F is a monomorphism, then since the maximum excess is a first quasi-Betti number we know that

m.e.(F′) ≤ m.e.(F).

But this inequality is clear from the subsheaf formulation of maximum excess in Theorem 4.6.

We remark that we first proved the SHNC using twisted homology theory, and then rewrote our proofs to use only maximum excess. In fact, twisted homology theory offers some additional intuition regarding the maximum excess. Twisted homology theory shows that (after pulling back appropriately, see [Fri]), the maximum excess can be interpreted as the dimension of a certain vector space of “twisted harmonic one-forms” of the sheaf. When this dimension is d > 0, one can impose d′ linear conditions on the twisted harmonic one-forms and still have a d − d′ dimensional space of one-forms. This is how we view the variance in L of K_{M′}(L), as in the exact sequence of equation (21): to take a space of one-forms on K_{M′}(L) and obtain a oneform in K_{M′}(L′), one has to impose |G| |E_{L}\E_{L′}| conditions on the one-forms, namely the conditions that they vanish on the edges in LG that do not lie in L′G. Of course, one has to pullback by an appropriate covering map to make this rigourous (see [Fri]), but all the edge counts and dimension counts scale appropriately under any covering.

The k-th power kernels in this paper are subsheaves of the constant sheaf \underline{𝔽}G ≃ \underline{𝔽}^{G}. We believe that subsheaves of constant sheaves satisfy some stronger properties than general sheaves, regarding their homological invariants and maximum excess. It would nice to study this further.

References

[Arz00] G. N. Arzhantseva. A property of subgroups of infinite index in a free group. Proc. Amer. Math. Soc., 128(11):3205–3210, 2000.

[Ati76] M. F. Atiyah. Elliptic operators, discrete groups and von Neumann algebras. In Colloque “Analyse et Topologie” en l’Honneur de Henri Cartan (Orsay, 1974), pages 43–72. Astérisque, No. 32– 33. Soc. Math. France, Paris, 1976.

[Bur71] Robert G. Burns. On the intersection of finitely generated subgroups of a free group. Math. Z., 119:121–130, 1971.

[Del77] P. Deligne. Cohomologie étale. Lecture Notes in Mathematics, Vol. 569. Springer-Verlag, Berlin, 1977. Séminaire de Géométrie Algébrique du Bois-Marie SGA 4\frac{1}{2}, Avec la collaboration de J. F. Boutot, A. Grothendieck, L. Illusie et J. L. Verdier.

[DF01] Warren Dicks and Edward Formanek. The rank three case of the Hanna Neumann conjecture. J. Group Theory, 4(2):113–151, 2001.

[Dic94] Warren Dicks. Equivalence of the strengthened Hanna Neumann conjecture and the amalgamated graph conjecture. Invent. Math., 117(3):373–389, 1994.

[Eve08] Brent Everitt. Graphs, free groups and the Hanna Neumann conjecture. J. Group Theory, 11(6):885–899, 2008.

[Fri] Joel Friedman. Sheaves on graphs and their homological invari-

ants. availble at http://arxiv.org/pdf/1104.2665v1 and at
http://www.math.ubc.ca/~jf.

[Fri93] Joel Friedman. Some geometric aspects of graphs and their eigenfunctions. Duke Math. J., 69(3):487–525, 1993.

[Fri05] Joel Friedman. Cohomology of grothendieck topologies and lower bounds in boolean complex-

ity.  2005.  http://www.math.ubc.ca/~jf, also
http://arxiv.org/abs/cs/0512008, to appear.

[Ger83] S. M. Gersten. Intersections of finitely generated subgroups of free groups and resolutions of graphs. Invent. Math., 71(3):567–591, 1983.

[GM03] Sergei I. Gelfand and Yuri I. Manin. Methods of homological algebra. Springer Monographs in Mathematics. Springer-Verlag, Berlin, second edition, 2003.

[Gro77] Jonathan L. Gross. Every connected regular graph of even degree is a Schreier coset graph. J. Combinatorial Theory Ser. B, 22(3):227– 232, 1977.

[Har77] Robin Hartshorne. Algebraic geometry. Springer-Verlag, New York, 1977. Graduate Texts in Mathematics, No. 52.

[Har92] Joe Harris. Algebraic geometry, volume 133 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1992. A first course.

[How54] A. G. Howson. On the intersection of finitely generated free groups. J. London Math. Soc., 29:428–434, 1954.

[Imr77a] Wilfried Imrich. On finitely generated subgroups of free groups. Arch. Math. (Basel), 28(1):21–24, 1977.

[Imr77b] Wilfried Imrich. Subgroup theorems and graphs. In Combinatorial mathematics, V (Proc. Fifth Austral. Conf., Roy. Melbourne Inst. Tech., Melbourne, 1976), pages 1–27. Lecture Notes in Math., Vol.

622. Springer, Berlin, 1977.

[Iva99] S. V. Ivanov. On the intersection of finitely generated subgroups in free products of groups. Internat. J. Algebra Comput., 9(5):521– 528, 1999.

[Iva01] S. V. Ivanov. Intersecting free subgroups in free products of groups. Internat. J. Algebra Comput., 11(3):281–290, 2001.

[JKM03] Toshiaki Jitsukawa, Bilal Khan, and Alexei G. Myasnikov. On the Hanna Neumann conjecture, 2003. Available as

http://arxiv.org/abs/math/0302009.

[Kha02] Bilal Khan. Positively generated subgroups of free groups and the Hanna Neumann conjecture. In Combinatorial and geometric group theory (New York, 2000/Hoboken, NJ, 2001), volume 296 of Contemp. Math., pages 155–170. Amer. Math. Soc., Providence, RI, 2002.

[Lüc02] Wolfgang Lück. L^{2}-invariants: theory and applications to geometry and K-theory, volume 44 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer-Verlag, Berlin, 2002.

[Min10] Igor Mineyev. The topology and analysis of the Hanna Neumann Conjecture. March 2010. Preprint. Available at

http://www.math.uiuc.edu/~mineyev/math/art/shnc.pdf.

[MW02] J. Meakin and P. Weil. Subgroups of free groups: a contribution to the Hanna Neumann conjecture. In Proceedings of the Conference on Geometric and Combinatorial Group Theory, Part I (Haifa, 2000), volume 94, pages 33–43, 2002.

[Neu56] Hanna Neumann. On the intersection of finitely generated free groups. Publ. Math. Debrecen, 4:186–189, 1956.

[Neu57] Hanna Neumann. On the intersection of finitely generated free groups. Addendum. Publ. Math. Debrecen, 5:128, 1957.

[Neu90] Walter D. Neumann. On intersections of finitely generated subgroups of free groups. In Groups—Canberra 1989, volume 1456 of Lecture Notes in Math., pages 161–170. Springer, Berlin, 1990.

[Neu07] Walter D. Neumann. A short proof that positive generation implies the Hanna Neumann Conjecture, 2007. Available as

http://arxiv.org/abs/math/0702395, to appear.

[Ser83] Brigitte Servatius. A short proof of a theorem of Burns. Math. Z., 184(1):133–137, 1983.

[sga72a] Théorie des topos et cohomologie étale des schémas. Tome 1: Théorie des topos. Springer-Verlag, Berlin, 1972. Séminaire de Géométrie Algébrique du Bois-Marie 1963–1964 (SGA 4), Dirigé par M. Artin, A. Grothendieck, et J. L. Verdier. Avec la collaboration de N. Bourbaki, P. Deligne et B. Saint-Donat, Lecture Notes in Mathematics, Vol. 269.

[sga72b] Théorie des topos et cohomologie étale des schémas. Tome 2. Springer-Verlag, Berlin, 1972. Séminaire de Géométrie Algébrique du Bois-Marie 1963–1964 (SGA 4), Dirigé par M. Artin, A. Grothendieck et J. L. Verdier. Avec la collaboration de N. Bourbaki, P. Deligne et B. Saint-Donat, Lecture Notes in Mathematics, Vol. 270.

[sga73] Théorie des topos et cohomologie étale des schémas. Tome 3. Springer-Verlag, Berlin, 1973. Séminaire de Géométrie Algébrique du Bois-Marie 1963–1964 (SGA 4), Dirigé par M. Artin, A. Grothendieck et J. L. Verdier. Avec la collaboration de P. Deligne et B. Saint-Donat, Lecture Notes in Mathematics, Vol. 305.

[sga77] Cohomologie l-adique et fonctions L. Lecture Notes in Mathematics, Vol. 589. Springer-Verlag, Berlin, 1977. Séminaire de Géometrie Algébrique du Bois-Marie 1965–1966 (SGA 5), Edité par Luc Illusie.

[ST96] H. M. Stark and A. A. Terras. Zeta functions of finite graphs and coverings. Adv. Math., 121(1):124–165, 1996.

[Sta83] John R. Stallings. Topology of finite graphs. Invent. Math., 71(3):551–565, 1983.

[Tar92] Gábor Tardos. On the intersection of subgroups of a free group. Invent. Math., 108(1):29–36, 1992.

[Tar96] Gábor Tardos. Towards the Hanna Neumann conjecture using Dicks’ method. Invent. Math., 123(1):95–104, 1996.

[Wis05] Daniel T. Wise. The coherence of one-relator groups with torsion and the Hanna Neumann conjecture. Bull. London Math. Soc., 37(5):697–705, 2005.

A An Alternate View of ρ-kernels

In this section we give a direct proof that the vanishing generic maximum excess of ρ-kernels for all subgraphs, L, of any Cayley graph, G, implies the SHNC. We shall not use exact sequences. We shall require a few definitions, and some calculations to follow. While this gives some extra intuition about ρ-kernels, this section is not essential to the proof of the SHNC; we shall omit some of the easy but tedious graph theoretic details.

Definition A.1 Let L be a subgraph of a Cayley bigraph, G, on a group, G. As usual, for P ∈ V_{G} ⨿ E_{G}, let G_{L}(P) be the set of g ∈ G such that Lg contains P. By a vertex family on (L, G, G) we mean a function, U, from V_{G} to P(G), the power set (i.e., set of subsets) of G, such that for all v ∈ V_{G} we have U(v) ⊂ G_{L}(v). Similarly, an edge family on (L, G, G) is a function W: E_{G} → P(G) such that W(e) ⊂ G_{L}(e) for all e ∈ E_{G}. A vertex family, U, and edge family, W, are compatible if for all e ∈ E_{G} we have W(e) ⊂ U(te) ∩ U(he). Given a vertex family, U, the induced edge family, U_{E}, of U is the edge family U_{E} given by

U_{E}(e) = U(te) ∩ U(he) ∩ G_{L}(e).

The following lemmas motivate the above definitions; we omit their proofs, which are almost immediate.

Lemma A.2 To each vertex family, U on (L, G, G), and compatible edge family, W, on (L, G, G), there is a subgraph H ⊂ L ×_{B_{2}} G determined via

V_{H} = {(vg^{−1}, v) | g ∈ U(v)}, E_{H} = {(eg^{−1}, e) | g ∈ W(e)};

conversely, any subgraph H ⊂ L ×_{B_{2}} G arises from a unique vertex family, U, and compatible edge family, W.

Lemma A.3 For any vertex family, U, on (L, G, G) and compatible edge family, W, we have

W(e) ⊂ U_{E}(e).

In other words, U_{E} is the “largest” edge family compatible with U.

Definition A.4 Let L be a subgraph of a Cayley bigraph, G, on a group, G, let M ∈ 𝔽^{ρ(L)×G} be totally linearly independent, and let K = K_{M} be the resulting ρ-kernel. By a straight subspace of K(V) we mean a subspace

U = ∑_{v∈V_{G}} U(v) ∈ K(V),

such that for each v ∈ V_{G}, we have

U(v) = Free_{U(v)}  (28)

for some U(v) ⊂ G, with notation as in Definition 6.7.

Our goal for the rest of this section is to prove the following theorem.

Theorem A.5 Let L be a subgraph of a Cayley graph, G, on a group, G. The following conditions are equivalent:

1. for all L′ ⊂ G, the SHNC holds for (L, L′); 2. for every vertex family, U, on (L, G, G) we have

∑_{e∈E_{G}} |U_{E}(e)|_{ρ(L)} ≤ ∑_{v∈V_{G}} |U(v)|_{ρ(L)};

and

3. for some or any field, 𝔽, and some or any totally independent M ∈ 𝔽^{ρ(L)×G}, every straight subspace of K(V) with K = K_{M}(L) has excess zero.

We know by Theorem 5.2 that the SHNC holds iff it holds for all pairs (L, L′) that are subgraphs of a Cayley graph, G. Hence Theorem 9.3, that implies condition (3) of this theorem, implies the SHNC. Proof Conditions (2) and (3) are easily seen to be equivalent via equation (28) and equation (14).

If U is any vertex family on (L, G, G), let the positive set of U consist of those v ∈ V_{G} for which |U(v)| > ρ(L) and of those e ∈ E_{G} for which |U_{E}(e)| > ρ(L). We easily see that the positive set forms a subgraph, L′, of G, and that the pairs (P g^{−1}, P) such that P is in the positive set and g lies in U(P) or U_{E}(P) (as is appropriate), forms a subgraph, H, of L ×_{B_{2}} L′. We see that

−χ(H) = ∑_{e∈E_{L′}} |U_{E}(e)| − ∑_{v∈V_{L′}} |U(v)|

= ρ(L)χ(L′) + ∑_{e∈E_{L′}}(|U_{E}(e)| − ρ(L)) − ∑_{v∈V_{L′}}(|U(v)| − ρ(L))

= ρ(L)χ(L′) + ∑_{e∈E_{G}} |U_{E}(e)|_{ρ(L)} − ∑_{v∈V_{G}} |U(v)|_{ρ(L)}.

Hence we may write

−χ(H) − ρ(L)χ(L′) = ∑_{e∈E_{G}} |U_{E}(e)|_{ρ(L)} − ∑_{v∈V_{G}} |U(v)|_{ρ(L)}.  (29)

This equation is the main ingredient in the equivalence of conditions (1) and (3). Let us now state some graph theoretic lemmas that will firmly establish this equivalence.

Lemma A.6 For any digraphs H ⊂ G, we have

−χ(H) ≤ ρ(G);

and equality holds if H consists of all connected components, X, of G with h_{1}(X) > 0 and any of those with h_{1}(X) = 0.

Proof The statement about equality is clear from the definition of ρ in equation (6). The inequality can be established graph theoretically by induction on the number of vertices and edges in G that are not in H. Alternatively, see the end of Section 4.

□

Lemma A.7 Let U be a vertex family for (L, G, G), where L is a subgraph of a Cayley digraph, G, on a group, G. Assume that

∑_{e∈E_{G}} |U_{E}(e)|_{ρ(L)} − ∑_{v∈V_{G}} |U(v)|_{ρ(L)} > 0.  (30)

Then there is a vertex family, U′, which satisfies this inequality with U replaced by U′, for which the positive set of U′, L′, satisfies −χ(L′) = ρ(L′).

Proof For any subgraph, Y ⊂ G and vertex family W on (L, G, G), set

f(W, Y) = ∑_{e∈E_{Y}} |W_{E}(e)|_{ρ(L)} − ∑_{v∈V_{Y}} |W(v)|_{ρ(L)}.

Then clearly we have

f(U, L′) = ∑_{X∈conn(L′)} f(U, X),

where conn(L′) is the set of connected components of L′. But equation (30) says that f(U, G) > 0, and clearly f(U, L′) = f(U, G). Hence we have f(U, X) > 0 for some connected component, X, of L′; fix any such X.

We claim that ρ(X) = −χ(X). Since X is connected, this is true unless χ(X) = 1; so it suffices to show that χ(X) = 1 is impossible. If χ(X) = 1, then by repeatedly pruning the leaves of X, i.e., deleting a vertex of degree one and its incident edge from X, we arrive at an isolated vertex. But if Y is any subgraph of G with a vertex, v ∈ V_{Y}, of degree one, and incident edge e ∈ E_{Y}, and if Y′ is Y with v and e discarded, we claim that f(U, Y′) ≥ f(U, Y); indeed, U_{E}(e) ⊂ U(v), so

f(U, Y′) = f(U, Y) + |U(v)|_{ρ(L)} − |U(e)|_{ρ(L)} ≥ f(U, Y).

Hence, by repeatedly pruning X we are left with X′′ that is a single vertex with no edges, so f(U, X′′) ≥ f(U, X) > 0. But clearly f(U, X′′) ≤ 0 for X′′ consisting of a single vertex. Hence χ(X) = 1 is impossible, and so χ(X) ≤ 0 and hence ρ(X) = −χ(X).

For any vertex family, V of (L, G, G) and any subgraph Y ∈ G define a vertex family V|_{Y} via

V|_{Y} (v) = \{ \begin{matrix}V(v) & if v ∈ V_{Y}, \\ ∅ & otherwise. \end{matrix}

for all v ∈ V_{G}. We easily see that

V(e) ⊂ (V|_{L})_{E}(e)  (31)

for all e ∈ E_{L}. Hence

f(V|_{Y} , G) = f(V|_{Y} , Y) ≥ f(V, Y),

using equation (31). In particular, for V = U and Y = X we have

f(U|_{X}, G) ≥ f(U, X) > 0.

So we take U′ = U|_{X} and let L′ be its positive set. Then f(U′, L′) = f(U′, G) > 0, and L′ consists of X plus possibly some addition edges, so L′ is connected and χ(L′) ≤ χ(X) ≤ 0, so ρ(L′) = −χ(L′).

□

At this point condition (1) of Theorem A.5 easily implies condition (2). For if condition (2) does not hold, then for some U, and with L′ given as its positive set, we may assume ρ(L′) = −χ(L′) we have

∑_{e∈E_{G}} |U_{E}(e)|_{ρ(L)} − ∑_{v∈V_{G}} |U(v)|_{ρ(L)} > 0

and hence

ρ(L ×_{B_{2}} L′) ≥ −χ(H) > −ρ(L)χ(L′) = ρ(L)ρ(L′).

Hence the SHNC is false on a pair of subgraphs of G.

It remains to show that condition (2) of Theorem A.5 implies condition (1). Again, we need some graph theoretic considerations.

Lemma A.8 Assume the SHNC is false on a pair of subgraphs, (L, L′), of a Cayley bigraph G on a group G. Then there is a subgraph, L′′ ⊂ L′, such that

1. the SHNC is false on (L, L′′),

2. L′′ is connected,

3. −χ(L′′) = ρ(L′′), and

4. there is a subgraph, H ⊂ L ×_{B_{2}} L′′ such that −χ(H) = ρ(L ×_{B_{2}} L′′), and if U is the vertex family associated to H, then we have

f(U, G) > 0.

If condition (1) of Theorem A.5 is false, then the hypothesis of the above lemma holds; but item (4) of the lemma means that condition (2) of Theorem A.5 is false. Hence we conclude this section, and the proof of Theorem A.5 with the proof of the above lemma. Proof So assume the SHNC is false on a pair of subgraphs, (L, L′). Similar to before, the SHNC must therefore be false on (L, L′′), where L′′ is some connected component of L. Fix such a connected component, L′′.

We cannot have ρ(L′′) = 0, for otherwise ρ(L ×_{B_{2}} L′′) = 0 and the SHNC is not false on (L, L′′). Hence we have L′′ ⊂ L′ is connected and ρ(L′′) > 0, whereupon we have −χ(L′′) = ρ(L′′).

Now let L′′ ⊂ L′ be a minimal subgraph of L′ (with respect to inclusion of subgraphs) with the properties that L′′ is connected, ρ(L′′) > 0, and the SHNC is false on (L, L′′). We shall show that the lemma holds with this subgraph, L′′; we have already established the first three items in the conclusion.

Then take any H ⊂ L ×_{B_{2}} L′′ such that −χ(H) = ρ(L ×_{B_{2}} L′′). We now make a number of claims regarding L′′ that follow from the minimality of L′′.

First, we claim that L′′ has no leaves, i.e., no vertices of degree one. Otherwise, if v is a vertex of degree one, and e is its incident edge, then there are at least as many vertices in H over v as there are over v. So letting L′′′ be L′′ with v and e discarded, we see that ρ(L′′′) = ρ(L′′); but if H′ consists of the vertices and edges of H that do not lie over e or v, then H′ is a subgraph of H and ρ(H′) = ρ(H) (since we obtain H′ from H by discarding isolated vertices over v or vertices over v along with their single incident edges, lying over e). Hence the SHNC would fail also on (L, L′′′), contradicting the minimality of L′′.

Second, we claim that over each e ∈ E_{L′′} we there are at least ρ(L) + 1 edges in H; if not, we delete e from L′′, obtaining L′′′ ⊂ L′′, and delete the at most ρ(L) edges over e from H, obtaining H′ that lies over L′′′; this yields a strict subgraph, L′′′ of L′′ such that

ρ(L ×_{B_{2}} L′′′) ≥ −χ(H′) ≥ −χ(H) − ρ(L) = ρ(L ×_{B_{2}} L′′) − ρ(L)
> ρ(L)(ρ(L′′) − 1).

But since L′′ is pruned, we have ρ(L′′′) = ρ(L′′) − 1. So, once again, we have the SHNC fails on (L, L′′′) for some a proper subgraph, L′′′, of L′′; this contradicts the minimality of L′′.

Third, we claim that over each v ∈ V_{L′′} there are at least ρ(L)+1 vertices in H. Indeed, if v is incident upon some edge, e, in L′′, then e has at least ρ(L) + 1 vertices in H above it, so v does as well. If v is isolated in L′′, i.e., incident upon no edge, then L′′ consists of only v, since L′′ is connected; but this contradicts the fact that ρ(L′′) > 0.

To H is associated a vertex family, U, and an edge family, W. According to the three claims established in the previous three paragraphs, we have

v ∈ V_{L′′} ⟹ |U(v)| ≥ ρ(L) + 1, e ∈ E_{L′′} ⟹ |W(e)| ≥ ρ(L) + 1.

Clearly also

v ∉ V_{L′′} ⟹ U(v) = ∅, e ∉ E_{L′′} ⟹ W(e) = ∅.

It follows that, as before

f(U, G) ≥ ∑_{e∈E_{L′′}} |W(e)|_{ρ(L)} − ∑_{v∈V_{L′′}} |U(e)|_{ρ(L)}

= −χ(H) − ρ(L)(|E_{L′′}| − |V_{L′′}|) = ρ(L ×_{B_{2}} L′′) − ρ(L)ρ(L′′),

using the fact that L′′ is connected and ρ(L′′) > 0 (so that ρ(L′′) = |E_{L′′}| − |V_{L′′}|). Hence f(U, G) > 0, which shows item (4) in the conclusion of the lemma.

□
□