LINEAR ALGEBRA AND THE HANNA NEUMANN CONJECTURE

JOEL FRIEDMAN

Abstract. In this paper we give a short proof of the Hanna Neumann Conjecture (HNC) using only basic linear algebra, group theory, and algebraic geometry. We also give a number of exercises, partly to develop simpler material, and partly to give the reader more intuition for our new point of view. This article is currently a work in progress; we plan to keep adding more material, discussing more mathematics related to the HNC. All material is presented “from scratch,” assuming only a basic knowledge of linear algebra and group theory.

Introduction

In [Fri11a] we solved the Hanna Neumann Conjecture (or HNC) of the 1950’s using what we call “sheaf theory on graphs” developed in [Fri11b]. This article has two goals:

(1) we give a short proof of the HNC from scratch, using only basic linear algebra and group theory; this proof does not involve cohomology or many of the “heavy-handed” techniques of sheaf theory; and

(2) we describe additional aspects of mathematics, especially graph and group theory, related to the HNC, including showing how our approach to the HNC yields interesting examples of L^{2} Betti numbers.

This article assumes a background only in basic linear algebra and group theory.

This article is a work in progress. We will post a draft of the article as soon as we have a reasonable exposition of our first goal, a simple proof of the HNC. The second goal, regarding additional aspects of mathematics, is open ended at present, although we hope to eventually include:

(1) the simple sheaf theory of [Fri11b] that illustrates a number of points of more sophisticated sheaf and cohomology theories, such as étale cohomology;

(2) simple but interesting examples and calculations of L^{2} Betti numbers;

(3) a detailed exposition of Mineyev’s proof(s) of the HNC, of [Min11b, Min11a], based on combinatorics of infinite groups and, at first, L^{2} Betti numbers and von Neumann dimension, that appeared independently and almost simultaneously with our proof; and

(4) other topics(?).

Date: Thursday 28^{th} July, 2011, at 15:59(remove currenttime eventually).

2000 Mathematics Subject Classification. Primary 05C10, 55N30, 18F20; Secondary 05C50, 18F10, 14F20.

Research supported in part by an NSERC grant. Research done in part at the Banff International Research Station for Mathematical Innovation and Discovery.

We welcome feedback to jf@math.ubc.ca. This article grew out of notes for a lecture we gave our work at the “Groups, graphs and stochastic processes” workshop at BIRS^{1} in June 2011.

This article is written to give the main points, leaving easy calculations for the exercises. We have also included a number of additional exercises; even the mathematician familiar with the HNC, L^{2} Betti numbers, sheaf theory, etc., may benefit from these exercises, given how different our approach seems to be.

We remark that [Fri11b, Fri11a] have been combined into one longer article, [Fri11c], and that both [Fri11a, Fri11c] indicate how to construct the elementary proof of the HNC that we give. What is new here is the style of exposition and our somewhat more general discussion of the maximum excess. Note that we still use the same definition of sheaf here, but we do not use homology or pullbacks of sheaves in our simple proof.

This exposition has the following features:

• Easily proven statements, called “propositions,” are either very easy or have their proofs relagated to the exercise section; this makes the main exposition less cluttered and helps to emphasize the main points.

• Supplementary exercises are provided to help the reader’s intuition of the

material. This article is a work in progress, and it is unclear at which stage, if any, it will

be formally published (I am not posting this on arxiv.org, because of possible copyright issues).

As of July 28, 2011, I am posting this work on my web page. It contains a relatively short proof of the SHNC in three sections, and some additional material and exercises regarding these ideas. A fourth section is in progress.

I wish to thank Miklos Abert and Balint Virag who organized a BIRS workshop on “Groups, graphs and stochastic processes,” and numerous people for conversations there, including Miklos Abert, Balint Virag, and especially Igor Mineyev and Martin Kassabov.

1. Statement of the SHNC

The Hanna Neumann Conjecture (or HNC) was first stated in the 1950’s as a conjecture in group theory. It was eventually realized that this conjecture, and a strengthened conjecture, could be stated as an equivalent conjecture regarding finite directed graphs. In this section we introduce some basic concepts and notation in graph theory, and then state the graph theoretic form of the HNC and the Strengthened Hanna Neumann Conjecture (or SHNC). At the end of this section we shall describe the conjecture in its original group theoretic form.

1.1. Basic Graph Invariants. We will 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 digraph 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}.

1Banff International Research Station for Mathematical Innovation and Discovery

We can usually drop the subscripts from μ_{V} and μ_{E}, although for clarity we shall sometimes include them.

Definition 1.1. The fibre product of morphisms μ_{1} : G_{1} → G and μ_{2} : G_{2} → G is the graph, K = G_{1} ×_{G} G_{2}, given by

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}}).

This fibre product comes with natural digraph morphisms, π_{i}: G_{1} ×_{G} G_{2} → G_{i} called projection onto the first and second component, respectively, given by the respective set theoretic projections on V_{K} and E_{K}.

The fibre product gives rise to commutative diagram

(1.1)  \xymatrix{G_{1} ×_{G} G_{2} \ar[d]_{π_{1}} \ar[r]^{π_{2}} & G_{2} \ar[d]^{μ_{2}} \\ G_{1} \ar[r]^{μ_{1}} & G}

The fibre product is sometimes called the pullback in topology, and is the fibre product or pullback in the category theory sense; see [Fri93, Sta83] or Exercise 1.6.

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) with those of ν(v), and a bijection (respectively, injection) of outgoing edges of v and ν(v). If ν: K → G is a covering map and G is connected, then the degree of ν, denoted [K: G], is the number of preimages of a vertex or edge in G under ν (which does not depend on the vertex or edge); if G is not connected, one can still write [K: G] when π is of constant degree, i.e., the number of preimages of a vertex or edge in G is the same for all vertices and edges.

In (1.1), we say that π_{2} is obtained from μ_{1} via base extension of μ_{2}; for many classes, C, of morphisms (covering maps, étale maps, d-to-1 maps, sujections, inclusions, etc.), if μ_{1} ∈ C, then π_{2} ∈ C; see Exercise 1.5. We say that such a class of morphisms, C, is stable under base change.

Example 1.2. For integer d ≥ 1, let B_{d} be the directed graph with one vertex and d edges (which must be self-loops). Assume that the edges of B_{d} are labelled {1, …, d}. A digraph morphism G → B_{d} is equivalent to giving a digraph G and a colouring or labelling of the edges of G with the “colours” or labels {1, …, d}. The morphism G → B_{d} is étale (respectively, a covering map) iff each vertex, v ∈ V_{G}, has at most (respecitvely, exactly) one edge of each colour whose head is v, and the same with “tail” replacing “head.”

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}|.

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

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

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

which we call the reduced cyclicity of G. It is not hard to see that

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

(see Exercise 1.12). We also see that

h_{0}^{acyc}(G) = χ(G) + ρ(G)

is the number of connected components of G that are acyclic.

One can say that |V_{G}| and |E_{G}| are combinatorial invariants, in that they simply count the size of a set associated with G; if π: K → G is any d-to-1 digraph morphism, i.e., each vertex and edge has d preimages in K, then

|V_{K}| = |V_{G}| d, |E_{K}| = |E_{G}| d, χ(K) = χ(G) d.

Furthermore, if π is a d-to-1 (i.e., constant degree) covering map, then also ρ and h_{0}^{acyc} satisfy this multiplicative property, in that

ρ(K) = ρ(G) [K: G], h_{0}^{acyc}(K) = h_{0}^{acyc}(G)[K: G]

(see Exercise 1.7). By contrast, h_{0}, h_{1}, ρ, h_{0}^{acyc}, can be said to be topological invariants, in that they do not change under homotopy (see Exercise 1.8). The invariants ρ, h_{0}^{acyc}, and χ are therefore distinguished, in that they are both topological and multiplicative under covering morphisms. One simple fact that explains both these properties is that

(1.3)  ρ(G) = lim_{\{π: K→G\}} \frac{h_{1}(K)}{[K : G]}, h_{0}^{acyc}(G) = lim_{\{π: K→G\}} \frac{h_{0}(K)}{[K : G]},

where the limit is over covering maps as a directed set under refinement (see Exercise 1.14); this limit equation also indicates that h_{0}^{acyc}(G) and ρ(G) are the zeroth and first L^{2} Betti numbers of the universal cover of G (see Exercise 1.18).

1.2. Cayley Graphs and The Fibre Product. The fibre product seems difficult to understand in many situations. However, in this subsection we remark that certain fibre products involving Cayley graphs have a simple interpretation. This is part of what may be called “Galois graph theory” (see [Fri93, ST96, Fri11b, Fri11a, Fri11c]).

Definition 1.3. Given a group, G, and elements g_{1}, …, g_{d} ∈ G, we define the Cayley graph on group G with generators g_{1}, …, g_{d} to be the graph G = Cayley(G; g_{1}, …, g_{d}) whose vertices are V_{G} = G and whose edges are

E_{G} = G × {1, 2, …, d} = {(g, i) | g ∈ G, i = 1, …, d},

with

t_{G}((g, i)) = g, h_{G}((g, i)) = g_{i}g.

There is a natural left action of G on G; in other words, for each g′ ∈ G there is an automophism of G taking the edge (g, i) to (gg′, i), and the vertex g to gg′.

If B_{d} is the graph that is one vertex with d self-loops numbered {1, …, d}, we define a digraph morphism G → B_{d} taking an edge (g, i) to the i-th edge of B_{d}.

This is a covering morphism, in fact a Galois morphism (see Exercise 1.5(g)). It is easy to see that

G ×_{B_{d}} G ≃ ∐_{g∈G} G,

i.e., |G| disjoint copies of G (see Exercise 1.4). Moreover, if L_{1}, L_{2} are subgraphs of G then

L_{1} ×_{B_{d}} L_{2} ≃ ∐_{g∈G}(L_{1}g) ∩ L_{2},

where L_{1}g is the image of L_{1} the left action of g on G (see Exercise 1.4).

We note that historically one insisted in the above defininition of Cayley graph that g_{1}, …, g_{d} generate G so that the Cayley graph is connected; we do not insist on this. Furthermore we allow for g_{i} = g_{j} for i ≠ j, so that our Cayley graph may have multiple edges; similarly, we allow for some of the g_{i} to be the identity, so that our Cayley graph may have self-loops.

1.3. The (Strengthened) Hanna Neumann Conjecture. The Hanna Neumann Conjecture was stated around 1956 by Hanna Neumann as a conjecture in group theory; see [How54, Neu56, Neu57]. The conjecture was strengthened in 1990 by Walter Neumann; see [Neu90]. Both conjectures have received a lot of attention; see [Bur71, Imr77b, Imr77a, Ser83, Ger83, Sta83, Neu90, Tar92, Dic94, Tar96, Iva99, Arz00, DF01, Iva01, Kha02, MW02, JKM03, Neu07, Eve08, Min10]. These conjectures have equivalent conjectures in graph theory, which we now describe; the equivalence is proven in [Sta83], although some may argue (e.g., [DF01]) that the equivalence was known, perhaps implicitly, as early as Howson’s work.

Recall that B_{d} denotes the digraph with one vertex and d edges, and to give a graph, G, whose edges are labelled with d colours, is equivalent to giving a morphism G → B_{d}. Given such a G, by a coloured subgraph of G we mean a subgraph H ⊂ G that inherits G’s edge colouring, i.e., such that we label H’s edges via composing the inclusion H → G with the morphism G → B_{d}.

The SHNC is equivalent to the following conjecture.

Conjecture 1.4. For every étale morphisms of digraphs L_{1} → B_{2} and L_{2} → B_{2}, we have that

ρ(L_{1} ×_{B_{2}} L_{2}) ≤ ρ(L_{1})ρ(L_{2}).

The HNC is equivalent to this conjecture where ρ(L_{1} ×_{B_{2}} L_{2}) is replaced by ρ of any connected component of L_{1} ×_{B_{2}} L_{2}.

The first goal of this article is to prove this conjecture.

Once can reduce Conjecture 1.4 certain special cases. Here we state two of them.

Proposition 1.5. Assume that Conjecture 1.4 is false, i.e., that for some étale L_{1} → B_{2} and L_{2} → B_{2} we have

ρ(L_{1} ×_{B_{2}} L_{2}) > ρ(L_{1})ρ(L_{2}).

Then there exists a coloured subgraph L′_{2} ⊂ L_{2} such that

ρ(L_{1} ×_{B_{2}} L′_{2}) > ρ(L_{1})ρ(L′_{2}),

and, in addition, we have (1) L′_{2} is connected;

(2) L′_{2} has all vertices of degree two or more; (3) there is a subgraph, H, of L_{1} ×_{B_{2}} L′_{2} such that −χ(H) = ρ(L_{1} ×_{B_{2}} L′_{2}), and each edge and vertex of L′_{2} has at least ρ(L_{1}) + 1 preimages under the projection H → L′_{2} (this projection is, more precisely, the composition of the inclusion H → L_{1} ×_{B_{2}} L′_{2} followed by the projection onto the second component).

Proof. See Exercise 1.16. □

In this theorem, conditions (1) and (2) are well-known; condition (3) is easy, but will be important for our proof of the SHNC.

We state an interesting result that we shall not use here, which is another refinement of conditions (1) and (2) of Proposition 1.5.

Theorem 1.6 (Jitsukawa-Kahn-Myasnikov). Assume at Conjecture 1.4 is false, i.e., that for some étale L_{1} → B_{2} and L_{2} → B_{2} we have

ρ(L_{1} ×_{B_{2}} L_{2}) > ρ(L_{1})ρ(L_{2}).

Then there exists such an L_{1}, L_{2} with, in addition, the property that each vertex of either is of degree two or degree three, and all vertices of degree three have two incoming edges and one outgoing edge of colour 1.

Proof. See Exercise 1.17. □

The reader will our statement of the SHNC and the term “coloured subgraph” are implicit references to the category of “graphs over B_{2}” (see Exercise 1.19).

1.4. Exercises.

Exercise 1.1. Show that for any digraphs, G, H, we have G ×_{G} H is isomorphic to H.

Exercise 1.2. Show that any digraph admits a unique morphism to B_{1}. If G, H are two digraphs, show that the adjacency matrix of G ×_{B_{1}} H is the tensor product of those of G and H. The product G ×_{B_{1}} H is often called the “tensor product” of G and H.

Exercise 1.3. For i = 1, 2, let G_{i} be a cycle of length n_{i} ≥ 1, meaning a connected graph with n_{i} vertices and n_{i} edges, each vertex occurring as the head of one edge and the tail of one edge. Describe G_{1} ×_{B_{1}} G_{2} (see Exercise 1.2), in terms of the greatest common divisor of n_{1} and n_{2}. Consider, especially, the case n_{1} = n_{2}.

Exercise 1.4. Let G → B_{d} be a Cayley graph on a group, G. 1.4(a) Show that G ×_{B_{d}} G is isomorphic to |G| disjoint copies of itself. (This

generalizes Exercise 1.3.) 1.4(b) Show that, more generally, if L_{1}, L_{2} are subgraphs of G, that

L_{1} ×_{B_{d}} L_{2} ≃ ∐_{g∈G}(L_{1}g) ∩ L_{2}.

Exercise 1.5. Prove that the following classes of morphisms are stable under base change: 1.5(a) étale morphisms; 1.5(b) covering morphisms; 1.5(c) d-to-1 morphisms, for any integer d ≥ 1 (meaning the preimage of each

vertex and edge is of size d); 1.5(d) surjections; 1.5(e) injections; 1.5(f) morphisms that are d-to-1 on the edges; 1.5(g) morphisms that are Galois, meaning the data consisting of a morphism

π: K → G and a subgroup, G, of the automorphisms of π,

Aut(π) = {ν: K → K | πν = π, ν invertible}

such that G acts simply transitively on each vertex fibre and edge fibre of ν;

1.5(h) morphisms that are Abelian, meaning Galois with the distinguished subgroup of automorphisms being Abelian.

Exercise 1.6. Show that, in the situation of Definition 1.1, the fibre product G_{1} ×_{G} G_{2} (along with the morphisms π_{i} with target G_{i}, for i = 1, 2), is a fibre product or pullback in the category theoretic sense. That is, show that any digraph, K, and morphisms η_{i}: K → G_{i} for i = 1, 2 such that μ_{1}η_{2} = μ_{2}η_{1}, there is a unique morphism τ: K → G_{1} ×_{G} G_{2}.

[figure: K; η_{1}; η_{2}; τ; G; μ_{1}; μ_{2}; G_{1}; μ_{1}; G_{2}; μ_{2}; G]

In other words, G_{1} ×_{G} G_{2} (along with π_{1}, π_{2}) is a terminal object in the category of digraphs over the diagram with the objects G_{1}, G, G_{2} and the morphisms μ_{1}, μ_{2}.

Exercise 1.7. Show that if π: K → G is a covering map and G is connected, then ρ(K) = ρ(G)[K : G]. [Hint: show that it suffices to prove this when K is connected, so h_{1}(K) = h_{1}(G) = 1, and use the fact that χ(K) = χ(G)[K : G].] Conclude the same when G is not connected but π is of constant degree. Conclude the same about h_{0}^{acyc}, either from scratch or using that h_{0}^{acyc} = χ + ρ.

Exercise 1.8. Consider the following two operations on a digraph, G:

(1) vertex splitting: we discard a vertex, v, of G, replacing it by a new edge, e, and two new vertices, v_{1}, v_{2} that are the head and tail, respectively, of e; some G edges with head or tail at v now have this head or tail at v_{1}, the rest at v_{2};

(2) leaf adding: we add to G a vertex, v, of degree one and an edge, e, whose

head or tail is v, and whose other endpoint is a vertex of G. 1.8(a) Show that h_{0}, h_{1}, h_{0}^{acyc}, ρ are invariant if we change a graph by a vertex

splitting or adding a leaf. 1.8(b) Consider the operation of edge subdivision, where we replace an edge in G

by a new path of finite length (where the edges along the path have arbitrary orientation). Show that this operation is a special case of repeated vertex splitting.

1.8(c) (Assuming you know what homotopy type means.) Explain why edge subdivision and adding a leaf preserve the homotopy type of the graph, i.e., the homotopy type of the geometric realization of a graph (where each edge is a real interval of unit length, and the edges are “glued” at the vertices).

1.8(d) Show that each connected graph, G, has the homotopy type of B_{d}, the

graph with one vertex and d self-loops, where d = h_{1}(G). 1.8(e) Show that two graphs, G, G′ are of the same homotopy type iff there is a

correspondence between their connected components so that corresponding components have the same value of h_{1}.

1.8(f) Show that two graphs, G, G′ are of the same homotopy type iff they can be obtained from one another by a series of vertex splittings, adding a leaf, and the inverses of these two operations. [Hint: Use Exercise 1.8(e).]

Exercise 1.9. Let G be a digraph, and v ∈ V_{G}. By the indegree of v we mean the number of edges of G whose head is v; by the outdegree we mean the same, with “tail” instead of “head.” By the degree of v we mean the sum of the indegree and outdegree of v; we denote this number deg_{G}(v). 1.9(a) Show that

χ(G) = ∑_{v∈V_{G}}(2 − deg_{G}(v))/2.

1.9(b) Show that if each vertex of G has degree at most two, then each connected

component of G, and therefore G, has vanishing ρ. 1.9(c) Show that if each vertex of G is of degree at least two, then ρ(G) = −χ(G).

Exercise 1.10. 1.10(a) Show that a connected graph that is acyclic, i.e., either an isolated vertex or a tree, either (1) consists of one vertex, or (2) has exactly two vertices of degree one and is a path, or (3) has at least three vertices of degree one.

1.10(b) Show that if G is connected, ρ(G) ≥ 1, and each vertex of G is of degree at last two, then removing an arbitrary edge, e, of G yields a graph, G′ with ρ(G′) < ρ(G). [Hint: Since χ = h_{0}^{acyc} − ρ, if ρ(G′) = ρ(G) then h_{0}^{acyc}(G′) = 1; hence te, he, or both must lie in an acyclic component of G′. Now use Exercise 1.10(a).]

Exercise 1.11. Consider the following two operations on a digraph, G:

(1) discarding an inessential component: we discard from G one of its connected components with vanishing ρ;

(2) pruning: we discard from G a vertex of degree one and its incident edge (this is the opposite operation of leaf adding of Exercise 1.8; a vertex of degree one is called a leaf).

Say that G is sheared if neither of the above two operations can be performed on G, i.e., that all connected components of G have ρ ≥ 1, and G has no vertices of degree one; to shear a digraph is to perform the above two operations until we obtain a sheared graph. 1.11(a) Show that the above two operations leave ρ invariant. 1.11(b) Show that if G is non-empty and sheared, then removing any one edge of

G will reduce its ρ by one. [Hint: Use Exercise 1.10(b).] 1.11(c) Show that if G is connected and h_{1}(G) ≥ 2, then shearing G yields the

subgraph, G′, that consists of all edges and vertices of G that lie on a cycle of G. [Hint: Use induction on |V_{G}| + |E_{G}|; if G contains a vertex of degree one or zero, then use the inductive claim; if not, then every vertex is of degree at least two, so use Exercise 1.10.]

1.11(d) Show that if shearing G yields G′, then G′ is independent of the order of the shearing and consists of all vertex and edges that lie on a cycle in a connected component of ρ ≥ 1.

1.11(e) Show that if shearing G yields G′, then −χ(G′) = ρ(G′) = ρ(G). [Hint: Shearing does not affect ρ, but leaves a graph, G′, with no acyclic components.]

Exercise 1.12. Show that for any digraph, G, the maximum of −χ(H) over all H ⊂ G is ρ(G), and classify when this maximum is achieved. Do so in the following steps: 1.12(a) Show that if H ⊂ G are digraphs, then h_{1}(H) ≤ h_{1}(G). [Hint: As men-

tioned before, h_{1} is the minimum number of edges you need to remove from a graph to leave it free of cycles.]

1.12(b) Use −χ(H) = h_{1}(H)−h_{0}(H) to argue that if G is connected, then −χ(H) ≤ ρ(G), and that equality is equivalent to either: (i) H is empty and h_{1}(G) ≤ 1, or (ii) H is connected and h_{1}(H) = h_{1}(G) ≥ 1.

1.12(c) Show that if H, G are both connected digraphs with H ⊂ G and h_{1}(G) ≥ 2, then then −χ(H) ≤ ρ(G) with equality iff every edge of G that lies on a cycle also lies in H, i.e., G can be “partially” sheared to obtain H. [Hint: Use Exercise 1.11.]

1.12(d) For general G, describe the H ⊂ G for which −χ(H) = ρ(G). 1.12(e) If H_{1}, H_{2} are two subgraphs of G for which −χ(H_{1}) = −χ(H_{2}) = ρ(G),

show that H_{1} ∩ H_{2} and H_{1} ∪ H_{2} also have −χ equal to ρ(G).

Exercise 1.13. By a directed set we mean a set S with a partial order, ≤, such that for any s_{1}, s_{2} ∈ S there is an s ∈ S such that s_{1} ≤ s and s_{2} ≤ s. Given, say, a real-valued function f: S → ℂ, we say that “the limit of f(s) for s ∈ S equals L,” written

lim_{s∈S} f(s) = L

for a real number, L, if for each ϵ > 0 there is an s ∈ S such that |f(t) − L| ≤ ϵ provided that s ≤ t. Show that this limit is unique, i.e., if this limit equals both L and L′, then L = L′.

Exercise 1.14. By a refinement of a morphism, μ: K → G, we mean a morphism μ′: K′ → G that factors through μ, i.e., such that μ′ = τμ for some τ: K′ → K. 1.14(a) Show that any two covering maps of a digraph, G, have a common refiine-

ment. [Hint: use the fibre product.] 1.14(b) Show that if G is connected and μ: K → G is a covering map, then K has

at most [K : G] connected components. 1.14(c) Show that if G is connected, then

h_{1}(K) = h_{0}(K) + (h_{1}(G) − 1)[K : G].

[Hint: use the fact that χ = h_{0} − h_{1} scales under covering maps.] 1.14(d) Show that if G is connected, then G has a covering map of any degree,

d ≥ 1, μ: K → G, with K connected iff h_{1}(G) ≥ 1. 1.14(e) Show that if G is connected and h_{0}(G) = 0, then for any covering map

μ: K → G of degree d ≥ 1, K has d connected components.

1.14(f) Use the above observations to argue that for any G and any ϵ > 0, there is a covering map μ: K → G such that for any covering map μ′: K′ → G that factors through μ we have

ρ(G) ≤ h_{1}(K′)/[K′ : G] ≤ ρ(G) + ϵ.

This last part of this exercise means that

lim_{\{μ: K→G\}} \frac{h_{1}(K)}{[K : G]} = ρ(G)

over the directed set of covering maps K → G (ordered by refinement), in view of Exercise 1.13.

Exercise 1.15. Show that if K_{1} → G and K_{1} → G are two Abelian morphisms (see Exercise 1.5(h)), then their fibre product is Abelian. Prove a limit statement like (1.3), as proven in Exercise 1.14, where the limit is taken over all Abelian morphisms.

Exercise 1.16. Prove Proposition 1.5, in the following steps. Fix L_{1}, L_{2} as in the proposition. Consider a subgraph, L′_{2} ⊂ L_{2}, such that |V_{L′_{2}}| + |E_{L′_{2}}| is as small as possible such that

ρ(L_{1} ×_{B_{2}} L′_{2}) > ρ(L_{1})ρ(L′_{2}).

Show the following of L′_{2}: 1.16(a) L′_{2} is connected [Hint: if not, at least one of its components is a counterex-

ample to the SHNC.]; 1.16(b) L′_{2} has no vertex of degree zero; 1.16(c) L′_{2} has no vertex of degree one, i.e., L′_{2} is pruned [Hint: otherwise prune

L′_{2}.]; 1.16(d) ρ(L′_{2}) > 0 [Hint: since each vertex of L′_{2} is of degree at least two, by

Exercise 1.9 ρ(L′_{2}) = 0 iff L′_{2} is a cycle.] 1.16(e) if H is the shearing of L_{1} ×_{B_{2}} L′_{2} (see Exercise 1.11), then the number of

edges in H over any edge of L′_{2} is at least ρ(L_{1}) + 1 [Hint: if not, discard any such edge of L′_{2}.];

1.16(f) if H is the shearing of L_{1} ×_{B_{2}} L′_{2}, then the number of vertices over any vertex of L′_{2} is at least ρ(L_{1}) + 1 [Hint: each vertex of L′_{2} is incident upon at least one edge of L′_{2}.]

Exercise 1.17. Prove Theorem 1.6 as follows. Consider the following transformation on étale bigraphs L → B_{2}: replace each edge of colour 1 in L by an oriented path of length two of two edges of colour 1 (oriented as the original edge was), simultaneously replace every edge of colour 2 in L by a path of length four with edges of colour 1, then 2, then 1 in the opposite orientation, then 2 in the opposite orientation. If v is a vertex of L of degree four, then in the new graph we identify (or “collapse”) the two incoming edges of colour 1 to v. Show that the transformed graphs the the desired properties; show that

ρ(L_{1} ×_{B_{2}} L_{2}) > ρ(L_{1})ρ(L_{2})

iff the same is true with L_{1}, L_{2} replaced by their transformed graphs. See [JKM03].

Exercise 1.18. This exercise will prove that ρ(G) and h_{0}^{acyc}(G) are the L^{2} Betti numbers of the universal cover of G. This belongs in a different section.

Exercise 1.19. Let B be a digraph, and consider the category of “graphs over B” (also called the slice category over B): the objects of this category are digraph morphisms ϕ: G → B; a morphism from ϕ_{1} : G_{1} → B to ϕ_{2} : G_{2} → B is a morphism ν: G_{1} → G_{2} such that ϕ_{1} = ϕ_{2}ν. 1.19(a) Show that the product in the category of graphs over B is just the fibre

product over B. 1.19(b) Show why a “coloured subgraph” represents a subobject of an object in the

category of graphs over B_{d}. 1.19(c) Explain how an automorphism in the category of graphs over B relates to

how we define a Galois morphism in Exercise 1.5(g).

2. The Maximum Excess and Sheaves

In this section we discuss the maximum excess, as a general concept in linear algebra. We will then realize that a very special case of it, defined for any graph, G, amounts to ρ(G). This will then motivate our definition of sheaf.

2.1. The Maximum Excess of a Linear Family.

Definition 2.1. By a linear family we mean the data (𝔽, A, B, α) (sometimes we just write α) consisting of (1) a field, 𝔽, (2) finite dimensional 𝔽-vector spaces, A, B, and (3) a collection, α = {α_{i}}_{i∈I}, of 𝔽-linear maps from A to B. For U ⊂ B, we define the neighbourhood of U (with respect to α) to be

Γ_{α}(U) = {a ∈ A | ∀i ∈ I, α_{i}(a) = U};

we define the excess of U to be

excess_{α}(U) = dim(Γ_{α}(U)) − dim(U);

we define the maximum excess of α to be

m.e.(α) = max_{U⊂B} (excess_{α}(U));

we define the excess maximizers (or simply maximizers) of α to be

Maximizers(α) = {U ⊂ B | excess_{α}(U) = m.e.(α)}.

We will often drop the subscript α when it is clear.

We shall later explain that this definition is motivated by (and is a generalization of) the Abelian limit homology groups (see Section ??); another general motivation for this definition is given in Exercise 2.2, as a trivial bound for the dimension of the kernel of any linear combination of elements of the linear family.

It is easy to check that the excess is a supermodular function, in that

excess(U_{1} + U_{2}) + excess(U_{1} ∩ U_{2}) ≥ excess(U_{1}) + excess(U_{2})

for all U_{1}, U_{2} ⊂ B, and that the inequality occurs precisely when the inclusion

(2.1)  Γ_{α}(U_{1}) + Γ_{α}(U_{2}) ⊂ Γ_{α}(U_{1} + U_{2})

is a proper inclusion; see Exercise 2.3. As a consequence we have that Maximizers(α) is closed under sum and intersection, and that (2.1) holds with equality whenever U_{1}, U_{2} ∈ Maximizers(α).

We now wish to describe ρ(G) as the maximum excess of a natural family of linear maps. We shall need one result.

Definition 2.2. Let 𝔽 be a field, and let A, B be finite dimensional 𝔽-vector spaces. Let α = {α_{i}}_{i∈I} be a family of 𝔽-linear maps from A to B. Given direct sum decompositions

A ≃ A_{1} ⊕ ⋯ ⊕ A_{n}, B ≃ B_{1} ⊕ ⋯ ⊕ B_{m},

we have an inclusion A_{j} → A for each j = 1, …, n,

a ↦ (0, …, 0, a, 0, …, 0) ∈ {0} × ⋯ × {0} × A_{j} × {0} × ⋯ × {0}

(which we identify with a subspace of A); similarly for B_{k} → B for k = 1, …, m. We say that a direct sum decompositions of A, B as above are compatible with α if for each i ∈ I, α_{i}: A → B factors through some A_{j} → A and B_{k} → B; i.e., is a function of only A_{j}, and the image of α_{i} consists of vectors of B that are zero on summands B_{k′} with k′ ≠ k.

Proposition 2.3. Consider the situation of Definition 2.2. For any U ⊂ B, we have Γ_{α}(U) = Γ_{α}(U′), where U′ is the largest subspace of B that is a direct subsum, i.e.,

U′ ≃ B′_{1} ⊕ ⋯ ⊕ B′_{m},

where B′_{k} ⊂ B_{k} for k = 1, …, m, and ≃ is the same isomorphism as in the direct sum decomposition of B. In particular, U ∈ Maximizers(α) implies that U′ = U in this notation. Furthermore, for any U ⊂ B, Γ(U) is a direct subsum of A.

Proof. See Exercise 2.4. □

2.2. Graphs as Linear Families.

Definition 2.4. Let G be a digraph and 𝔽 a field. By the simple 𝔽-linear system on G we mean the map system (𝔽, A, B, α), where

A = 𝔽^{E_{G}}, B = 𝔽^{V_{G}},

and

α = {α_{i}}_{i∈I} and I = E × {h, t},

where α_{(e,h)} is the projection to the e-component, followed by the inclusion of of he component, and similarly for α_{(e,t)}.

By Proposition 2.3, the maximizers of α must be of the form 𝔽^{V′} with V′ ⊂ V_{G}. Furthermore,

excess(𝔽^{V′}) = dim(Γ(𝔽^{V′})) − |V′| = |E′| − |V′|,

where E′ are those edges of G whose two endpoints lie in V′; in other words

excess(𝔽^{V′}) = −χ(G|_{V′}),

where G|_{V′} is the subgraph of G induced on the vertices V′. It easily follows that

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

(see Exercise 2.2(c)).

2.3. Sheaves. We now wish to generalize the simple 𝔽-linear system on G of Definition 2.4. These more general linear systems can be viewed as the generalization of the notion of a graph; this systems give rise to “additional morphisms” of graphs, and one can form kernels, images, cokernels, quotients, etc., when working with these linear systems.

Definition 2.5. 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 an 𝔽-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 comprised of the value U at each vertex and edge, with all restriction maps being the identity map. The constant sheaf \underline{𝔽} will be called the structure sheaf of G (with respect to the field, 𝔽), for reasons to be explained later. To an 𝔽-vector sheaf, F, on G we associate the linear system (𝔽, F(E), F(V), α) where

F(E) = ⨁_{e∈E_{G}} F(e), F(V) = ⨁_{v∈V_{G}} F(v),

and α = {α_{i}}_{i∈I}, with I = E_{G} × {h, t}, where α_{(e,h)} is projection onto F(e), followed by F(e, h), followed by the inclusion of F(he) into F(V); similarly for α_{(e,t)}.

In particular, the simple 𝔽-linear system of G is just the linear system associated to the structure sheaf, \underline{𝔽}, on G.

Definition 2.6. We define the Euler characteristic of an 𝔽-sheaf on G, F, to be

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

We define the neighbourhood of a subspace, U ⊂ F(V), its excess, and the maximum excess and excess maximizers of F to be those of the associated linear family.

Here is another example of a class of sheaves. To any subgraph, L ⊂ G, we associate the 𝔽-sheaf on G, \underline{𝔽}_{L} to be the sheaf whose values are 𝔽 on L and zero elsewhere, and whose restriction maps are the identity whenever the source and target are 𝔽 (otherwise the source or target or both are zero, and the restriction must be the zero map). In other words, \underline{𝔽}_{L} is just \underline{𝔽} on G restricted to L and “extended to all of G by zero.” Clearly χ(\underline{𝔽}_{L}) = χ(L). Given that the maximum excess of the simple sheaf associated to a graph is its reduced cyclicity, it is easy to see that m.e.(\underline{𝔽}_{L}) = ρ(L). In fact, this can also be seen from the alternate description of the maximum excess in the proposition below.

Definition 2.7. We say that F′ is a subsheaf of a sheaf, F, on a graph, G, if for each P ∈ V_{G} ⨿ E_{G} we have F′(P) is a subspace of F(P). Furthermore, we say that F′ is an edge-full subsheaf if

F′(e) = F(e) ∩ F′(he) ∩ F′(te)

for each e ∈ E_{G}.

Proposition 2.8. For any sheaf, F, on a graph, G, we have

m.e.(F) = max_{F′⊂F} −χ(F′).

Furthermore, if the excess maximizers (or simply maximizers) of F denote the set of it subsheaves, F′, such that −χ(F′) = m.e.(F), then the set of maximizers is closed under intersection and sum.

Proof. The point is that a subsheaf the maximizes −χ is necessarily edge-full, and a direct subsum of F(V) naturally corresponds to an edge-full subsheaf of F, and vice versa, with the excess of the subsum equal to minus the Euler characteristic of the sheaf. The closure of the maximizers under intersection and sum follows from that of the associated linear family. See Exercise 2.5. □

As a corollary to this proposition we get the following.

Proposition 2.9. Let F_{1} ⊂ F_{2} be sheaves on a graph, G. Then we have

m.e.(F_{1}) ≤ m.e.(F_{2}),

with equality iff the minimum (i.e., intersection of all) excess maximizer of F_{2} is a subsheaf of F_{1}.

2.4. Exercises.

Exercise 2.1. Given an arbitrary field, 𝔽, and integer n ≥ 1, say that Z ⊂ 𝔽^{n} is Zariski closed if it is described as the zero set of some finite set of polynomials, {f_{i}}_{i∈I}, i.e.,

Z = {x ∈ 𝔽^{n} | f_{i}(x) = 0 ∀i ∈ I},

with each f_{i} ∈ 𝔽[x_{1}, …, x_{n}]. Say that U ⊂ 𝔽^{n} is Zariski open if it is the complement of a Zariski closed set. Say that U ⊂ 𝔽^{n} is generic if it contains a nonempty Zariski open subset of 𝔽^{n}. 2.1(a) Show that the Zariski open sets in 𝔽^{n} are closed under arbitrary union and

finite intersection. 2.1(b) Show that if 𝔽 is infinite, then any generic set is nonempty; moreover, show

that for any generic set, G ⊂ 𝔽^{n}, there is an integer, d, such that if A ⊂ 𝔽 is a finite subset, then at least (|A| − d)^{n} elements of A^{n} lie in G.

2.1(c) Show that generic subsets of 𝔽^{n} are closed under arbitrary union. Show if 𝔽 is finite, then every subset of 𝔽^{n} is Zariski open. Show that generic subsets of 𝔽^{n} are closed under finite intersection iff 𝔽 is infinite.

2.1(d) If Z ⊂ 𝔽^{n} is the zero set of an arbitrary set of polynomials, explain how the Hilbert basis theorem (see [Har77]) implies that this set of polynomials can be taken to be finite.

2.1(e) Let M = M(x) be a matrix whose elements are polynomials in indeterminates x_{1}, …, x_{n} over a field, 𝔽. Show that for any integer, k ≥ 0, the set of x ∈ 𝔽^{n} for which the kernel of M is of dimension at most k is a Zariski open subset of 𝔽^{n}; do this by writing determinants of submatrices of M. The smallest value of k for which this subset is non-empty is called the generic kernel dimension of M.

2.1(f) Consider M = M(x) as in Exercise 2.1(e). View M as a matrix in the field 𝔽(x_{1}, …, x_{n}). Explain how the shape of the echelon form of M over 𝔽(x_{1}, …, x_{n}) can be used to determine the generic kernel dimension of M.

Exercise 2.2. Let 𝔽 be a field, and A, B finite dimensional 𝔽-vector spaces. Let α = {α_{i}}_{i∈I} be a collection of linear maps from A to B. 2.2(a) Let θ = {θ_{i}}_{i∈I} ∈ 𝔽^{I} be a collection of elements of 𝔽 such that θ_{i} = 0 for

all but finitely many i. Define

θ · α = ∑_{i∈I} θ_{i}α_{i}.

Show that

dim(ker(θ · α)) ≥ m.e.(α).

2.2(b) If I is finite, show that there is an integer, N, such that for all θ ∈ 𝔽^{I} we

have

dim(ker(θ · α)) ≥ N

with equality holding for θ in a Zariski open subset of 𝔽^{I} (see Exercise 2.1, especially 2.1(e)). We call N the generic dimension of the kernel of θ · α (understanding α fixed and θ regarded as indeterminates).

2.2(c) Say that α is tight if the generic dimension of the kernel of θ · α equals the maximum excess. Show that the simple 𝔽-linear family associated to a graph is tight. [Hint: It suffices to show that if G is a connected graph, then there is at least one linear combination of the family that has ρ(G) as its kernel dimension. Fix a spanning tree, T, of G. Choose coefficients of the combination that are one whenever they involve edges of T, and are variable along the remaining edges; show that a generic linear combination is onto, unless G = T is a tree.]

2.2(d)^{∗} Show that α is tight whenever the family is compatible with a direct sum decomposition whose direct summands of A are all one dimensional. [Hint: See [Fri11b, Fri11c].]

2.2(e) Let 𝔽 be an arbitrary field, and let B = 𝔽^{4} be spanned by x, y, z, w. Let A = 𝔽^{2} ⊕ 𝔽^{2} and set

α_{1}((a_{1}, a_{2}, a_{3}, a_{4})) = a_{1}x + a_{2}y,
α_{2}((a_{1}, a_{2}, a_{3}, a_{4})) = a_{1}z + a_{2}w,
α_{3}((a_{1}, a_{2}, a_{3}, a_{4})) = a_{3}x + a_{4}z,
α_{4}((a_{1}, a_{2}, a_{3}, a_{4})) = a_{3}y + a_{4}w.

Show that the generic kernel dimension of this linear family is one, but its maximum excess is zero.

Exercise 2.3. Let α = {α_{i}}_{i∈I} be a linear family of maps A → B. 2.3(a) Show that the function, f, from subspaces of B to the integers defined by

f(U) = dim(U)

is modular, i.e., for subspaces U_{1}, U_{2} of B we have

f(U_{1}) + f(U_{2}) = f(U_{1} ∩ U_{2}) + f(U_{1} + U_{2}),

where U_{1} + U_{2} is the span of U_{1} and U_{2} in B. 2.3(b) Show that for any subspaces U_{1}, U_{2} of B we have

Γ_{α}(U_{1}) ∩ Γ_{α}(U_{2}) = Γ(U_{1} ∩ U_{2})

and

(2.2)  Γ_{α}(U_{1}) + Γ_{α}(U_{2}) ⊂ Γ(U_{1} + U_{2}).

Conclude that

g(U) = dim(Γ_{α}(U))

is a supermodular function, i.e.,

g(U_{1}) + g(U_{2}) ≤ g(U_{1} ∩ U_{2}) + g(U_{1} + U_{2}),

with equality iff we have equality in the inclusion of (2.2). 2.3(c) Conclude that the function

h(U) = g(U) − f(U) = excess_{α}(U)

is a supermodular function, and that

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

holds with equality iff (2.2) holds with equality.

Exercise 2.4. Prove Proposition 2.3, in the following steps. Given U ⊂ B, for i = 1, …, m let B′_{i} ⊂ B_{i} be given by

B′_{i} = {b_{i} ∈ B_{i} | (0, …, 0, b_{i}, 0, …, 0) ∈ U}.

Show that U′ = B′_{1} ⊕ ⋯ ⊕ B′_{m} satisfies U′ ⊂ U but Γ_{α}(U′) = Γ_{α}(U). Hence U does not achieve the maximum excess if U′ ≠ U. Furthermore, show that Γ_{α}(U′) is of the form A′_{1} ⊕ ⋯ ⊕ A′_{n} with A′_{i} ⊂ A_{i}.

Exercise 2.5. Prove Proposition 2.8 as follows. Consider the natural decomposition of F(V) into the summands F(v) with v ranging over V_{G}. Given a subsum, U, of F(V), i.e., a subspace U(v) ⊂ F(v) for each v ∈ V_{G}, associate to U the subsheaf, F′, of F by setting F′(v) = U(v) for each v ∈ V_{G}, and

F′(e) = F(e) ∩ U(he) ∩ U(te).

Show that F′ is edge-full, and that the excess of U is −χ(F′). Conversely, show that if F′ is any subsheaf of F, then setting U to be the direct sum of the F′(v) with v ∈ V_{G}, we have that

−χ(F′) ≤ excess(U),

with equality iff F is edge-full. Then notice that since the excess maximizers of a linear family are closed under intersection and sum, then so are the excess maximizers of a sheaf.

3. Proof of the SHNC

In this section we give a short proof of the SHNC. Motivation of the sheaves we use here will be delayed until Section 4.

Definition 3.1. Let G be a finite group, 𝔽 a field, and k ≥ 0 an integer. We denote by 𝔽^{k×G} the set of k × G matrices with entries in 𝔽, i.e., matrices with k rows and whose columns are indexed on G. As such M gives rise to a linear transformation from 𝔽^{G} to 𝔽^{k}. We say that M ∈ 𝔽^{k×G} is totally independent if any subset of k columns of M are linearly independent.

If A ⊂ G, let 𝔽_{A}^{G} with the subset of 𝔽^{G} of vectors that vanish outside the Acomponents. We easily see (see Exercise 3.1) that M ∈ 𝔽^{k×G} is totally independent iff for all A ⊂ G we have

dim(ker(M) ∩ 𝔽_{A}^{G}) = max(0, |A| − k).

Definition 3.2. Let G be a finite group, and let g_{1}, g_{2} ∈ G. Let L be a subgraph of a Cayley graph G = Cayley(G; g_{1}, g_{2}). For each totally independent M ∈ 𝔽^{k×G} we define a sheaf, K(M), that we call the k-th power (L, G, G)-kernel determined by M, as follows: for each v ∈ V_{G} we set

G_{L}(v) = {g ∈ G | vg^{−1} ∈ V_{L}},

and

(K(M))(v) = ker(M) ∩ 𝔽^{G_{L}(v)}
= {u ∈ 𝔽^{G} | Mu = 0 and u(g) ≠ 0 implies g ∈ G_{L}(v)};

similarly, for e ∈ E_{G} we set

G_{L}(e) = {g ∈ G | eg^{−1} ∈ E_{L}},

and

(K(M))(e) = {u ∈ 𝔽^{G} | Mu = 0 and u(g) ≠ 0 implies g ∈ G_{L}(e)};

finally restriction maps are given by inclusions (notice that (K(M))(e) is included in both (K(M))(he) and (K(M))(te) since G_{L}(e) is a subset of both G_{L}(he) and G_{L}(te).

The following three theorems imply the SHNC:

Theorem 3.3. The SHNC is true provided that for all Cayley graphs, G and all coloured subgraphs, L_{1}, L_{2} of G we have

ρ(L_{1} ×_{B_{2}} L_{2}) ≤ ρ(L_{1})ρ(L_{2}).

Theorem 3.4. Let L be a coloured subgraph of a Cayley graph G = Cayley(G; g_{1}, g_{2}). Assume that there is a ρ(L)-th power (L, G, G)-kernel, K = K(M), that has maximum excess zero. Then for all coloured L_{2} ⊂ G we have

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

Theorem 3.5. Let L be a coloured subgraph of a Cayley graph G = Cayley(G; g_{1}, g_{2}). Let 𝔽 be an infinite field. Then there is a set, M ⊂ 𝔽^{ρ(L)×G}, such that

(1) for each M ∈ M, the ρ(L)-th power (L, G, G)-kernel K = K(M) has maximum excess zero; and

(2) M is generic, i.e., contains a nonempty Zariski open subset of 𝔽^{k×G}; in other words, there is a polynomial f = f({m_{ij}}) in indetermines m_{ij} indexed in integers i with 1 ≤ i ≤ ρ(M) and j ∈ G, with coefficients in 𝔽, such that if M ∈ 𝔽^{ρ(L)×G} and f(M) ≠ 0, then M ∈ M.

We shall later explain that the sheaves K = K(M) arise as the kernel of a certain surjective morphism of sheaves. In the next subsection we prove Theorems 3.3 and 3.4, which is quite easy. Theorem 3.5 will be proven in the two subsections thereafter.

3.1. First Steps: Proofs of Theorems 3.3 and 3.4.

Proof of Theorem 3.3. Let L_{1} → B_{2} and L_{2} → B_{2} be étale.

We claim that there is an inclusion L_{1} → L′_{1}, where L′_{1} that admits a covering map to B_{2}; indeed, the number of vertices without a head of colour 1 in L_{1} is the same as those without a tail of colour 1, and similarly for colour 2; so we form L′_{1} by an arbitrary matching between vertices missing tails and those missing heads of each colour. The resuling graph, L′_{1} has each vertex with exactly one head and tail of each colour, and therefore admits a covering map to B_{2}.

Hence L_{1} → B_{2} factors as an inclusion, L_{1} → L′_{1}, following by a covering map L′_{1} → B_{2}; similarly for L_{2} → B_{2}, as L_{2} → L′_{2} → B_{2}. Let L → B_{2} be a common refinement of L′_{1} → B_{2} and L′_{2} → B_{2}, e.g., their fibre product. By the Normal Extension Theorem of Galois Graph Theory (see [Fri93, ST96, Fri11b] or Exercise 3.2), L → B_{2} has a normal extension G → L → B_{2}, meaning that G is a Cayley graph. Then K_{1} = L_{1} ×_{L′_{1}} G and K_{2} = L_{2} ×_{L′_{2}} G are subgraphs of G (by stability of inclusions under base extension), and are coverings of L_{1} and L_{2} respectively (by stability of covering maps under base extension). Hence to verify the SHNC on (L_{1}, L_{2}), it suffices to do so on (K_{1}, K_{2}), and K_{1}, K_{2}, as subgraphs of G, are subgraphs of the same Cayley graph on two generators. □

Proof of Theorem 3.4. Fix L ⊂ G where G = Cayley(G; g_{1}, g_{2}). Assume that there is an L_{2} ⊂ G such that

(3.1)  ρ(L ×_{B_{2}} L_{2}) > ρ(L)ρ(L_{2}).

According to Proposition 1.5, we may assume that L_{2} has all vertices of degree two or greater, and that there is an H ⊂ L×_{B_{2}} L_{2} with −χ(H) = ρ(L×_{B_{2}} L_{2}) such that each vertex and edge of L_{2} has at least ρ(L) + 1 preimages in H (via the inclusion of H into L ×_{B_{2}} L_{2}, followed by the projection onto L_{2}).

For each P ∈ V_{L_{2}} ⨿ E_{L_{2}}, let

U(P) = {g ∈ G | (P g^{−1}, P) ∈ H},

and otherwise let U(P) be empty; let

U(P) = ker(M) ∩ 𝔽^{U(P)},

and set

U(V) = ⨁_{v∈V_{G}} U(v), U(E) = ⨁_{e∈E_{G}} U(e).

Then U(V) ⊂ K_{M}(V), and U(E) ⊂ Γ(U(V)). It follows that

m.e.(K_{M}) ≥ excess(U(V))

= ∑_{e∈E_{G}} max(0, |U(e)| − ρ(L)) − ∑_{v∈V_{G}} max(0, |U(v)| − ρ(L)).

But |U(P)| is at least ρ(L) + 1 for P ∈ V_{L_{2}} ⨿ E_{L_{2}}, or otherwise zero. Hence

m.e.(K_{M}) ≥ ∑_{e∈E_{L_{2}}}(|U(e)| − ρ(L)) − ∑_{v∈V_{L_{2}}}(|U(v)| − ρ(L))

= −χ(H) − ρ(L)(|E_{L_{2}}| − |V_{L_{2}}|) = ρ(L ×_{B_{2}} L_{2}) − ρ(L)ρ(L_{2}) > 0.

This contradicts the fact that K_{M} has maximum excess zero. □

3.2. Outline of Proof of Theorem 3.5. The proof of Theorem 3.5 is a bit more involved, especially the notation. In this subsection we prove Theorem 3.5 on the basis of three lemmas; these three lemmas are easy to prove, but a bit cumbersome to include in the discussion here. Based on these three lemmas we complete the Proof of Theorem 3.5.

Definition 3.6. Let M ∈ 𝔽^{k×G} and let m′ = {m′_{g}}_{g∈G} ∈ 𝔽^{G}. By M augmented with m′, denoted [M, m′], we mean the matrix in 𝔽^{(k+1)×G} whose first k rows are M, and whose last row is m′.

If M′ is M with any row augmented, then the kernel of M′ is contained in that of M. It follows that for any fixed (L, G, G), K_{M′}, as in Definition 3.2, is a subsheaf of K_{M}. Using Proposition 2.9 we will easily establish the following lemma.

Lemma 3.7. Let L be a subgraph of a Cayley graph, G, on a group, G, on two generators. For some integer, k, let M ∈ 𝔽^{k×G} satisfy m.e.(K_{M}) > 0, with K_{M} as in Definition 3.2. Then there is a u ∈ 𝔽^{G}, such that

∑_{g∈G} m′ · u ≠ 0 ⟹ m.e.(K_{[M,m′]}) < m.e.(K_{M}).

Definition 3.8. By a dimension profile on a digraph, G, we mean a function

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

where ℤ_{≥0} denotes the non-negative integers. 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 graph, G = Cayley(G; g_{1}, g_{2}), 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 M is totally independent and for which K_{M} a subsheaf, F, with dim(F) = n.

Definition 3.9. A locally closed set in a topological space is the intersection of an open set with a closed set; a constructible set is a finite union of locally closed sets.

If a locally closed set is not open, then it is contained in a closed, proper subset of the space. Hence a constructible set in 𝔽^{n} with the Zariski topology is either generic or lies in a closed, proper subset of 𝔽^{n}.

Lemma 3.10. Let n, L, G, G, 𝔽, k be as in Definition 3.8. Then

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

is constructible.

Lemma 3.11. Let n, L, G, G, 𝔽, k be as in Definition 3.8. Then for each g ∈ G we have M(n)g = M(ng), where G acts on 𝔽^{k×G} by a certain permutation of the columns, and where G acts on dimension profiles by

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

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

We shall prove Lemmas 3.7, 3.10, and 3.11 in Section ??. Assuming these lemmas, let us complete the proof.

Theorem 3.12. The SHNC, i.e., Conjecture 1.4, holds.

Proof. Fix L, G, G, 𝔽, k as in Definition 3.8, and assume that 𝔽 is infinite. Let the generic dimension profiles of L, G, G, 𝔽, k be

GDP(L, G, G, 𝔽, k) = {n | M(n) = M(L, G, G, 𝔽, k) is generic }.

Let ρ_{max}(k) = ρ_{max}(L, G, G, 𝔽, k) of

{−χ(n) | n ∈ GDP(L, G, G, 𝔽, k)}.

According to Lemma 3.10, we have that there is a generic set of M ∈ 𝔽^{k×G} for which ρ(K_{M}) = ρ_{max}(k).

Now we claim that for any k ≥ 0 we have ρ_{max}(k) is divisible by |G|. Indeed, given k ≥ 0, let n_{0} be a generic dimension profile with |n_{0}| maximal subject to −χ(n_{0}) = ρ_{max}(k). Then

N = M(n_{0}) ∩ M(n_{0}g) ∩ {M ∈ 𝔽^{k×G} | ρ(K_{M}) = ρ_{max}(k)}

is a generic set; but since the excess maximizers is closed under taking sums, we have that M ∈ N implies that there is an excess maximizer, F, of K_{M} with

dim(F) ≥ max(n_{0}, n_{0}g),

where the max here is taken pointwise in V_{G} ⨿ E_{G}. Hence there must be a generic dimension profile n_{1} ≥ max(n_{0}, n_{0}g) with −χ(n_{1}) = ρ_{max}(k). But then |n_{1}| > |n_{0}|, unless n_{0} = n_{0}g. Hence n_{0} = n_{0}g for all g ∈ G; and hence −χ(n_{0}), which is just ρ_{max}(k), is divisible by |G|.

Now we claim that for each k ≥ 0 we have

(3.2)  ρ_{max}(k) > 0 ⟹ ρ_{max}(k + 1) ≤ ρ_{max}(k) − |G|.

Indeed, otherwise, since ρ_{max}(k + 1), ρ_{max}(k) are divisible by |G|, we would have ρ_{max}(k + 1) = ρ_{max}(k). It follows that there is a generic set of M′ ∈ 𝔽^{(k+1)×G} for which ρ(K_{M′}) = ρ(K_{M}), where M is obtained from M′ by discarding the last row. But this easily implies (see Exercise 3.3) that for a generic set, S, of 𝔽^{k×G}, for each M ∈ S we have that ρ(K_{[M,m′]}) = ρ(K_{M}) for generic m′ ∈ 𝔽^{G}. But this contradicts Lemma 3.7. Hence (3.2) holds.

For k = 0, we have that the kernel of

𝔽_{L}G → 𝔽^{0}

is just 𝔽_{L}G, which is just |G| translates of L, whose maximum excess is ρ(L)|G|. Hence

ρ_{max}(0) = ρ(L)|G|.

Hence, by induction, (3.2) implies that for all k between 1 and ρ(L) we have

ρ_{max}(k) ≤ (ρ(L) − k)|G|.

In particular, ρ_{max}(ρ(L)) = 0, and so the generic ρ-kernel has maximum excess 0. □

3.3. End of the Proof of the SHNC. In this subsection we prove Lemmas 3.7, 3.10, and 3.11. This completes a proof of the SHNC that does not involve cohomology or pullbacks per se.

Proof of Lemma 3.7. Let F be the minimal (i.e., intersection of all) excess maximizers of K_{M}. Since K_{M} has positive maximum excess, we have −χ(F) > 0, and therefore F(e) ≠ 0 for some e; fix such an e, and let u ∈ F(e) with u ≠ 0. Since F(e) ⊂ 𝔽^{G}, we may view u as an element of 𝔽^{G}. But if

∑_{g∈G} m′ · u ≠ 0,

then u ∉ K_{M′}(e), and so F(e) is not a subset of K_{M′}(e), and so, according to Proposition 2.9, m.e.(K_{M′}) is strictly less than m.e.(K_{M}). □

Proof of Lemma 3.10. Note that for each M ∈ 𝔽^{k×G} we have K_{M}(P) is a subspace of 𝔽^{G}; hence an n(P) dimensional subspace of K_{M}(P) can be specified by n(P) appropriate vectors in 𝔽^{G}. We introduce |f| vectors of |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 totally independent;

(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, if C ⊂ 𝔽^{k×G} ⊕ 𝔽^{|n|×G} of pairs (M, x), that satisfy conditions (1)–(5) above, where x = {x_{P,i}}, then there is 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 (M, x) ∈ C iff 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). Note that in algebraic geometry we often assume that 𝔽 is algebraically closed, but here we can deduce the existence of f_{i} and f̃_{j} as above with coefficients in the algebraic closure, and therefore conclude constructibility; see Exercise 3.6. Hence M(n), the image of C, is constructible. □

Proof of Lemma 3.11. We shall prove a stronger statement than Lemma 3.11, that will require more group actions and notation. Namely, for g ∈ G and M ∈ 𝔽^{k×G}, let Mg be the matrix whose g′ column, for g′ ∈ G, is the g^{−1}g′ column of M. For g ∈ G and any sheaf, F, on G, let Fg be the sheaf given by

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

(with restriction maps similarly translated by g^{−1}). For g ∈ G let π = π_{g}: 𝔽^{G} → 𝔽^{G} sending a = {a_{h}}_{h∈G} to πa whose coordinates are

(πa)_{h} = a_{gh}.

Finally, if F ⊂ \underline{𝔽}^{G}, there is a natural sheaf πF; namely the values of F are subspaces of 𝔽^{G} and its restriction maps are inclusions, so let πF the values that are π acting on the values of F (and with restriction maps being inclusions). For any g ∈ G and M ∈ 𝔽^{k×G}, we have M is totally independent iff Mg is; if so, we shall show that

(3.3)  π(K_{M}(L)g) = K_{Mg}(L).

This implies the Lemma 3.11, for if F is a subsheaf of K_{M}(L), then πFg is a subsheaf of K_{M}(L), and

dim(πFg) = dim(Fg) = dim(F)g;

this first equality holds since π does not change the dimension of subspaces of 𝔽^{G}, and the second since for each P ∈ V_{G} ⨿ E_{G} we have (Fg)(P) = F(P g^{−1}).

To prove (3.3), first note that for any v ∈ V_{G} we have

G_{L}(vg^{−1}) = {h ∈ G | (vg^{−1})h ∈ V_{L}} = {g(g^{−1}h) ∈ G | v(g^{−1}h) ∈ V_{L}} = gG_{L}(v).

Similarly for e ∈ E_{G}. Hence for P ∈ V_{G} ⨿ E_{G} we have

(K_{M}(L)g)(P) = ker(M) ∩ 𝔽^{G_{L}(P g^{−1})}
= ker(M) ∩ 𝔽^{gG_{L}(P)} ⊂ 𝔽^{G}.

So consider the coordinate permutation π: 𝔽^{G} → 𝔽^{G} sending a = {a_{h}}_{h∈G} to πa whose coordinates are

(πa)_{h} = a_{gh}.

We have

a ∈ 𝔽^{gG_{L}(P)} ⟺ a_{h} = 0 ∀h ∉ gG_{L}(P) ⟺ a_{gg^{−1}h} = 0 ∀g^{−1}h ∉ G_{L}(P)

⟺ a_{gh′} = 0 ∀h′ ∉ G_{L}(P) ⟺ (πa)_{h′} = 0 ∀h′ ∉ G_{L}(P) ⟺ πa ∈ 𝔽^{G_{L}(P)}, Furthermore

a ∈ ker(M) ⟺ π^{−1}(πa) ∈ ker(M) ⟺ πa ∈ ker(N)

where N is obtained from M by permuting its columns so that

π^{−1}b ∈ ker(M) ⟺ b ∈ ker(N);

but

π^{−1}b ∈ ker(M) ⟺ M(π^{−1}b) = 0 ⟺ ∑_{h∈G} M_{i,h}(π^{−1}b)_{h} = 0 ∀i

⟺ ∑_{h∈G} M_{i,h}b_{g^{−1}h} = 0 ∀i ⟺ ∑_{h′∈G} M_{i,gh′}b_{h′} = 0 ∀i,

so the h′ column of N is the gh′ column of M; hence N is just what we wrote as Mg. Hence for all P ∈ V_{G} ⨿ E_{G} we have

a ∈ (K_{M}(L)g)(P) ⟺ a ∈ ker(M) ∩ 𝔽^{G_{L}(P g^{−1})}
⟺ πa ∈ ker(Mg) ∩ 𝔽^{G_{L}(P)} ⟺ πa ∈ (K_{Mg}(L))(P).

This establishes (3.3). □

3.4. Exercises.

Exercise 3.1. Let 𝔽 be a field, and M ∈ 𝔽^{m×n} an m × n matrix with entries in M and with n ≥ m. Show that the following are equivalent:

(1) any m columns of M are linearly independent;

(2) for any A ⊂ {1, …, n} we have

dim(ker(M) ∩ 𝔽_{A}^{n}) = max(0, |A| − m),

where 𝔽_{A}^{n} denotes the subset of 𝔽^{n} of vectors whose components outside of A vanish;

(3) the same as condition (2), except for any A ⊂ {1, …, n} with |A| = m. [Hint: (2) immediately implies (3); (3) implies (1) since the rank of M restricted to the columns of A plus the dimension of its kernel equals m; for (1) implies (2) show that the rank of M restricted to the columns of A is min(m, |A|).]

Exercise 3.2. Let π: K → G be a covering map of degree n. For an integer, r, let K_{G}^{r} be the r-fold fibre product K ×_{G} ⋯ ×_{G} K. Let Λ_{G}^{r}(K) be the subgraph of K_{G}^{r} induced on the vertices of the form (v_{1}, …, v_{r}) with v_{1}, …, v_{r} distinct. 3.2(a) Show that projection onto the first coordinate (or any coordinate) gives a

covering map from K_{G}^{r} to K; show that its degree is n^{r−1}. 3.2(b) Show that same with K_{G}^{r} replaced with Λ_{G}^{r}(K); show that its degree is

(n − 1)(n − 2) ⋯ (n − r + 1). 3.2(c) Show that the first coordinate projection Λ_{G}^{n}(K) → K followed by K → G

is Galois with Galois group the symmetric group on n elements.

Exercise 3.3. Let a, b be non-negative integers. Let C ⊂ 𝔽^{a+b} be a generic set. Show that for some generic subset, A ⊂ 𝔽^{a} we have that for each α ∈ A, the set

{β ∈ 𝔽^{b} | (α, β) ∈ C}

is a generic subset of 𝔽^{b}. [Hint: Let x = (x_{1}, …, x_{a}) and y = (y_{1}, …, y_{b}) be vectors of a and b indeterminates (respectively). There is a polynomial f = f(x; y) = f(x_{1}, …, x_{a}; y_{1}, …, y_{b}) such that f(α; β) ≠ 0 implies that (α; β) ∈ C. It suffices to show that for some generic A ⊂ 𝔽^{a} we have that α ∈ A implies that g(y) = f(α; y) is not constant in y.]

Exercise 3.4. Let A ⊂ 𝔽^{n} for some infinite field, 𝔽, and integer n ≥ 0. Show that the following are equivalent:

(1) A is constructible; and

(2) A can be expressed as a finite statement using “and,” “or,” “not,” and membership in some Zariski open subsets of 𝔽^{n}.

Exercise 3.5. Show that if

f = f(x_{1}, …, x_{n}) ∈ \overline{𝔽}[x_{1}, …, x_{n}]

is a polynomial with coefficients in the algebraic closure of 𝔽, then the subset of 𝔽^{n} on which f vanishes is a Zariski closed subset of 𝔽^{n} (i.e., equals the subset of 𝔽^{n} on which some set, S, of polynomials with coefficients in 𝔽 vanish). [Hint: f’s coefficients lie in some finite extension of 𝔽, 𝔽′; 𝔽′ has a finite basis as a 𝔽-vector space, of size [𝔽′ : 𝔽]; express f in terms of this basis and 𝔽[x_{1}, …, x_{n}].]

Exercise 3.6. Conclude that if C is constructible in \overline{𝔽}^{n}, then C∩𝔽^{n} is constructible in 𝔽^{n}. [Hint: Use Exercises 3.4 and 3.5.]

4. More on Sheaves – Work in Progress!

In this section we will describe more about sheaves.

4.1. Morphisms of Sheaves.

Definition 4.1. 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 [sga72]).

4.2. Intuition on k-th Power Kernels. At this point we give some intuition as to how the sheaves K_{M}, used in the last section, arise. Later we give more details, but for now we give enough intuition so that the reader will have a basic idea of how to think of these sheaves.

For any étale bigraphs, L_{1}, L_{2}, we wish to show that

(4.1)  ρ(M_{1}) ≤ ρ(M_{2}),

where M_{1} = L_{1} ×_{B_{2}} L_{2}, and M_{2} is ρ(L_{1}) disjoint copies of L_{2}.

Homology and cohomology often involve “long exact sequences,” that look like, for example,

⋯ → H_{i}(A) → H_{i}(B) → H_{i}(C) → ⋯,

where H_{i} is an i-th homology group of some sort, and A, B, C form a “short exact sequence” of some sort. In such a sitution, if the homology groups are vector spaces over some field, then

dim(H_{i}(B)) ≤ dim(H_{i}(C))

provided that H_{i}(A) = 0.

It will turn out that in (4.1), in the very special (and trivial) case of L_{2} = G = Cayley(G; g_{1}, g_{2}) and L_{1} ⊂ G, ρ will act as the dimension of a homology group, and we will have a short exact sequence

0 → K_{M} → M_{1} → M_{2} → 0,

where now M_{2} is just ρ(L_{1}) copies of G and M_{1} is the disjoint union of L_{1}g over all g ∈ G. However, this short exact sequence does not exist as graphs, but rather when we view these graphs as sheaves over G, and ρ is defined for on a sheaf to be its maximum excess.

In a bit more detail, to each “digraph, K, over G,” i.e., each morphism of digraphs K → G, one can associate, in a natural way, a sheaf \underline{𝔽}_{K} on G whose maximum excess is ρ(K). This was done just after Definition 2.6 Furthermore, a disjoint union of graphs over G is associated to the direct sum of sheaves associated to the individual graphs over G. So to M_{2} is associated the sheaf

\underline{𝔽}_{M_{2}} = \underline{𝔽}^{ρ(L_{1})};

to M_{1} is associated

\underline{𝔽}_{M_{1}} = \underline{𝔽}_{L_{1}}G = ⨁_{g∈G} \underline{𝔽}_{L_{1}g};

and K_{M} is the kernel of the surjection of \underline{𝔽}_{M_{1}} → \underline{𝔽}_{M_{2}} determined by M in a natural way (and ρ has to be replaced by the maximum excess, to extend its definition to sheaves).

Once we establish that K_{M} has maximum excess zero for generic M’s of size ρ(L_{1}) × G, we will have established (4.1) in the trivial case of L_{2} = G, a Cayley graph, and L_{1} ⊂ G. This case is trivial because (4.1) follows from the fact that L_{1} ×_{B_{2}} G is isomorphic to |G| copies of L_{1}. Surprisingly, our comparatively difficult and unconventional proof of a trivial special case of the SHNC, using the sheaves K_{M}, turns out to easily imply the entire SHNC. This is shown in Theorem 3.4, although with appropriate sheaf technology this can be proven in a few lines (see [Fri11a, Fri11c]).

4.3. Exercises.

Exercise 4.1. Write an exercise.

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.

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

[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.

[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 complexity. 2005. http://www.math.ubc.ca/~jf, also

http://arxiv.org/abs/cs/0512008, to appear.

[Fri11a] Joel Friedman. Sheaves on graphs and a proof of the hanna neumann conjecture. April 2011. available at http://arxiv.org/pdf/1105.0129v1 and at

http://www.math.ubc.ca/~jf.

[Fri11b] Joel Friedman. Sheaves on graphs and their homological invariants. April 2011. available

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

[Fri11c] Joel Friedman. Sheaves on graphs, their homological invariants, and a proof of the hanna neumann conjecture. June 2011. available at http://arxiv.org/pdf/1105.0129v2 and

at http://www.math.ubc.ca/~jf.

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

[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.

[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.

[Min11a] Igor  Mineyev.  Groups,  graphs,  and  the  Hanna  Neu-
mann  Conjecture.  May  2011.  Preprint.  Available  at

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

[Min11b] Igor  Mineyev.  Submultiplicativity  and  the  Hanna  Neu-
mann  Conjecture.  May  2011.  Preprint.  Available  at

http://www.math.uiuc.edu/~mineyev/math/art/submult-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.

[sga72] 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.

[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.

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.

E-mail address: jf@cs.ubc.ca or jf@math.ubc.ca