Abelian Girth and Gapped SheavesbyAlice IzsakB.Sc., Harvey Mudd College, 2007M.Sc., The University of British Columbia, 2009A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)December 2015c© Alice Izsak 2015AbstractThe girth of a graph is the length of the shortest cycle in a graph, and theabelian girth of a graph is the girth of the graph’s universal abelian coveringgraph. We denote the abelian girth of a graph G as Abl(G) and show thatfor d-regular graphs on n vertices with d constant and n growing we haveAbl(G) ≤ 6 logd−1 n+ on(1).This can be seen as a version of the Moore bound for abelian girth. We alsoprove Girth(G) ≤ Abl(G)/3, which implies that any multiplicative improve-ment to the abelian girth Moore bound would also improve the standardMoore bound.Sheaves on graphs and two of their homological invariants, the maximumexcess and the first twisted Betti number, were used in the proof of theHanna Neumann Conjecture from algebra and may be of use in provingseveral related unresolved conjectures. These conjectures can be proven ifcertain sheaves called ρ-kernels have vanishing maximum excess. Ungappedsheaves have maximum excess equal to the first twisted Betti number, andit is easy to compute the maximum excess of a given sheaf in the case thatthe sheaf is not gapped. For general sheaves though, there is no knownway of computing the maximum excess in polynomial time. We give severalconditions that gapped sheaves must satisfy. These conditions include that agapped sheaf must have edge dimension at least as large as the abelian girthof the underlying graph. The ρ-kernels are subsheaves of constant sheaves.We prove that gapped subsheaves of constant sheaves exist, implying thatfinding maximum excess of some ρ-kernels may be computationally difficult.iiPrefaceThis dissertation is unpublished research done in collaboration with JoelFriedman, Lior Silberman and myself with the bulk of the research donein regular meetings between Joel Friedman and myself. The scope of theproject was planned by Joel Freidman and myself. Though the vast major-ity of the research originates from discussions between myself and Friedmanwith Silberman joining occasionally, some results I first discovered on myown. These include the chain decomposition described in Chapter 9, theminimal gapped sheaves on the figure-eight graph and the theta graph de-scribed in Chapter 11 and the existence of the gapped subconstant sheafalso described in Chapter 11, though computations verifying the sheaf wasgapped were done by myself and Friedman.I wrote the first drafts of every chapter except Chapters 7 and 8 whichwere written by Joel Friedman and subsequently edited by the author.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . vi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 Graph Terminology . . . . . . . . . . . . . . . . . . . . . . . 62.2 Our Fundamental Lemma . . . . . . . . . . . . . . . . . . . . 72.3 Main Results on Abelian Girth . . . . . . . . . . . . . . . . . 83 Proof of Theorem 2.6 . . . . . . . . . . . . . . . . . . . . . . . 104 Proofs of the Fundamental Lemma and Theorem 2.5 . . . 155 Abelian Girth of the LPS Expanders . . . . . . . . . . . . . 186 k-Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . 216.1 Oriented Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 216.2 k-Independence . . . . . . . . . . . . . . . . . . . . . . . . . 237 Sheaves on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 257.1 Sheaves and Homology . . . . . . . . . . . . . . . . . . . . . 257.2 Twisted Homology . . . . . . . . . . . . . . . . . . . . . . . . 277.3 Maximum Excess of a Sheaf . . . . . . . . . . . . . . . . . . 297.4 Main Theorems . . . . . . . . . . . . . . . . . . . . . . . . . 31ivTable of Contents8 Remarks on Gapped Sheaves . . . . . . . . . . . . . . . . . . 348.1 Minimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348.2 Minimal Elements and Stability . . . . . . . . . . . . . . . . 358.3 Edge Subsheaf Closed Collections . . . . . . . . . . . . . . . 378.4 Vertex Quotient Closed Collections . . . . . . . . . . . . . . 388.5 Edge Quotient Closed Collections and Injectivity . . . . . . . 408.6 The Proof of Theorem 8.9 . . . . . . . . . . . . . . . . . . . 419 The Twist Trick and Edge Detachment . . . . . . . . . . . . 439.1 The Fundamental “Twist Trick” Lemma . . . . . . . . . . . 439.2 Edge Detachment . . . . . . . . . . . . . . . . . . . . . . . . 459.3 Alternate Proof of the Twist Trick . . . . . . . . . . . . . . . 489.4 The Chain Decomposition . . . . . . . . . . . . . . . . . . . 509.5 The Second Twist Trick . . . . . . . . . . . . . . . . . . . . . 5910 Homotopy Simplifications and Vector Bundles . . . . . . . 6210.1 Some Homotopy Operations . . . . . . . . . . . . . . . . . . 6210.2 A Twisted Homotopy Operation . . . . . . . . . . . . . . . . 6510.3 Example: Vector Bundles . . . . . . . . . . . . . . . . . . . . 6610.4 A High Road to Homotopy . . . . . . . . . . . . . . . . . . . 6710.5 Contracting and Subdividing Gapped Sheaves . . . . . . . . 6911 Proofs of Theorems 7.17 and 7.18 . . . . . . . . . . . . . . . 7311.1 Three Minimal Gapped Sheaves . . . . . . . . . . . . . . . . 7311.2 Proof of Theorem 7.17 . . . . . . . . . . . . . . . . . . . . . 7511.3 Proof of Theorem 7.18 . . . . . . . . . . . . . . . . . . . . . 7512 Subquotients, Submodularity and Supermodularity . . . . 7912.1 Subquotients of a Sheaf . . . . . . . . . . . . . . . . . . . . . 7912.2 Simplifications for Stable Sheaves . . . . . . . . . . . . . . . 8012.3 Single Vertex Graphs and Proof of Corollary 7.19 . . . . . . 8012.4 Submodularity and Supermodularity . . . . . . . . . . . . . 8213 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86vAcknowledgementsJoel Friedman’s guidance, patience and valuable insights have propelled methrough my graduate career. I could not have hoped for a more supportivesupervisor, and his breadth of knowledge and eagerness to attack mathemat-ical problems in unique ways have been constant inspirations. I also mustthank Lior Silberman for his help answering many questions throughout thisresearch and his extensive help in the editing process. I have learned muchabout how to write mathematical documents well from Lior. I also need toacknowledge Omer Angel, the other member of my supervisory committee,for helping oversee the research presented here. I should also mention thatthis research was supported by a UBC Four Year Fellowship.I am beyond grateful for my family’s love and support over the lastfew years. Thank you Nina, Benjamin, Ariela, Leon and Celine Izsak. Ialso send my heartfelt gratitude to colleagues and friends who have helpedme in innumerable ways throughout my graduate career, particularly CraigWeidert, Jaimie Veale, Julieta Martinez, Herbie Carvajal, Samuel Rudolph,Stephen Jones, Julia Fornaca, and Jess Latimer. Finally, my love goes outto my partner Rachael Gillese who has stood with me through so much andbrought so much happiness in my life. Thank you, thank you, thank you.viChapter 1IntroductionThis dissertation is divided into two main parts. In the first, we discuss agraph invariant called the abelian girth of a graph, which Friedman intro-duced in his proof of the the Hanna Neumann Conjecture (or HNC) [18].In the second part we discuss sheaves on graphs and their homological in-variants. Though these two parts are fairly independent from one another,they are tied together by a main result of this dissertation which shows thatwhat we call a minimally gapped sheaf on a graph has total dimension equalto the abelian girth of the underlying graph.In the first part of this dissertation, we show several relations betweenthe abelian girth of the graph and the standard girth of a graph as wellas between the abelian girth and the volume bound on girth known as theMoore bound. Specifically, we give some evidence to show that boundingthe abelian girth from above is a possible approach to improving the Moorebound. Let us make this more precise.The girth of a graph is the length of the shortest non-trivial cycle in thegraph. If Gn,d is any d-regular graph on n vertices, it is known that for fixedd and large n we haveGirth(Gn,d) ≤ 2 logd−1 n+ on(1). (1.1)We are interested in knowing if the factor of 2 can be improved upon. Thisbound follows from the Moore bound (see [12]); although the Moore boundfor regular graphs is very easy to prove, there has been only slight im-provements to it in the last 50 years—only an additive constant of one ortwo—and, in particular, the factor of 2 in (1.1) is the best factor knownto date. Graphs of large girth have numerous applications ([2, 28, 33]) andmuch has been written on the girth and the Moore bound (see [3]).The abelian girth of a graph, G, denoted Abl(G), is the girth of itsuniversal abelian cover, or equivalently the shortest length of a non-trivial,closed, non-backtracking walk that traverses each edge the same number oftimes in each direction. The abelian girth arises in sheaf theory on graphsand the first proof of the Hanna Neumann Conjecture [18]; furthermore, inthe second portion of this dissertation we show the abelian girth is strongly1Chapter 1. Introductionrelated to what we call minimal gapped sheaves on a graph. First though,we show that there is an analogue of the Moore bound for the abelian girth,and that improving this analogue would improve the Moore bound. We alsoprovide evidence that such an improvement may be possible.Specifically, we show thatgirth(G) ≤ Abl(G)/3,for any graph, G. Second, we show that there is an argument analogous tothe Moore bound that shows that for fixed d we haveAbl(Gn,d) ≤ 6 logd−1 n+ on(1) (1.2)for any d-regular graph on n vertices, Gn,d; we remark that the proof of thistheorem is not as immediate as that of the Moore bound. It follows thatany improvement to the factor of 6 in (1.2) would give an improvement tothe factor of 2 in (1.1).Ideally we would show that all known explicit constructions of familiesof d-regular graphs have abelian girth at most c logd−1 n for some c < 6. Inthis paper, we will focus on the only family of d-regular graphs with d fixedwhich has girth greater than logd−1 n. It is known that the factor of 2 in(1.1) cannot be less than 4/3, at least for certain d: indeed, [27] constructsgraphs, Xp,q, for primes p, q ≡ 1 (mod 4), that are d = p + 1 regular onn = q(q2 + 1) vertices for whichgirth(Xp,q) = (4/3) logd−1 n+ on(1)for fixed d = p+ 1 and large n = q(q2 + 1). Furthermore there are no knownfamilies of graphs which improve on the above 4/3; in fact, for general d,all known constructions of graphs have girth at most logd−1 n+ on(1). Thisbound is attained for a family of graphs constructed by choosing a randomgraph and slightly modifying it [11, 13]. To show that it is plausible toimprove on the factor of 6 in (1.2), we will show thatAbl(Xp,q) ≤ (16/3) logd−1 n+ on(1)which suggests that there is room for the factor of 6 to decrease. We con-jecture that the 16/3 can be replaced with 4, for reasons we shall explainlater. We are unaware of any other graph constructions in the literature forwhich one can improve upon the 16/3 above.To prove (1), we prove a fundamental lemma that suggests many possiblegeneralizations of the above discussion of abelian girth and the Moore bound.2Chapter 1. IntroductionThe girth of a graph is smallest positive length of a cycle that embeds in thegraph. Our fundamental lemma states that the abelian girth is the smallestnumber of edges in a graph of Euler characteristic −1 that embeds in thegraph provided that we weight the edges appropriately: namely, we counteach edge twice, except in “barbell graphs” we count each edge in the barfour times.Both girth and abelian girth can be viewed as linear algebraic invariantsof graphs; indeed, girth is often studied as a property of the adjacency matrixof the graph (see, for example, [3]), and the abelian girth relates to sheaves ofvector spaces over the graph. So our fundamental lemma also suggests thatthere could be other such girth-type invariants, both (1) arising as linearalgebraically from the graphs, and (2) satisfying inequalities analogous toEquation (1).The rest of this paper is organized as follows. In Section 2 we givesome precise definitions and state our main theorems. In Section 3 weprove Equation (1.2). In Section 4 we prove the fundamental lemma aswell as Equation (1) which follows quickly from the fundamental lemma.In Section 5 we describe the graphs Xp,q from [27] and show that they obeyEquation (1).The next part of this dissertation studies sheaves on graphs and theirhomological invariants. One invariant we study is the maximum excess of asheaf. The maximum excess has a definition with no reference to homologytheory, but it is also arises as a limit of Betti numbers akin to the L2 Bettinumbers studied by Atiyah [4] and has a long/short exact sequence theory.The maximum excess originally was discussed in Friedman’s proof of theHNC [18]. The reason maximum excess is necessary for Friedman’s proofand a reason we study it in this paper is that it generalizes the notion ofreduced cyclicity, a graph invariant from the graph theoretic reformulationof the HNC (see [21], [22], [30], [20], [7], [32], [29], [14].) In particular, themaximum excess of a sheaf on a graph is equivalent to the reduced cyclicityof that graph if the sheaf is what we call a structure sheaf.Our study of the maximum excess is partially motivated by our desireto prove certain conjectures related to the HNC (see [23], [24], [9], [10] [34].)These are conjectures on the rank of the intersection of two subgroups froma free product of groups. In Friedman’s proof, he shows that the HNC is trueif certain sheaves called ρ-kernels have vanishing maximum excess. Similarlythese other conjectures can be verified if one can prove that certain other ρ-kernels also have vanishing maximum excess. Unfortunately, the techniquesfrom Friedman’s proof of the HNC are alone not sufficient in proving theother conjectures.3Chapter 1. IntroductionA drawback of using the maximum excess is that there is no known wayto compute the maximum excess of a sheaf on a graph in time polynomial inthe total dimension of the sheaf. Friedman’s proof also defines the twistedhomology groups and twisted Betti numbers of a sheaf. The first twistedBetti number is easy to compute, bounds the maximum excess from above,and is in many cases equal to the maximum excess. We refer to sheaves asgapped if the maximum excess and first twisted Betti number are not equal.If a sheaf is known to not be gapped, the maximum excess is easy to computeby a computation of the first twisted Betti number. In this dissertation wegive several results describing necessary properties of gapped sheaves.We describe sheaves on graphs as a collection of vector spaces indexedalong the vertices and edges of the graph, along some linear maps from theedge spaces to the vertex spaces that we call restriction maps. A constantsheaf is sheaf where all of those vector spaces are identical and the restric-tion maps are all the identity, and a subconstant sheaf is any subsheaf of aconstant sheaf. One of the more surprising results of my dissertation is thatthere exists gapped subconstant sheaves. Since the ρ-kernels from the con-jectures related to the HNC are subconstant sheaves, any attempted proofof conjectures related to the HNC may need to take into account that thefirst twisted Betti number on these sheaves could be nonzero even thoughthe maximum excess vanishes on that sheaf. In related work (to appear) wedo find ρ-kernels that correspond to a conjecture in [9] that are gapped.Not only do gapped subconstant sheaves exist, but there are gappedsubconstant sheaves on a graph that are only two vertices and multiple edgesbut no self loops. This implies an interesting, purely linear algebraic result.The usual notion of linear independence of vectors in a vector space canbe stated in many equivalent ways. In quiver representation theory, therearises a notion of what we call linear k-indepedence, which is defined for everyinteger k, and which reduces to the usual linear indepedence for k = 1 [6].The notion of linear 2-independence defines a remarkable type of sheaf on agraph which we call a pseudobundle. Unfortunately, linear k-independence,for k ≥ 2, is difficult to check directly. However, there is a related notion,which we call tensorial k-independence, which is easier to verify and whichimmediately implies linear k-independence. Using the existence of gappedsubconstant sheaves on two vertices and no self loops, we prove though thattensorial k-dependence does not imply linear k-independence.We also find a connection between gapped sheaves on a graph and theabelian girth of the underlying graph. We prove that the abelian girth ona graph is equal to the minimum of the total dimensions of the gappedsheaves on the graph. This result can also be viewed as an improvement on4Chapter 1. IntroductionTheorem 1.10 from [18], which states that if a lift of a sheaf on a graph hasa sufficiently large degree dependent on the abelian girth of the graph , thenthe pullback sheaf is not gapped. Our result implies that in the case thatthe lift is just the identity map, then we can remove the factor of 2 fromFriedman’s Theorem 1.10.Though our research is mainly motivated by our desire to prove con-jectures related to the HNC, there are other reasons we are interested inanswering fundamental questions about sheaves on graphs. A sheaf on agraph can be viewed as a generalization of the incidence matrix of the graph;indeed the structure sheaf of a graph has the same incident matrix as theunderlying graph. It follows that sheaves on graphs allow a generalization ofstandard algebraic graph theory. Tools such as long/short exact sequencescan allow for new graph theoretic inequalities. Also, any morphism betweengraphs can be represented by a morphism on sheaves on graphs, but thereare morphisms between sheaves on graphs that do not correspond to anymorphism between graphs. These “new morphisms” are necessary in Fried-man’s proof of the HNC but may also be useful in studying other aspects ofgraph theory.Section 6 introduces linear and tensorial 2-independence in terms of onlylinear algebra and gives a counterexample to the two being equivalent. Sec-tion 7 gives an introduction to sheaf theory on graphs, twisted Betti numbersand maximum excess. At the end of the chapter, we also explicitly state themain results of the paper. In Section 8 we define minimal gapped sheavesand establish several properties of minimal gapped sheaves. In Section 9 weprove what we call the twist trick lemma. This lemma allows us to give lowerbounds on the edge dimension of minimally gapped sheaves. Section 10 de-fines homotopy preserving operations that will allow us to transform a sheafon a graph while not changing the gap of the sheaf. In Chapter 11 we in-troduce three minimally gapped sheaves which then allows us to prove thatthe abelian girth of a graph is the minimal edge dimension of a gappedsheaf on that graph. We also use one of those gapped sheaves to constructthe counterexample to linear and tensorial 2-independence being equivalent.Chapter 12 discusses a few results not necessary in proving the main the-orems of this dissertation but are still of interest, in particular boundingthe edge dimension of gapped subquotient sheaves thus giving a bound forgapped subconstant sheaves.5Chapter 2Main ResultsIn this section we fix some terminology regarding graphs and formally statethe main results of the first part of this dissertation.2.1 Graph TerminologyThis entire subsection consists of definitions used throughout this paper;they are more or less standard.By a graph we shall mean a quadruple G = (VG, EG, tG, hG) where VGand EG are sets (the “vertices” and “edges”, respectively) and tG, hG : EG →VG are maps (the “tail” and “head” of each edge, respectively). The Eulercharacteristic of G isχ(G) = |VG| − |EG|,where | · | denotes the cardinality, provided that G is finite, i.e., that |VG|and |EG| are finite. We define the unoriented edge set of G to beUG = EG × {+,−},and we extend hG and tG to be functions on UG such that for e ∈ EGhG(e,+) = tG(e,−) = hG(e), tG(e,+) = hG(e,−) = tG(e);for e ∈ EG we say that (e,+) and (e,−) are inverses of each other. Wedenote the inverse of u ∈ UG by u−1. A walk of length m in G is a sequenceof unoriented edgesw = (u1, . . . , um)such that the head of ui is the tail of ui+1 for i = 1, . . . ,m − 1; we definethe vertices tG(u1) and hG(um) to be the starting and terminating verticesof w, jointly the endpoints of w, and the length of w to be m, denoted l(w);we say that w is closed if its two endpoints are the same vertex; we referto the edges of w as the e ∈ EG such that at least one of (e,+), (e,−) isan unoriented edge of w; we say that w is non-backtracking if there is noi = 1, . . . ,m − 1 for which u−1i = ui+1; we say that w is strongly closed,62.2. Our Fundamental Lemmanon-backtracking if w is closed and non-backtracking, and u1, um are notinverses of each other; we say that w is a path (respectively, cycle) if w isnon-backtracking with distinct endpoints (respectively strongly closed, non-backtracking), and each edge e ∈ EG appears at most once in w (i.e. (e,+)and (e,−) appears at most once in u1, . . . , um). The inverse of w is definedas the walkw−1 = (u−1m , . . . , u−11 ).Given a walk w = (u1, . . . , um) and a walk k = (t1, . . . , tn) such that theterminating vertex of w is the starting vertex of k, we define the product wkto be the walk (u1, . . . , um, t1, . . . , tn). We say that a walk w as above joinsits two endpoints. We say that G is connected if any two of its vertices arejoined by some walk in G.As usual, a morphism of graphs, f : G → H, is a pair f = (fV , fE)of maps fV : VG → VH and fE : EG → EH such that tH ◦ fE = fV ◦ tGand hH ◦ fE = fV ◦ hG. We often drop the subscripts from fV and fE .The set of morphisms will be denoted Mor(G,H). Thus morphisms arehomomorphisms of the underlying undirected graphs which preserve theorientation.As usual, the girth of a graph is the infimum of the lengths of closed,non-backtracking walks in the graph; this length is necessarily positive byour conventions above. (In the literature one often allows for walks of lengthzero, which we do not consider here.)2.2 Our Fundamental LemmaIn this subsection we discuss our main results.Definition 2.1. The abelian girth of a graph, G, denoted Abl(G), is theminimum m ≥ 1 such that there is a closed, non-backtracking walkw = (u1, . . . , um)such that each edge is traversed the same number of times in w in bothdirections, i.e., for each e ∈ EG the edge (e,+) appears the same number oftimes among u1, . . . , um as does (e,−).The abelian girth is the same as the girth of the universal abelian coverof G; see [18]. Given a walk w and an e ∈ EG, if (e,+) appears i+ timesand (e,−) appears i− times we say e appears a net i+ − i− times in w. Werefer to a walk as edge neutral if every edge appears a net 0 times in it.72.3. Main Results on Abelian GirthWe begin with a fundamental lemma. We remind the reader that ourconventions insists that cycles and paths are of positive length.Definition 2.2. Let G be a connected graph of Euler characteristic −1without leaves, i.e., without vertices of degree one. We say that G is1. a figure-eight graph if G consists of two cycles, mutually edge disjoint,sharing the same endpoint;2. a barbell graph if G consists of two cycles, w1, w2, and one path b, allmutually edge disjoint, such that b joins the endpoints of w1 and w2;we refer to b as the bar of G;3. a theta graph if G consists of two vertices joined by three paths thatare mutually edge disjoint.It is well known that the above three cases classifies all connected graphsof Euler characteristic −1 without leaves (see, for example, [26].)Definition 2.3. Let G be a connected graph of Euler characteristic −1without leaves. We define the abelian length of G, denoted lAbl(G), to betwice its number of edges except that each edge of its bar (if G is a figure-eight graph) is counted four times.We call the following lemma the Fundamental Lemma, as it gives analternative definition of the abelian girth that we use in several proofs.Lemma 2.4 (Fundamental Lemma). For any graph, G, we haveAbl(G) = minG′⊂GlAbl(G′)taken over all subgraphs, G′, that are connected, of Euler characteristic −1,and without leaves. If no such G′ exist, then Abl(G) =∞. Indeed, there areno closed non-backtracking walks that traverse each edge the same numberof times in both directions.2.3 Main Results on Abelian GirthNow we can easily state the other main results of the first part of thisdissertation.Theorem 2.5. For any graph we haveGirth(G) ≤ Abl(G)/3.82.3. Main Results on Abelian GirthThis theorem is an easy corollary of Lemma 2.4.Theorem 2.6. For any fixed d, let Gn,d be any d-regular graph on n vertices.Then for large n we haveAbl(G) ≤ 6 logd−1 n+ on(1).Our last theorem uses the LPS graphs Xp,q [27] whose definition we savefor Section 5.Theorem 2.7. Let p, q ≡ 1 (mod 4) be prime with (q/p) = 1. The graphXp,q of [27] of our Definition 5.1 has degree d = p + 1 and n = q(q2 + 1),and for fixed p and large q (i.e., fixed d and large n) we haveAbl(Xp,q) ≤ (16/3) logd−1 n+ on(1).9Chapter 3Proof of Theorem 2.6In this section we prove Theorem 2.6, but first we remind the reader of thestatement of the theorem.Theorem 2.6. For any fixed d, let Gn,d be any d-regular graph on n vertices.Then for large n we haveAbl(G) ≤ 6 logd−1 n+ on(1).In order prove this theorem, we begin by stating a few well known factsregarding free groups and graphs.Lemma 3.1. Let G be a finite graph. Then the fundamental group, pi1(G, u),of homotopy classes of closed walks in G about u for any u ∈ VG is isomor-phic to a free group on a finite set of generators.The contiguous appearance of an edge and its inverse in a walk is calleda reversal. Each walk, w, can be reduced by successively discarding itsreversals; the walk obtained is the reduction of w and is independent of thechoice of pairs to reduce; the reduction therefore contains no reversals and isnon-backtracking. We use the notation red(w) for the reduction of w. Notethat red(w−1) = red(w)−1 for any walk w since the portion of a walk thatis removed by reduction remain the same when we take the inverse of thatwalk.Definition 3.2. In each element ω of pi1(G, u), there exists one uniquenon-backtracking walk in G; any walk in ω reduces to that unique non-backtracking walk. By the length of ω, denoted |ω|, we mean the length ofthe unique non-backtracking walk in ω. Note this is not length with respectto a set of generators of pi1(G, u). Similarly, even though closed walks aremembers of homotopy classes in the fundamental group, when we refer to thelength of a walk or the reduction of a walk w we mean length and reductionas defined earlier and not with respect to a set of generators for a free group.10Chapter 3. Proof of Theorem 2.6The following fact is well known. For ease of reading we provide a proof,for which we thank Seirius on Stackexchange1.Lemma 3.3. Let F be a free group and let α and β be two elements of Fthat commute with each other. Then there exists ω ∈ F such that α = ωmand β = ωm′for m,m′ ∈ Z.Proof. By the Nielsen-Schreier theorem, the subgroup that α, β generate isa free group. And yet, any two elements of this subgroup commute, andhence this subgroup cannot be free and rank more than one. Hence thissubgroup is generated by some ω ∈ F , and the conclusion follows.For any closed walk w, we use the notation [w] for the homotopy class inpi1(G, u) that has w as a representative. Suppose a and b are closed walks and[a] and [b] commute in pi1(G, u). Note that equality in the previous lemmais with regards to pi1(G, u), meaning an equality of homotopy classes but notnecessarily walks. Reducing all the elements of a homotopy class gives oneunique walk though. So since [a] and [b] commute, we have red(a) = red(wm)and red(b) = red(wm′) for m,m′ ∈ Z and w a closed walk. These equalitiesmay not exist without the reductions. We may assume w is reduced, sincered(wm) = red(red(w)m).The following lemma is also well known and easy.Lemma 3.4. Let w be a closed nontrivial non-backtracking walk in a graph.Then if for integers m,m′ we have that the length of red(wm) equals that ofred(wm′), then m = ±m′.Proof. Let y be a maximal length walk such that w = yxy−1 for some walkx. Then it is easy to check that for m 6= 0 the length of red(wm) withrespect to S is precisely2|y|+ |m||x|.Proof of Theorem 2.6. Fix any vertex, v ∈ VG. Then for any integer h ≥ 1,there are d(d − 1)h−1 non-backtracking walks of length h from v. So let hbe the smallest integer for whichd(d− 1)h−1 ≥ 2n+ 1;1See http://math.stackexchange.com/questions/213576/in-a-free-group-two-elements-commute-if-and-only-if-they-are-powers-of-a-common11Chapter 3. Proof of Theorem 2.6then, by the pigeon hole principle, there are three distinct non-backtrackingwalks, a, b, c, in G beginning in v and terminating in the same vertex u(which may or may not equal v). We remark thath =(1 + on(1))logd−1 n.Hence, to prove the theorem it suffices to show that we haveAbl(G) ≤ 6h. (3.1)The rough idea is simple. We break the analysis into two cases: u = vand u 6= v. In either case we define new walk, d, based on a, b, c such that (1)the length of d is 4h or 6h (in the respective two cases), (2) each edge of EGappears a net 0 times in d, but (3) d is not necessarily non-backtracking. Themain work is to show that d does not reduce to the empty word. Discardinga consecutive pair of an (unoriented) edge of d and its opposite retainsthe property that each edge is traversed the same number of times in eachdirection. Hence if d is reduced to a non-empty, non-backtracking walk, d′,then d′ is edge neutral, and soAbl(G) ≤ 6h.Let us describe d as above. If u = v, then at least two of a, b, c are notinverses of each other; if a, b are such walks, then we set d = aba−1b−1. Thiswalk is of length 4h. If u 6= v, then we set d to d = ab−1ca−1bc−1, which isa walk of length 6h. For any e ∈ EG, if e appears a net k times in a walkw then e appears a net −k times in the walk w−1. Thus d in either case isedge neutral.It remains to show that d reduces to a non-empty non-backtracking walk.The case u = v and d = aba−1b−1 where a and b (are distinct and) arenot inverses of each other is relatively easy. If d reduces to the empty worde and if α = [a], β = [b] and δ = [d] then δ = [e] = [α, β]comm where [ , ]commdenotes the commutator. So α and β commute as elements of pi1(G, u).Hence, by Lemma 3.3, and since pi1(G, u) is a free group, it follows thata = red(wm) and b = red(wm′) for some closed walk w with w 6= 1; butthen by Lemma 3.4, since a and b have the same length, we have m = ±m′,which contradicts the fact that a and b are distinct and not inverses of eachother.Now suppose u 6= v. We remark that as elements of pi1(G, u) we haved = ab−1cb−1ba−1bc−1 = [ab−1, cb−1].12Chapter 3. Proof of Theorem 2.6Let δ = [d], α = [ab−1] and γ = [cb−1] and let e be the trivial walk. So if d ∈[e], we have that 1 = δ = [α, γ]comm and so [ab−1] and [cb−1] commute in thefundamental group. Hence red(ab−1) = red(wm) and red(cb−1) = red(wm′)for some closed non-backtracking walk w. Let w = yxy−1 with x a closednon-backtracking walk and y a walk of maximal length; then (1) x 6= 1 asthat would imply a = b, (2) the first and last edges of x are not inverses ofeach other, and (3) red(wm) = yxmy−1.Next we want to make some remarks on ab−1 and wm based on the factthat red(ab−1) = red(wm); we will later repeat similar remarks for cb−1 andwm′based on the fact that red(cb−1) = red(wm′). Notea = red(ab−1b) = red(red(ab−1)b) = red(red(wm)b) = red(wmb)as reductions are independent of the order in which we reduce portions ofthe word.Let p be the maximal prefix of b that is a suffix of red(wm) = yxmy−1(a priori p could be as large as the shorter of yxy−1 and b); sincea = red(wmb),we have|a| = 2|y|+ |m| |x|+ |b| − 2|p|.But by assumption |a| = |b|, and hence2|y|+ |m| |x| = 2|p|.It follows that|p| = |y|+ |m| |x|/2 > |y|, (3.2)since x 6= 1 and m 6= 0. Since |p| > |y| and p is a suffix of wm = yxmy−1, itfollows that p−1 begins with y and contains at least one more edge; hencep = yx1 where |x1| > 0 and the first edge of x1 is the inverse of the last edgeof xm.However, since red(cb−1) = red(wm′), the very same arguments showthat if p′ is defined analogously, i.e., as the maximal prefix of b that is asuffix of red(wm′), then p′ = yx′1 where |x′1| > 0 and the first letter of x′1 isthe inverse of the last letter of xm′. But since both p and p′ are both prefixesof b, we must have that m and m′ have the same sign: for if, say, m > 0 andm′ < 0, then the last edge of xm or it’s orientation is different than the lastedge of xm′by the maximality of y in the equation w = yxy−1.Hencea = red(wmb), c = red(wm′b),13Chapter 3. Proof of Theorem 2.6a, b, c have the same length, and without loss of generality we may assumem > m′ > 0. But then Equation (3.2) and its analog for cb−1 = wm′ showthatm = (|p| − |y|)/|x|, and m′ = (|p′| − |y|)/|x|.It follows that |p| > |p′|. Since both p and p′ are prefixes of b, we have thatp′ is a prefix of p. But p′ is the maximal suffix of wm′ that is also a prefixof b; since wm′is also a suffix of wm it follows that p′ = wm′ (otherwise pcould not be larger than p′). But in this case|c| = |b| − |p′| < |b|,which contradicts that fact that |c| = |b|.14Chapter 4Proofs of the FundamentalLemma and Theorem 2.5Lemma 2.4 (Fundamental Lemma). For any graph, G, we haveAbl(G) = minG′⊂GlAbl(G′)taken over all subgraphs, G′, that are connected, of Euler characteristic −1,and without leaves. If no such G′ exist, then Abl(G) =∞. Indeed, there areno closed non-backtracking walks that traverse each edge the same numberof times in both directions.Proof of the Fundamental Lemma. Let w be an edge neutral, closed, non-backtracking walk of minimal (positive) length, and let B be the subgraphof G of vertices and edges that occur in w. Then B is a connected subgraphof G such that each vertex has degree at least two. If the degree of everyvertex in B is strictly two, then B would be a cycle, which is impossiblesince any non-backtracing walk in a cycle traverses edges in at most onedirection. Hence at least some vertex of B is strictly greater than two;hence the formulaχ(B) =∑v∈VB(2− deg(v))shows that χ(B) ≥ −1.Now w traverses each edge of B at least once in each direction, and hencel(w) ≥ 2 |EB|.We claim that if w is a figure-eight graph or a theta graph, then there is anon-backtracking walk on B traversing each edge exactly twice, and hencel(w) = lAbl(B).We claim that this formula also holds if B is a barbell graph; indeed,it suffices to show that the edges of the bar have to be traversed at least15Chapter 4. Proofs of the Fundamental Lemma and Theorem 2.5four times in w, since there is a closed, non-backtracking walk on a barbellgraph that traverses each edge of the bar four times and the other edgestwice. Since each edge is traversed an even number of times in w, it sufficesto show that w cannot traverse an edge of the bar twice. Let e be anedge of the bar; by cyclically shifting w, we may assume that w begins bytraversing (e,+). Then w wraps some number of times around the cycle inthis direction of e, and eventually traverses (e,−), wrapping some numberof times around the other cycle and returning to the tail of e. At this pointeach edge in the cycle has been traversed in only one direction, so that wmust traverse (e,+) again. Hence e cannot be traversed only twice. Thisestablishesl(w) = lAbl(B)in the case where B is a barbell graph.It suffices to show that for, w, as above, there is another walk, w′ whichis edge neutral and closed non-backtracking for which l(w) ≥ l(w′) and thegraph corresponding to w′ is a subgraph of B with Euler characteristic −1.So assume, for the sake of contradiction, that this fails to hold.First we claim that B cannot contain a theta or figure-eight graph B′;indeedl(w) ≥ 2|EB|;but walking along the theta or figure-eight graph, there is a balanced, closednon-backtracking walk of length 2|EB′ |; but χ(B′) = −1, so B′ is a strictsubgraph of the connected graph, B, and hence 2|EB′ | ≤ 2|EB|, contradict-ing the minimality of w.Second, we claim that B cannot contain an edge, e such that when weremove e, B is disconnected; indeed, assume otherwise, and extend e in bothdirections until it meets vertices v1 and v2 whose degrees are greater thantwo; let p denote the walk from v1 to v2 through e. The same argumentused for the case where B is a barbell shows that (1) the path p is traversedin W four times, and (2) each endpoint of p is traversed in two cycles aboutthat endpoint that do not meet p. If c1 is the shortest cycle about v1 thatdoes not meet p, and similarly for c2 and v2, then|W | ≥ lAbl(B′),where B′ is the subgraph of B consisting of p, c1, and c2. But B′ is just abarbell graph.Third, we claim that either the first or second claim must be contra-dicted; this will complete the proof of the lemma. Indeed, B is not a tree,16Chapter 4. Proofs of the Fundamental Lemma and Theorem 2.5and therefore must contain a cycle, C. The cycle must contain a vertex, v,of degree at least three, or else B would consist entirely of C, which wouldthen have Euler characteristic zero. Let e be any edge not in C that is in-cident upon v, and let u be the other endpoint of e. Since removing e doesnot disconnect B, there must be a walk from u to a vertex of C that doesnot contain e; let p be such a walk of minimal length. Then p begins in uand is a beaded path to a vertex of c. But then the path e followed by pis disjoint from C and joins v to another vertex of C, which yields either afigure-eight graph (if p terminates in v) or a theta graph (if p terminates ina vertex of C that is not v).Hence the first claim is violated.We now prove Theorem 2.5 as a consequence of the Fundamental Lemma,but first we recall the statement of the theorem.Theorem 2.5. For any graph we haveGirth(G) ≤ Abl(G)/3.Proof of Theorem 2.5. Let G′ ∈ C be the subgraph of G of minimal abelianlength. If G′ is homeomorphic to the barbell graph, then Abl(G) ≥ 4 +4 Girth(G) since each of the two simple cycles in G′ is at least as long asthe girth. Similarly, Abl(G) ≥ 4 Girth(G) if G′ is homeomorphic to a figure-eight graph. In the case of a theta graph, we have two vertices u and v inG′ of degree 3 and three simple paths from u to v. Let the lengths of thesimple path be l, m and n. Then l + m,m + n, n + l ≥ Girth(G). Addingthese inequalities gives3 Girth(G) ≤ 2(l +m+ n) = 2|EG′ | = Abl(G).17Chapter 5Abelian Girth of the LPSExpandersThe Ramanujan graphs of Lubotzky, Phillips and Sarnak [27] are an infinitefamily of graphs with the largest known asymptotic girth. As mentionedearlier, these are graphs Xp,q, for primes p, q ≡ 1 (mod 4), that are d = p+1regular on n = q(q2 + 1) vertices for whichgirth(Xp,q) = (4/3) logd−1 n+ on(1).This immediately leads to the bound on abelian girthAbl(Xp,q) ≥ 4 logd−1 n+ on(1).We will describe these Ramanujan graphs and obtain an upper bound ontheir abelian girth in order to show that their abelian girth isn’t so largethat it would be impossible to improve Theorem 2.6.Definition 5.1. Let p and q be unequal primes congruent to 1 mod 4 with(p/q) = −1 and q > √p. The integral quaternions, denoted H(Z), are givenbyH(Z) = {α = α0 + α1i + α2j + α3k|aj ∈ Z}.We denote the conjugate of α by α and define N(α) = αα. Let S be theset of all α in H(Z) satisfying N(α) = p, α ≡ 1(mod2) and α0 ≥ 0. It canbe shown that |S| = p + 1. Define Λ′(2) as the set of α ∈ H(Z) such thatN(α) = pv for some non-negative integer v and α ≡ 1(mod2). Define Λ(2)as equivalence classes that identify α and β ∈ H(Z) if ±pv1α = pv2β for somev1, v2 ∈ Z. It is known that the Cayley graph of Λ(2) is the (p+ 1)-regulartree. Define Λ(2q) byΛ(2q) = {[α] ∈ Λ(2)|2q divides αj , j = 1, 2, 3}.This is a normal subgroup of Λ(2) and Xp,q, the LPS graph, is defined as theCayley graph of Λ(2)/Λ(2q) with generators S/Λ(2q). This graph is knownto be a (p+ 1)-regular bipartite graph on q(q2 + 1) vertices.18Chapter 5. Abelian Girth of the LPS ExpandersSince Xp,q is a Cayley graph it is vertex transitive which allows us toassume its smallest cycle goes from the identity element of Λ(2) to somenontrivial element of Λ(2q) along the infinite Cayley graph of Λ(2). We nowdefine a vertex’ depth as its distance from the identity in the Cayley graphof Λ(2). Biggs and Boshier [5] show that if [b] ∈ Λ(2) is at depth 2r andr > 0 then there is some b in the equivalence class [b] such thatb0 = ±(pr −mq2)with m > 0 and even.Definition 5.2. Positive integers are called good if they are not of the form4α(8β + 7) for integers α, β ≥ 0.The following is Lemma 2 of [5].Lemma 5.3. There exists a [b] ∈ Λ(2q) at level 2r with b0 = pr −mq2 withm > 0 and b0 positive if and only if 2mpr −m2q2 is good.In the paragraph before this Lemma, Biggs and Boshier prove at leastone of the integers 2mpr −m2q2 is good for the cases m = 2 and m = 4 solong as they are both positive.The following lemma is original.Lemma 5.4. If m = 4 + 8c for nonnegative integers c, then 2mpr −m2q2is good if it is positive.Proof. Note2mpr −m2q24= (2 + 4c)pr − (4 + 16c+ 16c2)q2 ≡ 2 mod 4implying that 2mpr −m2q2 is good.So for m = 4, 12, 20, 2mpr −m2q2 is good if we can show it is positive.Let r0 be the smallest positive integer such that pr0 > 10q2, which makes2mpr0 −m2q2 positive for those values of m. Then pr0−1 < 10q2 and sor0 < 2 logp q + logp 10 + 1.Thus there exists three distinct [b] ∈ Λ(2q), since each value of m producesa different b0, which means there are three distinct closed walks of length19Chapter 5. Abelian Girth of the LPS Expandersr0 from the identity vertex to itself of length 2r0. From the proof of Theo-rem 2.6 we showed that this situation would imply the abelian girth of Xp,qis at most 8r0. Since n = q(q2 + 1) and d− 1 = p we haveAbl(Xp,q) ≤ 163logd−1 n(1 + o(1)).There is reason to believe the 16/3 factor above can be improved. Inthe preceding arguments, we found three closed walks of length 2r0 from avertex to itself to prove the abelian girth is at most 8r0. Suppose insteadwe found three distinct walks all starting from a vertex v terminating at adifferent vertex u and all these walks are of length r0 + e for some constante. If e = 0 we would have three distinct closed walks from v to itself oflength 2r0 as before. Now though, these three walks correspond to the casefrom the proof of Theorem 2.6 where u 6= v implying that the abelian girthof this graph would be at most 6r0 + 6e instead of 8r0.20Chapter 6k-IndependenceIn this section, we introduce one of the main results from our paper interms of only linear algebra. The main concepts discussed here are linearand tensorial k-independence. In the section following this one, we show aconnection between our two forms of 2-independence and abelian girth usingsheaf theory.6.1 Oriented GraphsIn this subsection we fix some terminology on graphs and morphisms ofgraphs, and define some invariants of graphs that will be guiding examplesin graph homology. We may state easy results without proof; in some casesmore details may be found in [18].Even though the graphs we consider are undirected, it is more natural tostate the theory in terms of directed graphs (and arbitrarily orient the edgesof every undirected graph). There is an equivalent formulation without thechoice of orientation, but at the cost of more cumbersome notation; for moreon this see [18]. Our choice of formulation motivates the following choice ofnomenclature:By an oriented graph (henceforce simply “graph”) we shall mean aquadruple G = (VG, EG, tG, hG) where VG and EG are sets (the “vertices”and “edges”, respectively) and tG, hG : EG → VG are maps (the “tail” and“head” of each edge, respectively). We also sometimes use the notationse+G = hG and e−G = tGNote that we allow multiple edges and self-loops (but not half-edges).Unless otherwise indicated all graphs are assumed finite (that is, the setsVG, EG are finite).While our graphs are oriented, we shall treat them as undirected forgraph-theoretic purposes, that is allow paths in the graphs to traverse eachedge in either direction. Formally, a walk of length m ≥ 1 in a graph Gshall be a sequence of pairs (e1, s1), . . . , (em, sm) where ei ∈ EG for each i,si ∈ {±} and esiG(ei) = e−si+1G (ei+1) for 1 ≤ i < m. The vertices e−s1G (e1),216.1. Oriented GraphsesmG (em) will be called the starting and terminating vertices of the walk, andjointly the endpoints.This level of formality is mainly necessary for graphs with multiple edgesor self-loops, since a self-loop may be traversed along or against its orien-tation and this cannot be determined from knowing the order at which theendpoint of the edge are met.A walk is closed if its starting vertex is the same as its terminatingvertex. A walk in which all the edges are distinct is called simple, and aclosed, simple walk is also known as a cycle. Recall that a graph is acyclicif it has no cycles, connected if every two vertices in G are the endpoints ofa walk, and a tree if it is connected and acyclic.A walk is a path if all the edges and vertices of the walk are distinct.If G1 and G2 are subgraphs of a graph G, by a walk (or path) from G1 toG2 we mean a walk (or path) in G with starting vertex in G1, terminatingvertex in G2 and no other vertex of the walk in G1 or G2. We say a pathor cycle is beaded if every vertex is of degree 2 besides possibly the startingand terminating vertex.A morphism of graphs, f : G → H, is a pair f = (fV , fE) of mapsfV : VG → VH and fE : EG → EH such that tH ◦ fE = fV ◦ tG and hH ◦fE = fV ◦ hG. We shall usually drop the subscripts from fV and fE , butmay include them in the interests of clarity. The set of morphisms will bedenoted Mor(G,H). Thus morphisms are homomorphisms of the underlyingundirected graphs which preserve the orientation.We say that pi ∈ Mor(G,B) is a covering map (respectively, is e´tale2) iffor each v ∈ VG, piE gives a bijection (respectively, injection) of incomingedges of v (i.e. those edges whose head is v) with those of fV (v), and abijection (respectively, injection) of outgoing edges of v and piV (v). We callG a covering graph of B.If pi : G→ B is a covering map and B is connected, then the fibres pi−1(v)(v ∈ VH) and pi−1(e) (e ∈ EH) are all in bijection, and we call their jointcardinality the degree of f and denote it [G : H]. Even if H is not connected,one can still write [G : H] when pi is of constant degree, that is when thenumber of preimages of a vertex or edge in H is the same for all verticesand edges.2Stallings, in [31], uses the term “immersion.”226.2. k-Independence6.2 k-IndependenceIn this subsection we describe two notions of k-independence and give anexample showing they are not equivalent. In later sections, we will showhow the two notions of 2-independence correspond to certain homologicalinvariants of certain sheaves on graphs.Definition 6.1. Let A1, . . . , Ar be subspaces of a finite-dimensional vectorspace W over a field F. We say that A1, . . . , Ar are linearly k-independentwith k a positive integer if for all subspaces B ⊂W we haver∑i=1dim(Ai ∩B) ≤ k dim(B). (6.1)We define the total dimension of the subspaces to be |A1|+ . . .+ |Ar|This notion arises implicitly in quiver representation theory in [25], wherethe case k = 2 is of special interest. We shall explain in this paper that thek = 2 case also arises in what we call pseudobundles on a graph. Notice thatk-independence could easily be defined for any real number k.It is easy to see that r vectors in a vector space, W , are linearly inde-pendent (in the usual sense) iff the one-dimensional spaces that the vectorsspan are linearly 1-independent.Definition 6.2. Let A1, . . . , Ar be subspaces of a vector space, W , over afield, F, and let F be an algebraic closure of F. Let k be a positive integer. Wesay that A1, . . . , Ar are tensorially k-independent if for any f1, . . . , fr ∈ Fkand any ai ∈ Ai for 1 ≤ i ≤ r we have thatf1 ⊗ a1 + . . .+ fr ⊗ ar = 0only ifa1 = . . . = ar = 0or the jth components of the f1, . . . , fr are all 0 for some 1 ≤ j ≤ k.It is easy to see that r vectors in a vector space, W , are linearly indepen-dent (in the usual sense) iff the one-dimensional spaces that the vectors spanare tensorially 1-independent. It is also easy to see that if the Ai are nottensorially k-independent, they also are not tensorially k + 1-independentWe claim that tensorial k-independence implies linear k-independence(this is also shown in[19].) For this, consider A1, . . . , Ar ⊂ W that are notlinearly k-independent; then there exists a B ⊂W such thatdim(A1 ∩B) + · · ·+ dim(Ar ∩B) > k dim(B).236.2. k-IndependenceFor a vector space, U , over F, let U denote the corresponding vector spaceover F, namely U ⊗F F. Consider the mapA1 ∩B ⊕ · · · ⊕Ar ∩B → Bgiven byf1 ⊗ a1 + . . .+ fr ⊗ arfor some f1, . . . , fr ∈ Fk and ai ∈ Ai∩B. Since the dimension of the domainis greater than that of the range, there must exist a nontrivial element inthe kernel.Theorem 6.3. Linear 2-independence does not imply tensorial 2-independence.Here is an example of a collection of subspaces that are linearly butnot tensorially 2-independent. If W = F6 has basis α, β, γ, δ, , ζ then thesubspaces areA1 = Span(α, δ), A2 = Span(β, ), A3 = Span(γ, ζ),A4 = Span(β − γ, δ − , ζ − α), A5 = Span(α− β, γ − δ, − ζ).We will provide sheaf theoretic tools in later sections in order to provethese subspaces are linearly but not tensorially 2-independent. We alsoconjecture that this is the smallest such collection of subspaces in terms oftotal dimension of the subspaces.24Chapter 7Sheaves on GraphsIn this section we describe the notion of “sheaf on a graph” and show the2-independence problem is a special case of a general problem concerningtwo homological invariants of certain sheaves on graphs with two vertices.7.1 Sheaves and HomologyDefinition 7.1. Let G = (V,E, t, h) = (VG, EG, tG, hG) be a directed graph,and F a field. By a sheaf of finite dimensional F-vector spaces on G, orsimply an F-sheaf on G, we mean the data, F , consisting of1. a finite dimensional F-vector space, F(v), for each v ∈ V ,2. a finite dimensional F-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,We will often just refer to the sheaf, F , with the graph, G, being implicit.The vector spaces F(P ), ranging over all P ∈ VG q EG (q denoting thedisjoint union), are called the values of F . The morphisms F(t, e) andF(h, e) are called the restriction maps. If U is a finite dimensional vectorspace over F, the constant sheaf associated to U , denoted U , is the sheafcomprised of the value U at each vertex and edge, with all restriction mapsbeing the identity map. The constant sheaf F will be called the structuresheaf of G (with respect to the field, F), for reasons to be explained later.We say that F1 is a subsheaf of F if F1 is a sheaf on G whose value atany vertex or edge is a subspace of the value of F at that vertex or edge,and if the restriction maps of F1 are induced by those of F . Subsheaves ofconstant sheaves will be called subconstant sheaves.To a sheaf, F , on a digraph, G, we setF(E) =⊕e∈EF(e), F(V ) =⊕v∈VF(v).257.1. Sheaves and HomologyWe associate a transformationdh = dh,F : F(E)→ F(V )defined by taking F(e) (viewed as a component of F(E)) to F(he) (a com-ponent of F(V )) via the map F(h, e). Similarly we define dt. We define thedifferential of F to bed = dF = dh − dt,and define the Euler characteristic of F to beχ(F) = dim(F(V ))− dim(F(E)).We call the sheaf F a constant sheaf if F(e) = F(v) for all vertices v andedges e in G and the difference maps are all the identity.Definition 7.2. We define the zeroth and first homology groups of F tobe, respectively,H0(G,F) = cokernel(d), H1(G,F) = kernel(d).We denote by hi(G,F) the dimension of Hi(G,F) as an F-vector space,and call it the i-th Betti number of F . This definition agrees with sheafhomology theory. We often just write hi(F) and Hi(F) if G is clear fromthe context (when no confusion will arise between hi(F), the dimension, andh the head map of a graph). We call Hi(F) the i-th homology group of Gwith coefficients in F, denoted Hi(G) or, for clarity, Hi(G,F). This agreeswith the standard definition of Hi(G).In particular, we haveχ(F) = h0(F)− h1(F).Example 7.3. For F = F, d is just the usual incidence matrix; thus, if F isof characteristic zero, then the hi(G), i.e., the dimension of the Hi(G), arethe usual Betti numbers of G.Example 7.4. For any morphism φ : G′ → G of digraphs, and any sheafF on G′, there is a sheaf φ!F such that Hi(G′,F) is naturally isomorphicto Hi(G,φ!F). See [17, 19] for more details on this and other examples ofsheaves.One of the main tools in sheaf homology is the ability to get informationabout them by the long exact sequence in homology associated to a shortexact sequence of sheaves. For this we need to describe what is meant by amorphism of sheaves.267.2. Twisted HomologyDefinition 7.5. A morphism of sheaves α : F → G on G is a collectionof linear maps αv : F(v) → G(v) for each v ∈ V and αe : F(e) → G(e) foreach e ∈ E such that for each e ∈ E we have G(t, e)αe = αteF(t, e) andG(h, e)αe = αheF(h, e).It is not hard to check that all Abelian operations on sheaves, e.g., takingkernels, taking direct sums, checking exactness, can be done “vertexwiseand edgewise,” i.e., F1 → F2 → F3 is exact iff for all P ∈ VG q EG,we have F1(P ) → F2(P ) → F3(P ) is exact. This is actually well known,since our sheaves are presheaves of vector spaces on a category (see [15] orProposition I.3.1 of [1]).The following theorem results from a straightforward application of clas-sical homological algebra.Theorem 7.6. To each “short exact sequence” of sheaves, i.e.,0→ F1 → F2 → F3 → 0(in which the kernel of each arrow is the image of the preceding arrow), thereis a natural long exact sequence of homology groups0→ H1(F1)→ H1(F2)→ H1(F3) δ−→H0(F1)→ H0(F2)→ H0(F3)→ 0.7.2 Twisted HomologyHere we define twisted homology. We refer to [17, 18] for its motivation;in brief, it represents a “scaled Abelian limit” of ordinary homology, andhas “reduced cyclicity” as a special case. Here we give a self-containeddescription of these invariants, and the reader who does not consult [17, 19]may regard twisted homology as simply an alternate homology theory.Definition 7.7. Let F be a sheaf of F-vector spaces on a digraph, G, andlet F′ be a field containing F. A twist or F′-twist, φ, on G is a mapφ : EG → F′.By the twisting of F by φ, denoted Fφ, we mean the sheaf of F′-vectorspaces given viaFφ(P ) = (F(P ))⊗F F′277.2. Twisted Homologyfor all P ∈ VG q EG, andFφ(h, e) = F(h, e), Fφ(t, e) = φ(e)F(t, e),where F(h, e) and F(t, e) are viewed as F′-linear maps arising from theiroriginal F-linear maps.In other words, Fφ is the sheaf obtained by extending scalars to F′ andtwisting the tail maps. The map, dFφ , viewed as a matrix, has entries inthe field F′ and the groups Hi(Fφ) are F′-vector spaces.Definition 7.8. Let F be a sheaf of F-vector spaces on a digraph, G. Bythe full twist of F we mean the twist EG → F(ψ), where ψ = {ψ(e)}e∈EGis a collection of |EG| independent indeterminates, and F(ψ) is the field ofrational functions in the {ψ(e)} over F, and where the map EG → F(ψ) isgiven by e 7→ ψ(e). We shall refer to this twist as ψ when no confusion willarise. The twist ψ can be defined in the same way given a graph G and afield F even if no sheaf is specified. In this case we refer to ψ as the full twistof G.In the above situation, d = dFψ can be viewed as a morphism of finitedimensional vector spaces over F(ψ), given by a matrix with entries in F(ψ).Definition 7.9. We define the i-th twisted homology group of F , denotedbyHtwi (F) = Htwi (F , ψ),for i = 0, 1, respectively, to be the cokernel and kernel, respectively, of dFψdescribed above as a morphism of F(ψ) vector spaces. We define the i-thtwisted Betti number of F , denoted htwisti (F), to be dimension of Htwi (F).Notice that twisted homology as above is just the homology of certainsheaves over F(ψ). In particular, the following results from applying Theo-rem 7.6.Theorem 7.10. Let F be a field, and let ψ be a full twist on G. For anyshort exact sequence0→ F1 → F2 → F3 → 0of sheaves of F-vector spaces on G, there is a long exact sequence of F(ψ)vector spaces,0→ Htw1 (F1)→ Htw1 (F2)→ Htw1 (F3) δ−→Htw0 (F1)→ Htw0 (F2)→ Htw0 (F3)→ 0.287.3. Maximum Excess of a Sheaf7.3 Maximum Excess of a SheafDefinition 7.11. Let F be a sheaf on a graph, G. We define the excess ofF to beexcess(F) = −χ(F).We define the maximum excess of F to be the maximum excess over allsubsheaves of F , i.e.,m.e.(F) = maxF ′⊂Fexcess(F ′).The excess and maximum excess has a number of remarkable propertiesthat are established in [17, 19]; let us mention a few here without proof,referring the reader to [17, 19] for more details and the proofs.Let F be a sheaf on a graph, G. The dimension of the kernel of anylinear map from F(E) to F(V ) is at leastdim(F(E))− dim(F(V )) = −χ(F) = excess(F).If ψ is a full twist on G, then the map dFψ resticts to a map from F ′(E) toF ′(V ) for any subsheaf, F ′, of F ; hencehtw1 (F) ≥ m.e.(F).Definition 7.12. The gap of a sheaf, F , is the non-negative integergap(F) = htw1 (F)−m.e.(F).We say that a sheaf is gapped or has a gap if its gap is positive; otherwisewe say that the sheaf has no gap.This paragraph is written to give the reader some intuition for the gap,htw1 , and the maximum excess, though the results mentioned here will alsobe useful later on. In [17, 18] Friedman defines the pullback, µ∗F , for anygraph morphism µ : G′ → G and any sheaf on G (in a natural and standardfashion); he shows that if µ is a covering map thenm.e.(µ∗F) = deg(µ)m.e.(F), (7.1)and he shows that for any fixed sheaf, F , on G, we havem.e.(µ∗F) = htw1 (G′, µ∗F), (7.2)297.3. Maximum Excess of a Sheafprovided that µ : G′ → G is a covering map and the girth of G′ is sufficientlylarge. Therefore, if we order covering maps under refinement, we can saythat any sheaf has no gap if pulled-back via a covering map to a graph ofsufficiently large girth. We can also writem.e.(F) = limµhtw1 (µ∗F)deg(µ), (7.3)where the limit is taken over the directed set of covering maps, u, underrefinement.As a consequence of (7.3), we have that the maximum excess is additive,i.e., if F1,F2 are sheaves on a graph, thenm.e.(F1 ⊕F2) = m.e.(F1) + m.e.(F2);this follows since htw1 is additive and (arbitrary) pullbacks are additive. Sim-ilarly, we get inequalities from short exact sequences, which we now describe.Definition 7.13. For a sheaf, F , on a graph, we define its dual maximumexcess, denoted d.m.e.(F) to bed.m.e.(F) = χ(F) + m.e.(F).We easily see thatd.m.e.(F) = maxFF ′χ(F ′),sinced.m.e.(F) = χ(F) + maxF ′′⊂F−χ(F ′′) = maxF ′′⊂Fχ(F/F ′′).It follows that the dual maximum excess is non-negative andd.m.e.(F)−m.e.(F) = χ(F) = htw0 (F)− htw1 (F),for any sheaf, F ; in particularhtw1 (F)−m.e.(F) = gap(F) = htw0 (F)− d.m.e.(F),which gives an alternate expression for the gap of a sheaf.Theorem 7.14. To each short exact sequence of sheaves,0→ F1 → F2 → F3 → 0,307.4. Main Theoremsthe sequence of non-negative integers. . . , 0, 0,m.e.(F1),m.e.(F2),m.e.(F3),d.m.e.(F1),d.m.e.(F2), d.m.e.(F3), 0, 0, . . .is “triangular,” meaning any element of the sequence is at most the sum ofits successor and its predecessor.This follows from (7.3) and Theorem 7.6. Alternatively, this can beproven from scratch (see Warren Dicks’ appendix in [19].)The following definition is a crucial observation to the proof of the HannaNeumann Conjecture in [16, 19] and to this paper.Definition 7.15. A maximizer of the sheaf F is any subsheaf whose excessis the maximum excess of F .If F1,F2 are subsheaves of the sheaf F one can easily verify thatχ(F1) + χ(F2) = χ(F1 ∩ F2) + χ(F1 + F2).It follows that the set of maximizers of F is closed under intersection andaddition of subsheaves. In particular, each sheaf F has a unique maximum(or maximal) maximizer (namely the sum of all the maximizers) and uniqueminimum (or minimal) maximizer (namely the intersection of all the maxi-mizers).It is not hard to see that the structure sheaf, F, of a connected graph Ghasm.e.(G,F) = max(0,−χ(G)),and thatd.m.e.(G,F) ={1 if G is cyclic, and0 if G is acyclic,where G is acyclic if G is a vertex or a tree, and otherwise G is cyclic; if Gis not connected, then the maximum excess of F is the sum composed of themaximum excess of each of G’s connected components, and similarly with“maximum excess” replaced with “dual maximum excess.”7.4 Main TheoremsIn this section we fix some terminology regarding sheaves on graphs andformally describe the main theorems of the second part of this dissertation.317.4. Main TheoremsDefinition 7.16. Let F be a sheaf on a graph. By a subquotient of F wemean any sheaf of the form F2/F1, where F1 ⊂ F2 ⊂ F .Theorem 7.17. If G is a graph on two vertices, no self loops, and at leastfive edges, then there exists a gapped subconstant sheaf on G with maximumexcess 0.Theorem 6.3 follows quickly from this theorem in the following way. LetF be the gapped subquotient sheaf on the graph G with vertices v1 andv2 produced by the previous theorem. Let the vector space W = F(v1) +F(v2). If G has edges e1, ..., er, then let Ai = F(ei) for i = 1, . . . , r. Forany subconstant sheaf the head and tail maps are inclusions since theyare induced by identity maps, and so the Ai are subspaces of W . Sincem.e.(F) = 0, for any B ⊂Wr∑i=1dim(Ai ∩B) ≤ 2 dim(B),showing that the Ai are linearly 2-independent.Given any nonzero α ∈ Htw1 (F), let ai be α restricted to the edge spaceon ei. Thenr∑i=1fi ⊗ ai = 0where fi = (1,−ψei). This shows that theAi are not tensorially 2-independent.The proof for Theorem 7.17 is constructive, using a sheaf that is modi-fied from a minimally gapped sheaf necessary in the proof of the followingtheorem.Theorem 7.18. For any graph G we haveAbl(G) = min{dim(F(E))|F is a gapped sheaf on G}.The proof of this theorem includes explicit constructions of gapped sheaveswith minimal edge dimension for any graph. This theorem implies that sheaftheory could potentially be useful for finding better upper bounds on thegirth of a regular graph.Corollary 7.19. Let G be a graph with χ(G) < 0. Then there exists asubconstant sheaf on G with positive gap. If F is a subquotient of a constantsheaf on G with positive gap then dim(F(E)) ≥ 6.327.4. Main TheoremsThe smallest edge dimension known to us for a a gapped subconstantsheaf on a graph is 12. Before this research, it was not known whethergapped subconstant sheaves even existed.Proving the results in this subsection will occupy the rest of this disser-tation.33Chapter 8Remarks on Gapped SheavesRecall that that gap of a sheaf, F , on a graph is defined to begap(F) = htw1 (F)−m.e.(F) = htw0 (F)− d.m.e.(F)and that we say that F has a gap (or is gapped) if its gap is positive.The goal of the next few sections is to prove that certain sheaves have nogap. Furthermore, when a collection of sheaves contains gapped sheaves, wewish to describe the “simplest” example of a gapped sheaf in the collection.This section contains some important definitions and some easy observationsregarding these matters.As an example, Theorems 7.6 and 7.14 imply that htw1 , htw0 and the max-imum excess and dual maximum excess are additive invariants, and henceso is the gap; i.e.,gap(F1 ⊕F2) = gap(F1) + gap(F2)for any sheaves, F1,F2 on a graph. Hence if F1 ⊕ F2 is gapped, then so isF1 or F2. On certain collections of sheaves, with a certain partial order, thiswill mean that a minimal gapped sheaf (if it exists) is not a proper directsum. However, we need to specify the collections of sheaves and partialorders we use.8.1 MinimalityIn this subsection we define what is a “simplest” or “minimal” sheaf in acollection, in a sense useful to our theory. This section consists only ofdefinitions and very simple remarks.Definition 8.1. Let F be a sheaf on a graph, G. The total dimension (orT-dim) of F , denoted T− dim(F) shall mean the quantityT− dim(F) =∑P∈VGqEGdim(F(P )).348.2. Minimal Elements and StabilityDefinition 8.2. By a sheaf collection we mean a set of pairs, (G,F), whereG is a graph and F is a sheaf on G.If C is a sheaf collection, we may write F ∈ C instead of the morecumbersome (G,F) ∈ C when G is implicit.Definition 8.3. Given a sheaf collection, C, a T-minimal element of C isan F ∈ C of minimal total dimension.Clearly any nonempty sheaf collection has T-minimal element.Definition 8.4. Given a sheaf collection, C, a T-minimal gapped elementis a T-minimal element among the subcollection of sheaves in C which havea positive gap (if this subcollection is nonempty).8.2 Minimal Elements and StabilityWe now wish to state the main result in this section. It will be proved overthe next few subsections. First though, we include some addition definitionsrelated to the ones we need.Definition 8.5. The sheaf F is called1. cyclic if m.e.(F) = −χ(F), i.e., χ(F ′) ≥ χ(F) for each F ′ ⊂ F ;2. semistable if it is cyclic, and χ(F) = 0;3. stable if it is semistable, and for all F ′ ⊂ F we have χ(F ′) > χ(F)unless F ′ is 0 or F ;4. superstable if for all F ′ ⊂ F we have χ(F ′) > χ(F) unless F ′ is F .The minimum maximizer of F is called its supercore.A supercore is therefore necessarily superstable. Our terminology isborrowed from [25] and [8]. It is easy to see that for F ′ ⊂ F , if F issemistable, stable, or superstable, then so is F/F ′. Furthermore, if F isstable and F ′ 6= F , then F/F ′ is superstable.A graph is cyclic if it contains no components that are trees; it issemistable if its connected components all have Euler characteristic zero(i.e., when its leaves are repeatedly “pruned,” the graph becomes a union ofcycles); it is stable if it consists of a single cycle; it is superstable if all itsconnected components have no leaves and have negative Euler characteristic.One can also define dual or “co” notions of stability.358.2. Minimal Elements and StabilityDefinition 8.6. A sheaf, F , on a graph is called co-acyclic, co-semistable,co-stable, co-superstable, by taking the respective notion in Definition 8.5(omitting the prefix “co-”) and replacing “maximum excess” with “dualmaximum excess,” “χ” with “−χ,” and “F ′ ⊂ F” with “F ′ is a quotient ofF .”Generally speaking, to most of the notions and lemmas in this section,there is a “co” or “dual” notion; typically a lemma and its dual lemma aredifferent and both important to proving Theorem 8.9 below. We mention,however, that stability, one of the cornerstones of this article, is equivalentto its dual notion, co-stability. Indeed, to every subsheaf, F ′, of a sheaf, F ,there is a short exact sequence0→ F ′ → F → F ′′ → 0,(with F ′′ = F/F ′), and to every quotient, F ′′, of F there is a short exactsequence (with F ′ the kernel of the map F → F ′′). So whenever χ(F) = 0,the condition of having a subsheaf with non-negative Euler characteristic isequivalent to having a quotient sheaf with non-positive Euler characteristic.Hence stability and co-stability amount to the same thing.Definition 8.7. We say that a sheaf collection, C, is closed under subsheavesand quotients provided that for all F ∈ C, any subsheaf or quotient sheaf ofF lies in C.Definition 8.8. We say that a sheaf is faithful if every restriction map isan injection.Here is the main theorem of this section. Parts of this theorem are validunder weaker hypothesis, as will be evident in the subsections that follow.Theorem 8.9. Let C be a sheaf collection that is closed under subsheavesand quotients. Assume that C contains at least one gapped sheaf, and letF be any T-minimal gapped sheaf. Then F is stable, and htwi (F) = 1 fori = 0, 1.The proof will take up the rest of this section and will be completed inSubsection 8.6; the proof is straightforward and independent of the rest ofthis paper. The same theorem holds for any T-minimal gapped sheaf, aswell, although we will not need this result.368.3. Edge Subsheaf Closed Collections8.3 Edge Subsheaf Closed CollectionsDefinition 8.10. An edge subsheaf of a sheaf, F , is a subsheaf F ′ ⊂ Fsuch that F ′ and F agree on their values of each vertex. A sheaf collection,C, is edge subsheaf closed if F ∈ C implies that F ′ ∈ C whenever F ′ is anedge subsheaf of F .Lemma 8.11. Let F be a sheaf on a graph G with m.e.(F) ≥ 1. Then thereis an edge subsheaf, G, of F such that F/G is of total dimension one withm.e.(G) = m.e.(F)− 1.Proof. (Given in [18].) Let F ′ be the minimal subsheaf of F with −χ(F ′) =m.e.(F). Since m.e.(F) ≥ 1, there exists an e ∈ EG such that F ′(e) 6= 0; letA ⊂ F(e) be a subspace of codimension one such that F ′(e)∩A is a propersubspace of F ′(e). Let G be the (A, e) edge subsheaf of F . Then F/G is oftotal dimension one. We claim m.e.(G) = m.e.(F)−1; indeed, any subsheaf,G′, of G is also a subsheaf of F , but G′ does not contain the miniminal excessmaximizer of F ; hence −χ(G′) ≤ m.e.(F)− 1.Lemma 8.12. Let F be a sheaf on a graph, G with htw1 (F) ≥ 1. Then thereis an edge subsheaf, G, of F such that F/G is of total dimension one withhtw1 (G) = htw1 (F)− 1.Proof. Let α ∈ Htw1 (F , ψ) with α 6= 0. Since α is nonzero, there is ane ∈ EG with α(e) 6= 0. For some A ⊂ F(e) we have α(e) /∈ A(ψ). Fix somesuch A, and let G be the (A, e) edge subsheaf of F . Then Htw1 (G, ψ) is asubspace of Htw1 (F , ψ), but since the former does not contain α, the formeris a strict subspace of the latter. But since F/G is of total dimension one,the former cannot be of codimension greater than one in the latter. Hencehtw1 (G) = htw1 (F)− 1.Lemma 8.13. Let F be any gapped sheaf on a graph. Then there exists anedge subsheaf, F ′, of F , such that m.e.(F ′) = 0 and htw1 (F ′) = 1.Proof. We claim that it suffices to consider the case where m.e.(F) = 0.Indeed, assume that m.e.(F) > 0. By Lemma 8.11, F has an edge subsheaf,G, with m.e.(G) = m.e.(F) − 1 with F/G of total dimension one. Buthtw1 (G) ≥ htw1 (F ) − 1, since FcG is of total dimension one. Hence G is agapped edge subsheaf of F with maximum excess one less than F . Repeatingthis argument gives a gapped edge subsheaf, G′, of F with maximum excesszero, and it suffices to prove the lemma for G′.Similarly, if m.e.(F) = 0 but htw1 (F) ≥ 2, we may repeatedly ap-ply Lemma 8.12 to find an edge subsheaf, F ′, of F , with htw1 (F ′) = 1.378.4. Vertex Quotient Closed CollectionsBut passing to edge subsheaves cannot increase the maximum excess, som.e.(F ′) = 1.Corollary 8.14. Let C be a sheaf collection that is closed under edge sub-sheaves and that contains a gapped element. Then any T-minimal gappedelement, F , of C has m.e.(F) = 0 and htw1 (F) = 1.Proof. We know that F has an edge subsheaf, F ′, with m.e.(F ′) = 0 andhtw1 (F ′) = 1. But F ′ is also gapped, and by minimality must equal F .8.4 Vertex Quotient Closed CollectionsAt this point we give “dual” versions of all the statements in the previoussubsection.We remark that some readers can infer all the dual statements from thefollowing principle (and therefore need not read any proofs in this section.)Our sheaves on graphs can be viewed as presheaves of vector spaces on a1-dimensional category (in the evident sense.) For any presheaf of vectorspaces of finite dimension on a category, the dual spaces form a presheafon the opposite category. Since the statements in the previous subsectiongeneralize to this wider setting, the dual statements follow immediately.Definition 8.15. A vertex quotient of a sheaf, F , is a quotient of F whosevalues agree with those of F on all the edges. A sheaf collection, C, is vertexquotient closed if F ∈ C implies that F ′ ∈ C whenever F ′ is a vertex quotientof F .Lemma 8.16. Let F be a sheaf on a graph, G with d.m.e.(F) ≥ 1. Thenthere exists a vertex quotient, G, of F , such that d.m.e.(G) = d.m.e.(F)− 1and the total dimension of G is one less than the total dimension of F .Furthermore, G can be taken equal to F except at any vertex, v, for whichthe maximum excess maximizer’s value at v is not all of F(v).Proof. Let F ′ be the maximum subsheaf of F that maximizes the excess.Since1 ≤ d.m.e.(F) = m.e.(F) + χ(F),we have F ′ 6= F and −χ(F ′) > −χ(F). It follows that for some v we haveF ′(v) 6= F(v); let A be a one dimensional subspace of F(v) that does notlie in F ′(v), for such a v, and let G be the (A, v) quotient of F .388.4. Vertex Quotient Closed CollectionsWe claim that m.e.(G) = m.e.(F); this will finish the proof of the lemma,since thend.m.e.(G) = m.e.(G) + χ(G) = m.e.(F) + χ(F)− 1 = d.m.e.(F)− 1.To see that m.e.(G) = m.e.(F), consider the image of F ′ under the inclusionto F followed by the quotient map to G; this gives a subsheaf, G′, of G thatis isomorphic to F ′. Hencem.e.(G) ≥ m.e.(F). (8.1)But for any subsheaf, G′′, of G, consider its inverse image, F ′′, in F : we haveχ(F ′′) = χ(G′′) + 1, because of the quotienting at v, but F ′′ contains A andtherefore cannot maximize the excess of F . Hence−χ(F ′′) ≤ m.e.(F)− 1,and hence−χ(G′′) = −χ(F ′′) + 1 ≤ m.e.(F).Hence, maximizing the above over all G′′ in G, we havem.e.(G) ≤ m.e.(F).Combing this with (8.1) shows that m.e.(G) = m.e.(F), completing the proofof the lemma.Lemma 8.17. Let F be a sheaf on a graph, G with htw0 (F) ≥ 1. Then thereexists a vertex quotient, G, of F , such that htw0 (G) = htw0 (F) − 1 and thetotal dimension of G is one less than the total dimension of F .Proof. For v ∈ VG and w ∈ F(v), consider the element δv,w of F(V ) definedas 0 outside of v and w at F(v). Clearly the δv,w span F(V )(ψ). Henceif Htw0 (F) 6= 0, there is some δv,w with w 6= 0 that is not in the image ofdFψ . Fix such a v and w. Let G be the same as F except that its value atv is F(v) modulo the span of w. Then α is an equivalence class modulo theimage of F(E) in F(V ) under dcf. ψ .Lemma 8.18. Let F be any gapped sheaf on a graph. Then there exists avertex quotient, F ′, of F , such that d.m.e.(F ′) = 0 and htw0 (F ′) = 1.398.5. Edge Quotient Closed Collections and InjectivityProof. We claim that it suffices to consider the case where d.m.e.(F) =0. Indeed, assume that d.m.e.(F) > 0. By Lemma 8.16, F has a vertexquotient, G, with d.m.e.(G) = d.m.e.(F) − 1 with F/G of total dimensionone. But htw0 (G) ≥ htw0 (F )− 1, since FcG is of total dimension one. HenceG is a gapped vertex quotient of F with dual maximum excess one less thanF . Repeating this argument gives a gapped vertex quotient, G′, of F withdual maximum excess zero, and it suffices to prove the lemma for G′.Similarly, if d.m.e.(F) = 0 but htw0 (F) ≥ 2, we may repeatedly applyLemma 8.17 to find a vertex quotient, F ′, of F , with htw0 (F ′) = 1. Butpassing to vertex quotients cannot increase the dual maximum excess, sod.m.e.(F ′) = 1.Corollary 8.19. Let C be a sheaf collection that is vertex quotient closedand that contains a gapped element. Then any T-minimal gapped element,F , has d.m.e.(F) = 0 and htw0 (F) = 1.Proof. Let F be T-minimal gapped. Then F ′ has a vertex quotient withd.m.e.(F ′) = 0 and htw0 (F ′) = 1. But its T-dimension is strictly less unlessF ′ = F .8.5 Edge Quotient Closed Collections andInjectivityDefinition 8.20. Let F be a sheaf on a graph, G. Given e ∈ EG, and asubspace A ⊂ F(e), we define the A skyscraper (of F) at e, denoted A|e(with F understood), to be the subsheaf whose values for P ∈ VG qEG areA|e(P ) =A if P = e,F(e, h)A if P = he and P 6= te,F(e, t)A if P = te and P 6= he,F(e, h)A+ F(e, t)A if P = he = te, and0 otherwiseand where the restriction maps are given by restricting F(e, h) and F(e, t).By the A edge quotient of F at e we mean the quotient F/A|e. We saythat a sheaf collection, C, is edge quotient closed if for any F ∈ C, any edgequotient of F also lies in C.Lemma 8.21. Let C be a sheaf collection that is edge subsheaf, vertex quo-tient, and edge quotient closed. Let F ∈ C be T-minimal gapped. Then forany edge, e we have that both restriction maps at F(e) are injective.408.6. The Proof of Theorem 8.9Proof. Let e be any edge with two distinct endpoints. Assume that F(e) 6=0. For any nonzero a ∈ F(e) we claim that we must have F(e, h)a 6=0 and F(e, t)a 6= 0. Indeed, let F ′ be the A edge quotient of F at e,where A is the span of a; then F ′ ∈ C and F ′ < F in the T-order. IfF(e, h)a = 0 and F(e, t)a = 0, then F is the direct sum of F ′ plus A|e. Butin this case m.e.(A|e) = htw1 (A|e) and both the maximum excess and the firsttwisted Betti of a direct sum is the sum of the individual invariants. Hencem.e.(F ′) > htw1 (F ′), contradicting the minimality of F . The other case toconsider is F(e, h)a = 0 and F(e, t)a 6= 0 (the case with h and t reversed isargued identically). In this case we have an exact sequence0→ A|e → F → F ′ → 0,and htw0 (A|e) = htw1 (A|e) = 0, so F and F ′ have the same twisted Betti num-bers. Similary for any covering map φ : G′ → G we have that htw0 (φ∗A|e) =htw1 (φ∗A|e) = 0, so we have that F and F ′ have the same maximum excessand dual maximum excess. This again contradicts the minimality of F .8.6 The Proof of Theorem 8.9Proof of Theorem 8.9. Let C be a sheaf collection that is closed under sub-sheaves and quotients. Assume that C contains at least one gapped sheaf,and let F be any T-minimal gapped sheaf. According to Corollaries 8.14and 8.19 we have that m.e.(F) = d.m.e.(F) = 0 and htwi (F) = 1 for i = 0, 1.Furthermore, by Lemma 8.21, we have that each restriction is an injection.Consider any short exact sequence0→ F ′ → F → F ′′ → 0 (8.2)in which F ′ and F ′′ are both nonzero. Then F ′ and F ′′ are both less thanthan F in T-order, and hence F ′ and F ′′ have no gap.By Theorem 7.14, we havem.e.(F ′) = d.m.e.(F ′′) = 0.Since F ′ and F ′′ have no gap, we havehtw1 (F ′) = m.e.(F ′) = 0, htw0 (F ′′) = d.m.e.(F ′) = 0. (8.3)We also haveχ(F ′) = d.m.e.(F ′)−m.e.(F ′) = d.m.e.(F ′) ≥ 0. (8.4)418.6. The Proof of Theorem 8.9Furthermore,χ(F ′′) = χ(F)− χ(F ′) = −χ(F ′). (8.5)We claim that χ(F ′) > 0. Indeed, otherwise, by (8.4), χ(F ′) = 0, and,by (8.5), χ(F ′′) = 0. But χ(F ′) = 0 implies that htwi (F ′) is independent ofi, and similarly with F ′′ replacing F ′. Then (8.3) implies that htwi (F ′) = 0for i = 0, 1, and the same with F ′′ replacing F ′. But Theorem 7.10 showsthat if F ′ and F ′′ have all their twisted homology groups vanishing, then sodoes F . But we know htwi (F) = 1 for i = 0, 1.But if F ′ is any subsheaf of F , then it forms a subsequence of the formin (8.2), with F ′′ = F/F ′. Hence for any subsheaf, F ′, we have χ(F ′) > 0.Hence F is stable.42Chapter 9The Twist Trick and EdgeDetachmentIn this section we describe what we call the “twist trick.” It amounts tomodifying a sheaf by setting the head or tail map to zero along an edge, e,and noting that the new sheaf’s twisted homology groups do not depend onthe twist at e; this seemingly trivial observation yields one of our main tools.Intuitively, these theorems seem to specialize the value of an edge twist to bezero or infinity or some other value, and draw interesting conclusions (this“specialization” has to be explained and justified before it makes sense).We then define an operation on graphs and sheaves called “edge loopi-fication” and interpret our twist trick results in those terms. This leads usto a conjecture on sheaves on graphs which will occupy us for most of therest of this paper.9.1 The Fundamental “Twist Trick” LemmaThe basic “twist trick” is to take a sheaf, F , on a graph and modify it bysetting its head or tail map at some edge to zero, obtaining F ′. If S is avector space or a linear map, we use S∨ to denote the dual of S. Clearlyhtwist0 cannot decrease, and the elements of Htwist0 (F)∨ can be written interms of Htwist0 (F ′)∨; however, Htwist0 (F ′)∨ elements are independent of thetwist at the discarded edge, and this gives interesting results.First we give a lemma that describes the basic technique. Then we giveits consequences and some variants. The simplest consequence roughly saysthat “one can always set a twist to zero or infinity.’Lemma 9.1. Let F be a sheaf on a graph, G, and let e0 ∈ EG. Let G′ beG with e0 deleted, and let F ′ be F restricted to G′. If htwist0 (G;F) 6= 0, thenthere exists an element of Htwist0 (G′;F ′)∨ whose value at he0 (respectivelyte0) is a linear functional that vanishes at the image of F(e0, h) (respectivelyF(e0, t)).439.1. The Fundamental “Twist Trick” LemmaOur primary application is the case where te0 6= he0, but the lemmaholds even if e0 is a self-loop.Proof. Let ψ be a full twist of G, and which we will write as ψ = (ψ′, ψe0),where ψ′ is a full twist of G′ and ψe0 is the twist at e0. There is a naturalinjection:Htwist0 (G;F)∨ → Htwist0 (G′;F ′)∨(ψe0) = Htwist0 (G′;F ′)∨ ⊗F(ψ′) F(ψ),simply because an element, α, of Htwist0 (G;F)∨ is just a collection of linearfunctionals, α(v) ∈ F(v)(ψ)∨ that satisfy consistency conditions along theedges, namely for each e ∈ E:α(he)F(e, h)∨ = ψeα(te)F(e, t)∨.The elements of Htwist0 (G′;F ′)∨(ψe0) are the same, except that the conditionof consistency is not required at e = e0; since G′ has the same vertices asG, and F ′ has the same vertex spaces as F , the above map is an injection.Let α1, . . . , αr be a basis for Htwist0 (G′;F ′)∨. Any non-zero element, β, ofHtwist0 (G′;F ′)∨ may therefore be written asβ =r∑i=1ci(ψ)αi(ψ′),where the ci(ψ) ∈ F(ψ) and not all ci are zero, and where we have writtenαi as αi(ψ′) to emphasize the fact that the αi depend only on the twists ofψ′ are are independent of ψe0 . By clearing denominators we may assumethat ci(ψ) ∈ F[ψ], i.e., are polynomials in the ψ; we may therefore write, forsome integer, s,ci(ψ) =s∑j=0ψje0cij(ψ′),where the cij ∈ F[φ′]; furthermore, by dividing common factors of ψe0 , wemay assume that ci0 6= 0 for at least one value of i. But then the consistencycondition at e0 implies thatr∑i=1s∑j=0ψje0cij(ψ′)αi(ψ′)(he)F(e, h)∨= ψe0r∑i=1s∑j=0ψje0cij(ψ′)αi(ψ′)(te)F(t, h)∨. (9.1)449.2. Edge DetachmentSetting ψe0 to zero yieldsr∑i=1ci0(ψ′)αi(ψ′)(he)F(e, h)∨ = 0.In other words, ifγ =r∑i=1ci0(ψ′)αi(ψ′) ∈ Htwist0 (G′;F ′)∨,then γ(he)F(e, h)∨ = 0, or, in other words, the entire image of F(e) via themap F(e, h) in F(he) is taken to zero by the linear functional γ(he). Thecoefficient of ψs+1e0 must be equal on either side of Equation 9.1 and soψs+1e0r∑i=1cis(ψ′)αi(ψ′)(te)F(e, t)∨ = 0.Thus we also have a linear functional in Htwist0 (G′;F ′) that is zero over theimage of F(e0, t).9.2 Edge DetachmentIn this section we define “edge detachment” and explain that conjecturesabout this process imply that certain sheaf collections have no gap.Definition 9.2. Let F be a sheaf on a graph, G, and e an edge. By thee-head detachment of F we mean the sheaf on G that is identical to F exceptthat F ′(h, e) = 0. We define e-tail detachment analogously.Corollary 9.3. Let F be a sheaf on a graph, G, such that htwist0 (F) 6= 0.Then htwist0 (F ′) 6= 0, where F ′ is any head or tail detachment of FProof. Let Ge be the graph G with an edge e deleted, and let Fe be Frestricted to Ge. Any element of Htwist0 (Ge;Fe)∨ that satisfies the conditionα(he)F(e, h)∨ = 0 in the case F ′ is the tail detachment is also an element ofHtwist0 (G′;F ′)∨. Such an element is guaranteed to exist by Lemma 9.1 andso Htwist0 (G′;F ′)∨ and it’s dual space are nonempty.Corollary 9.4. Let F be a sheaf on a graph, and let F ′ be any head or taildetachment of F . Then for i = 0, 1 we havehtwi (F ′) ≥ htwi (F).459.2. Edge DetachmentProof. Since F ,F ′ have the same Euler characteristic, it suffices to prove theinequality for i = 0. We claim that for any positive integer n, if n ≤ htw0 (F),then n ≤ htw0 (F ′); we will use induction on n. The case n = 1 is justCorollary 9.3. Assume that our claim is true for some value of n ≥ 1, andassume that n + 1 ≤ htw0 (F); then htw0 (F ′) 6= 0, and so, by Lemma 8.17there exists G′ a vertex quotient of F ′ of total dimension one less withhtw0 (G′) = htw0 (F ′) − 1. But the if G agrees with F except that it hasthe same vertex values as F ′ (i.e., it equals F except that its value atone vertex is a quotient of F ’s value there of dimension one less), thenhtw0 (G) ≥ htw0 (F)− 1 ≥ n. Hence, by the inductive hypothesis, htw0 (G′) ≥ n,and hencehtw0 (F ′) = htw0 (G′) + 1 ≥ n+ 1.This proves the inductive step.Definition 9.5. Given a sheaf F on a graph G with some edge e, we definethe other space to e, h to bespan{imF(e′, h)|he = he′, e′ 6= e}+ span{imF(e′, t)|te = te′}and define the other space to e, t to bespan{imF(e′, t)|te = te′, e′ 6= e}+ span{imF(e′, h)|he = he′}.These spaces are denoted by other(e, h) and other(e, t) respectively. Wesay that the edge e is internal if imF(e, h) ∈ other(e, h) and imF(e, t) ∈other(e, t).The technical lemma below immediately implies that if F is a minimallygapped sheaf from a sheaf collection closed under quotients, then F is sup-ported on a graph with no leaves. It also shows that if e1 and e2 are twoedges incident to a degree two vertex v by, without loss of generality, theirtail maps then imF(e1, t) = imF(e2, t).Lemma 9.6. Let F be a gapped sheaf on a graph G. If there is somee ∈ E(G) such that e is not internal, then there is a gapped proper subsheafof F .Proof. Without loss of generality, assume imF(e, h) 6⊂ other(e, h). Let F ′be the same as F except F ′(e) = F(e, h)−1(other(e, h) ∩ imF(e, h)). Thisis a proper subsheaf. Any element of α ∈ Htw1 (F) can be restricted toan element of Htw1 (F ′), else dψ would map α|e to something nonzero inimF(e, h)/other(e, h) and no other head or tail map could cancel that out .469.2. Edge DetachmentSince it is a subsheaf, we have htw1 (F) = htw1 (F ′). Any subsheaf of F musthave at least as large an excess as the corresponding subsheaf in F ′, sincetheir only difference is that we made the edge dimension of F ′ smaller. Thisdirectly implies that m.e.(F) ≥ m.e.(F ′) and so F ′ is gapped.Corollary 9.7. Let C be a sheaf collection that is closed under subsheavesand quotients and let F be a T-minimal gapped sheaf in C over a graph G.Then all e ∈ E(G) such that F(e) 6= 0 must satisfydim (F(e)) > 1.Proof. Suppose to the contrary there exists e ∈ E(G) with dim (F(e)) = 1.Let span(a) be the image of F(e, h) with v the vertex mapped to by thehead of e and a ∈ F(v). Let F ′ be the the e-head detachment of F . Bythe previous corollary and theorem 8.9 we know htwi (F ′) ≥ 1 and that F isstable with m.e.(F) = 0. For any subsheaf U of F assign a correspondingsubsheaf U ′ of F ′ that has the same values on each edge and vertex as U ,implying that we have excess(U) = excess(U ′). A subsheaf R′ of F ′ is notmapped to in this way if and only if span(a) 6⊂ R′(v) and R′(e) 6= 0. Forany such R′ let R be the subsheaf of F with R′(E) = R(E) and the valueson the vector spaces also agree except for R(v) = R′(v) + span(a). By thedefinition of excess, excess(R′) = excess(R) + 1. By the stability of F , wehave excess(R′) ≤ 0 unless R is 0 or F . Since R(e) 6= 0, we know R 6= 0.If R = F on the other hand, then by Lemma 9.6 since F is a T-minimalgapped sheaf there is some element of R′(E) that maps to F(he) under asum of the head and tail maps, which contradicts that R′(he) = 0. Thusm.e.(F ′) = 0.Let span(b) be the image of F(e, t) for some b ∈ F(te). Let S1 be thesubsheaf of F that agrees with F on all vertices and edges except S1(e) = 0and let S2 be the subsheaf of F that is zero on all vertices and edges exceptF(te) = span(b). The sheaf S = S1/S2 is a subquotient of F . For anysubsheaf S ′ of S assign a corresponding subsheaf G of F ′ that is equal to S ′on all vertices and edges except G(e) = F(e) and G(te) = S ′(te) + span(b).The excess of S ′ is equal to the excess of G, as G is exactly one dimensionlarger in the vertex space and one dimension larger in the edge space thanS ′. So for any subsheaf of S there is a subsheaf of F with equal excess,implying m.e.(S) ≤ m.e.(F) = 0.Given any α ∈ Htw1 (F ′), let α′ be the restriction of α to all edge spacesexcept the edge space on e. So dF ′ψ(alpha′) is 0 on all vertex spaces except479.3. Alternate Proof of the Twist Trickpossibly on te where it is in span(b). This implies that α′ ∈ Htw1 (S) and soHtw1 (S) ≥ Htw1 (F ′). Thus S is a gapped subquotient of F9.3 Alternate Proof of the Twist TrickOne can also give a proof of Corollary 9.4 by arguing about htw1 directlyrather than htw0 . The nice thing about such a proof is that one can statea very general linear algebra lemma that illustrates the main technique inbroad terms.To explain the lemma, recall that if F is a field and ψ an indeterminate,then to every vector space, W , over F, there is a naturally associated vectorspace, W (ψ) = W ×F F(ψ) over F(ψ). Any vector of W can be identifiedwith one in W (ψ) (via w 7→ w⊗1), and any basis of W as such gives a basisof W (ψ); similarly for any subspace of W . One can reverse this process, to acertain extent. Any vector in W (ψ) is a finite sum of terms wi×fi(ψ), wherewi ∈ W and fi(ψ) ∈ F(ψ) is a rational function in ψ; scaling the vector bythe product of the denominators of the fi(ψ) gives a proportional vector inW [ψ] = W ×F F[ψ], i.e., a finite sum of terms wi × pi(ψ), where the pi(ψ)are polynomials. For any vector in W [ψ] and any c ∈ F, we can substitutec for ψ to get a vector in W ; if w1, . . . , wr are linearly independent vectorsin W [ψ], then w1 ∧ . . .∧wr is a nonzero element of (ΛrW )[ψ], and thereforefor all but at most finitely many c ∈ F, this element is nonzero when wesubstitute c for ψ. It follows that for any subspace of W (ψ), there is a basisof elements of W [ψ], for which we may substitute all but at most finitelymany c ∈ F, we get a subspace of W of the same dimension.Lemma 9.8. Let F be a field, and ψ an indeterminate. Let A,B be subspacesof F, and let J,K be subspaces of A ⊕ B. As usual, let A(ψ) = A ×F F(ψ)be A extended as an F(ψ) vector space, and similarly for B(ψ), J(ψ),K(ψ).LetJ∩ψK = {(j1, j2) ∈ J(ψ) | (j1, ψj2) ∈ K(ψ)},and for c ∈ F letJ∩cK = {(j1, j2) ∈ J | (j1, cj2) ∈ K}.Then for all c ∈ F we havedimF(ψ)(J∩ψK) ≤ dimF(J∩cK) . (9.2)489.3. Alternate Proof of the Twist TrickThe paragraph above the lemma shows that, by considering a basis forJ∩ψK in (A×B)[ψ], that (9.2) holds for all but at most finitely many c ∈ F.The novelty in the above lemma is that it holds for every c ∈ F, without afinite number of exceptions.Proof. We may assume J∩ψK is nonzero. We start by proving that thisimplies that J∩cK is nonzero. So let (j1, j2) ∈ J∩ψK be nonzero; we mayassume that (j1, j2) ∈ J [ψ], and write(j1, j2) =r∑i=0(ji1, ji2)(ψ − c)ifor some ji1, ji2 and r; by dividing by an appropriate power of (ψ−c) we mayassume that at least one of j01 , j02 is not zero. It follows that(j1, ψj2) =r∑i=0(ji1, ψji2)(ψ − c)ilies in K[ψ]. Hence(j01 , ψj02) = (j1, ψj2) + (ψ − c)w,where w ∈ (A×B)[ψ]. Hence(j01 , cj02) = (j01 , ψj02) + (ψ − c)(0,−j02) = (j1, ψj2) + (ψ − c)w′,where w′ ∈ (A×B)[ψ]. In other words,(j01 , cj02)− (ψ − c)w′ ∈ K[ψ],and so(j01 , cj02)− (ψ − c)w′ =s∑i=0(ψ − c)iki,for some ki ∈ K and s. Hence(j01 , cj02) = k0 ∈ K.Hence J ∩c K contains the nonzero vector (j01 , j02).We have shown1 ≤ dimF(ψ)(J∩ψK) ⇒ 1 ≤ dimF(J∩ψK),499.4. The Chain Decompositionand we can use this to establish thatn ≤ dimF(ψ)(J∩ψK) ⇒ n ≤ dimF(J∩ψK)for any positive integer n. There are a number of ways of doing this, at leastone of which is similar to our inductive proof of Corollary 9.4.For example, we can use induction on n. The case n = 1 has beenestablished. Assuming the claim for a particular value of n ≥ 1, assumethatn+ 1 ≤ dimF(ψ)(J∩ψK).Then we know there is a nonzero element, j = (j01 , j02) ∈ J∩cK; let J ′ be Jmodulo the span of j. Thendim(J ′∩cK) = dim(J∩cK)− 1;but since dim(J ′) = dim(J)− 1, we havedimF(ψ)(J′∩ψK) ≥ dimF(ψ)(J∩ψK)− 1 ≥ n.Hencedim(J∩cK) = dim(J ′∩cK) + 1 ≥ n+ 1.9.4 The Chain DecompositionThe main point of this subsection is to show that if F is a stable sheafon a graph, G, and F(e) 6= 0 for a self-loop e about a vertex, then F(e)and its restriction maps to F(v) have a fairly simple description in termsof “chains,” provided that F is not supported entirely on e and v; this isTheorem 9.12 below. This will be useful for what we call “the second twisttrick.” However, we will make a number of additional remarks regardingchains.Let us give some definitions that will allow us to state the main theoremof this section.Definition 9.9. Let H : E → V and T : E → V be two linear maps of vectorspaces over some field, and let i ≥ 0 be an integer. We say that (H,T ) issuperstable if for any finite dimensional subspace E ′ ⊂ E such that E ′ 6= 0we havedim(H(E ′) + T (E ′)) > dim(E ′). (9.3)509.4. The Chain DecompositionBy an (H,T )-chain of order i we mean an alternating sequence of elementsof V and Ec = (v1, e1, . . . , vi, ei, vi+1)(i.e., vj ∈ V for 1 ≤ j ≤ i+ 1 and ej ∈ E for 1 ≤ j ≤ i+ 1) such thatTej = vj and Hej = vj+1.for all 1 ≤ j ≤ i. By the edge sequence of the chain, c, we mean the sequence(e1, . . . , ei), and by the edge space of c, denoted cE , we meancEdef= span(e1, . . . , ei);we similarly define the vertex sequence and vertex space, cV , of the chain,c, based on the vj . If i ≥ 0 and j ≥ 1 are integers with j ≤ 2i + 1, werefer to the j-th element of a chain as its j-th component (which lies in Vor E according to whether j is odd or even). We often drop the “(H,T )”or “order i” from the term chain when H,T or i are understood (or when idoes not matter).A chain superficially resembles a walk in a graph. Also, a chain of order0 is simply an element of V. The last definition we need to state the maintheorem is the notion of a canonical form in the above setting.Definition 9.10. Let H : E → V and T : E → V be two linear maps ofvector spaces over some field. By a chain decomposition for (H,T ) we meana collection of (H,T )-chains such that their edge sequences are mutuallydisjoint and their union comprises a basis for E , and similarly for vertexspaces and V. In analogy with Jordan canonical form, we call also call achain decomposition a canonical form for (H,T ).Example 9.11. The unhappy 4-bundle is a sheaf described by Friedman in[19]. This is a sheaf U over the graph with vertex, v, and two self-loops, e1and e2. The vertex space has dimension 4 and dim(U(e1)) = dim(U(e2)) = 2.Let H and T be the respective restrictions of dh and dt to U(e1). There isa basisα, β for U(e1) for which Hα,Hβ, Tα, Tβ are linearly independent,spanning U(v). In this case Tα, α,Hα and Tβ, β,Hβ are two chains thatgive a canonical form for H,T ; the same is true if α and β are replaced byany two linear combinations of α and β that are linearly independent.Here is the main theorem of this section.519.4. The Chain DecompositionTheorem 9.12. Let (H,T ) be a superstable pair of linear maps E → Vof finite dimensional vector spaces over some field. Then there exists acanonical form for (H,T ).We remark that if V is larger than the span of the images of H and T thenthe canonical form for (H,T ) will necessarily contain a number of chains oforder zero, whose number is precisely the codimension of H(E) +T (E) in V.The rough idea of the proof of the above theorem is to build a canonicalform by starting with any chain of maximal order, and successively addingnew chains that are maximal subject to being linearly independent of theprevious chains.The setting of our notion of canonical form shares a number of othersimilarities with the setting of Jordan canonial form. First, in either settingthere is a polynomial time algorithm to compute a maximal chain, and hencea polynomial time algorithm to compute a canonical form. Second, in eithersetting chains of any order form a vector space. Third, if the chains ofmaximal order form a vector space of dimension d, then exactly d chains ofmaximal order appear in any canonical form. Fouth, the number of chainsof a given order in any canonical form is independent of the particular choiceof canonical form. Fifth, the dimension of chains of a given order and a basisfor this space of chains can be easily calculated once we find a canonial form.Sixth, there is a way to view our canonical form as related to the Jordancanonical form of a certain nilpotent matrix, which we now state.Theorem 9.13. Let (H,T ) be a superstable pair of linear maps E → V offinite dimensional vector spaces over some field. Let T ⊂ V be the span ofthe first elements of the chains in any canonical form. Then1. the first element of any maximal chain lies in T regardless of the par-ticular choice canonical form;2. the spaces H(E) and T are complementary spaces of V, i.e.,H(E) ∩ T = 0, and H(E) + T = V.We remark this implies there is a unique linear map A : V → V suchthat A restricts to TH−1 on H(E) and A maps T to 0; we have that A isnilpotent, and there is a one-to-one correspondence between canonical formsfor (H,T ) given T , the span of the first elements of the chains, and Jordancanonical forms for A.Below we will state some lemmas on (H,T )-chains which will not onlyprove the above theorems, but give more insight into chains.Let us record some simple remarks whose proofs are immediate.529.4. The Chain DecompositionProposition 9.14. Let H : E → V and T : E → V be two linear maps ofvector spaces. Then1. for any integer i ≥ 0, and any integer j ≥ 1 with j ≤ 2i+ 1, the mapthat takes a chain to its j-th component is a linear map; the chains oforder i are a vector space under term-by-term addition and term-by-term scalar multiplication;2. any chain is determined by its edge part;3. if H and T are injections, then any chain of a given order is deter-mined by any of its components.Let us begin with some remarks about superstable pairs.Proposition 9.15. Let (H,T ) be a superstable pair of linear maps E → Vof vector spaces over some field. Then1. H and T are injections, and hence any chain is uniquely determinedfrom any of its components;2. ifc = (v1, e1, . . . , ei, vi+1)is any nonzero chain of order i, then v1, . . . , vi, vi+1 are linearly inde-pendent in V, and e1, . . . , ei are linearly independent in E.In particular, if E and V are finite dimensional, then there is no nonzerochain of order greater than dim(E).Proof. If H were not an injection, then Hu = 0 for some u 6= 0, and then(9.3) would be violated for E ′ being the space spanned by u. Hence H is aninjection. Similarly T is an injection.Let us prove the second part by induction on i. If i = 0, then c consistsof a single element of V, and the claim is clear. Now say that the secondpart holds for a value of i ≥ 0, and let us prove that the same is true for ireplaced with i+ 1. So consider a chain(v1, e1, . . . , ei, vi+1, ei+1, vi+2).If this chain is not the zero chain, then since the value of v1 determinesthe values of the entire chain, we have v1 6= 0. By induction, we knowthat v1, . . . , vi+1 are linearly independent; hence, since T is an injection,539.4. The Chain Decompositionand ej = T−1vj for j = 1, . . . , i + 1, we have that e1, . . . , ei+1 are linearlyindependent. But thenE ′ = span(e1, . . . , ei+1)is i+ 1 dimensional, and henceT (E ′) +H(E ′) = span(v1, . . . , vi+2)must be of dimension at least i+ 2, by (9.3); hence v1, . . . , vi+2 are linearlyindependent. This proves the inductive argument, and hence the secondpart of the proposition holds.We remark that the inductive proof of independence can be viewed asstarting from v1, then proceeding to u1, then v2, then u2, etc. As such theproof can be viewed as zig-zagging up and down, or moving along the com-ponents of the chain. This type of induction will also be used in Lemma 9.18.We now define a canonical form for superstable pairs.Definition 9.16. Let (H,T ) be a superstable pair of linear maps E → V.We see that a sequence, c1, . . . , cm, of chains is successively maximal if1. c1 is a maximum order chain; and2. for each j ≥ 2,cj = (vj1, ej1, . . . , vjij+1)which is of maximum order among all chains for which vj1 is not in thespan of the vj′` ranging over all j′ ≤ j−1 and any ` (i.e., 1 ≤ ` ≤ ij′+1).We say that the a successively maximum sequence, c1, . . . , cm is complete ifthe span of the vertex spaces of c1, . . . , cm is all of V.Clearly a successively maximum sequence of chains exists if V is finitedimensional, since vertex spaces of some chains is not all of V, then we maytake any element of V that is not in this chain as the first element of a newchain.Now we come to some lemmas that culminate in showing that any com-plete sequence of successively maximum chains actually comprise a canonicalform.549.4. The Chain DecompositionLemma 9.17. Let (H,T ) be a superstable pair of maps of vector spacesover a field, F. Let c1, . . . , cm be a sequence of successive maximum (H,T )-chains, withcj = (vj1, uj1, . . . , vij+1).Then we havei1 ≥ i2 ≥ . . . ≥ im.For j = 1, . . . ,m − 1 let c˜j be the chain cj that is truncated to a chain oforder im taking its first 2im + 1 components, i.e.,c˜j = (vj1, uj1, . . . , vim+1).Then for any α1, . . . , αm−1 ∈ F, we have that c1, . . . , cm−1, c is also a se-quence of successive maximum chains, forc = cm − α1c˜1 − · · · − αm−1c˜m−1.Proof. If ij < ij+1 for some j = 1, . . . ,m − 1, then cj+1 is of order greaterthan cj and yet vj+11 is linearly independent of the vj′k with j′ < j and anyk; hence cj is not of maximal order subject to vj1 being linearly independentof vj′k for j′ < j.For the second part of the theorem, c has the same order as cm, andsince the first component of c isvm1 − α1v11 − · · ·αm−1vm−11 ,this cannot be linearly dependent on the vjk with j < m unless vm1 is linearlydependent as well.Lemma 9.18. Letcj = (vj1, ej1, . . . , vjij+1)for j = 1, . . . ,m be a sequence of successively maximal chains. Then1. the subspaceT def= span(v11, v21, . . . , vm1 ) ⊂ Vsatisfies T ∩H(E) = 0;2. the vjk, ranging over all k and j, are linearly independent, and similarlyfor the ujk; and559.4. The Chain Decomposition3. the subspaceH def= span(v1i1 , v2i2 , . . . , vmim) ⊂ Vsatisfies H ∩ T (E) = 0.Proof. We will prove this by induction on m. The inductive step will bevery similar to the proof of Proposition 9.15. Of course, this propositionalso proves almost everything we need for the base case m = 1.If m = 1, i.e., we have a single maximum chain, c1, then by Proposi-tion 9.15 we know that the v1k are linearly independent in V, as are the u1kin E . Since c is a maximum order chain, v11 cannot lie in the image of H(U),for otherwise we could lengthen the chain; similarly for v1i1 . This establishesthe claims about a sequence of successively maximum chain in the lemmain the case where m = 1. Let us establish the situation m ≥ 2 by induction.So assume that for some m ≥ 2 we have established the claims regard-ing any sequence of maximum chains c1, . . . , cm−1, and let us add to thissequence cm, a chain of maximum order subject to vm1 is not in the span ofthe vjk for j < m and all k.We first show that T ∩H(U) = 0 for c1, . . . , cm. Assume, to the contrary,thatα1v11 + · · ·αmvm1 ∈ H(U)for some αi ∈ F that are not all zero; sincespan(v11, . . . , vm−11 ) ∩H(U) = 0,we have that αm 6= 0. By subtracting multiples of the c1, . . . , cm−1 truncatedappropriately, as in Lemma 9.17 from cm, we may assume that αj for j < mare all zero. But then vm1 is in the span of H, and there is a unique way toextent cm “backwards” to a longer chain(vm0 , um0 , vm1 , . . . , vmim+1).We wll now get a contradiction by showing that vm0 is not in the span of thevjk for all k and j with j ≤ m− 1.For the sake of contradiction, assume thatvm0 =∑j≤m−1αjkvjk.Since ∑j≤m−1αij+1vjij+1= vm0 −∑j≤m−1∑k≤ijαjkvjk,569.4. The Chain Decompositionand the right hand side is in the image of T (U), we have∑j≤m−1αij+1vjij+1∈ T (U);but by the inductive assumption, this implies that∑j≤m−1αij+1vjij+1= 0.Hencevm0 =∑j≤m−1∑k≤ijαjkvjk.But vm0 and all the vjk are in the image of T , so we can apply HT−1 to bothsides and conclude thatvm1 = HT−1vm0 =∑j≤m−1∑k≤ijHT−1αjkvjk ==∑j≤m−1∑k≤ijαjkvjk+1.But this contradicts the fact that vm1 is not in the span of the vjk for j ≤ m−1.Hence vm0 would also not be in this span, and we must have T ∩H(U) = 0unless cm is not successively maximum when added to c1, . . . , cm.Next we claim that um1 (assuming that cm is of order at least one) islinearly independent of the ujk with j ≤ m − 1: indeed, if not, then byapplying T to um1 and its expression as a linear combination of the ujk withj ≤ m − 1, we would conclude that Tum1 = vm1 is a linear combination ofsome vjk with j ≤ m− 1, which is impossible.Now, similar to the proof of Proposition 9.15, we show that for ` =2, 3, . . . , im we have that vm` is not a linear combination of the “previousvjk,” meaning vm`′ with `′ < k and the vjk with j ≤ m− 1 (and k arbitrary),and also that the same holds for u replacing the v’s everywhere. Again weuse induction on `, having established ` = 1 as a base case. Indeed, sincevm` is in the image of H, and so are all the vjk with k ≥ 2 and j ≤ m − 1and with 2 ≤ k < `, the same argument as in the previous paragraph showsthat any way for writing vm` in terms of the previous vjk cannot involve anyof the vj1, with j ≤ m, since this would mean that some linear combinationof the vj1 would lie in H. Hence we need show that vm` cannot be written asa sum of the “previous vjk” where k ≥ 2; but then we can apply H−1, and579.4. The Chain Decompositionconclude that expressing vm` as such would imply that um`−1 could be writtenin term of “previous ujk” (meaning with j ≤ m− 1 or j = m and k < `− 1),contradicting the inductive claim. And then the claim for um` instead of vm`follows by applying T .To finish the lemma, we see, by the same argument, that vmim+1 cannotbe written in terms of the previous vjk (meaning either j ≤ m− 1 or j = mand k ≤ im). Now we finish by showing thatH = span(v1i1+1, . . . , vmim+1)has H ∩ T (U) = 0. But here we can use the same argument as used forT ∩H(U) = 0, by truncating c1, . . . , cm−1 from their beginning, rather thantheir end, and using the inductively known fact thatspan(v1i1+1, . . . , vm−1im−1+1) ∩ T (U) = 0.Now we get to the whole point of successively maximum chains.Lemma 9.19. Let c1, . . . , cm be a sequence of successively maximum (H,T )chains that is complete, where (H,T ) is a superstable pair. Then this se-quence is a canonical form for (H,T ).As remarked earlier, complete sequences exist since we can always aug-ment a sequence by adding chains of order zero, consisting of a single elementof V.Proof. By definition, the vertex spaces of the chains span all of V. Similarly,if the edge spaces of the chains do not span all of E , then choose some nonzero in E that is not in this span. Then (T, ,H) is a new chain. But now weclaim that T cannot be a linear combination of elements of the vertex spacesof the chains: indeed, otherwise this linear combination cannot involve anyof the last components of the chains (the vjij+1in the previous notation),for otherwise H would intersect T . But then we could apply T−1 to theequation representing T as a linear combination of vertex space elementsand conclude that is a linear combination of the edge spaces of c1, . . . , cm.Hence the sum of the vertex and edge spaces of the chains are, respec-tively, the entirety of V and E , and by Lemma 9.18, these chains give basesfor V and E and are therefore a canonical form for (H,T ).Proof of Theorem 9.12. Any complete sequence of successively maximal chainsgives a canonical form for (H,T ).589.5. The Second Twist TrickProof of Theorem 9.13. Let c1, . . . , cm be a complete sequence of succes-sively maximum chains of (H,T ), withcj = (vj1, ej1, . . . , vjij+1).Let ` be the order of the chain of maximum order, and let the dimensionof the vector space of maximum order chains be d. Since any chain isdetermined by its first component, if we write down any sequence of at mostd−1 chains, there is always a chain of maximal order whose first componentis linearly independent of the edge spaces of the chains in this sequence. Itfollows that c1, . . . , cd must all be of maximum order. However, then thev11, . . . , vd1 span the space of first components of chains of maximal order. Itfollows that cd+1, . . . , cm are all of order strictly less than `.9.5 The Second Twist TrickThis section shows that the twist trick can give a better result when theedge we are detaching is a self loop. This will give us stronger conditions onminimally gapped sheaves with self loops.Definition 9.20. Given a sheaf F on a graph G and a basis for F(E),b1, . . . , br, we can express any α ∈ Htw1 (F) as d1b1+. . .+drbr with di ∈ F(ψ).If all of the bi are elements of⋃e∈E F(e), we call the sequence (d1, . . . , dr)a representation of α with respect to the sequence (b1, . . . , br). We say Fis full if it satisfies htw1 (F) = 1 and for any nontrivial α ∈ Htw1 (F) andgiven any basis of F(E), the representation of α does not contain 0. Notethat any minimally gapped sheaf H from a sheaf collection closed undertaking subsheaves and quotients is also a full sheaf, since if there exists aα ∈ Htw1 (H) with a representation (d1, . . . , dr) with respect to (b1, . . . , br)and some di = 0 then we may quotient out span(bi) from the edge space ofH to create a new quotient sheaf H′ with maximal excess still 0 and Htw1 (H)containingd1b1 + . . .+ di−1bi−1 + di+1bi+1 + . . .+ drbr,contradicting that H is minimal.Lemma 9.21. Let C be a sheaf collection closed under taking subsheavesand quotients and let F be a full, stable, gapped sheaf in C on a graph G.Suppose G has a self loop l on a vertex v and F is supported on l. Let F˜ beF except F˜(l) = 0, F˜(v) = 0 and any restriction map into F(v) is now thezero map. Then htw1 (F˜) ≥ 2.599.5. The Second Twist TrickProof. Let α ∈ Htw1 (F) be nonzero on l and let ψ and ψ˜ be the full twists forF and F˜ respectively. By definition α is a direct sum consisting of a vectorα|e ∈ F(e)(ψ) for each e ∈ EG. For each vertex u ∈ VG, α must satisfy thecondition that ∑e∈h−1G (u)F(h, e)(α|e) +∑e∈t−1G (u)ψeF(t, e)(α|e) = 0.Fix a basis be1, . . . , bere for F(e) for each edge e. We can write α|e asbe1de1 + . . .+ berederewith de1, . . . , dere ∈ F(ψ). By multiplying out denominators for every edgethough, we may assume that dei ∈ F[ψ] for any edge e and 1 ≤ i ≤ re. Inother words, the dei are polynomials in ψ.Given a f ∈ F, we may define αf ∈ F˜(e)(ψ˜) to be α restricted to alledges except l and for each dei we substitute every instance of ψl with f .Then αf ∈ Htw1 (F˜) since for every u ∈ VG we have∑e∈h−1G (u)F˜(h, e)(a˜|e)−∑e∈t−1G (u)ψeF˜(t, e)(a˜|e) = 0.Let C = (v1, e1, . . . , ek, vk+1) be a chain from a canonical form on F(l).Let S be the span of the ei. We can express α|S ase1γ1 + ...+ ekγkfor γ ∈ F [ψ]. Since C is from a canonical form, (dh − ψldt)α|l restricted tothe span of the vi is the same as (dh−ψldt)α|S . If Θ = {αf |f ∈ F} ∈ Htw1 (F˜)must have dimension at most 1, then so must (dh−ψldt)Θ|E . This impliesψlγ1ψlγ2 − γ1...ψlγk − γk−1−γk = c0c1c2...ckck+1 (9.4)where c0 ∈ F(ψ) and for i = 1, . . . , k + 1 we have ci ∈ F(ψ˜). We also havec1 and ck+1 are nonzero since otherwise F wouldn’t be a full sheaf. Also c0609.5. The Second Twist Trickis nonzero or else stability is violated on the chain. Dividing by c0 givesψlγ′1ψlγ′2 − γ′1...ψlγ′k − γ′k−1−γ′k =c1c2...ckck+1 ∈(F(ψ˜))k+1. (9.5)Soγ′k = ±ck+1γ′k−1 = ±ψlck+1 ± clγ′k−2 = ±ψ2l ck+1 ± ψlcl ± ck−1...γ′1 = ±ψllck+1 ± ψk−1l cl ± . . .± c2.But c1 = ψlγ′1 6∈ F(ψ˜) since ck+1 6= 0.Corollary 9.22. Let G be a graph with a self loop e on a vertex v and let Fbe a minimally gapped sheaf supported on e. Then dim(F(v)) > dim(F(e))+1.Proof. Note dim(F(v)) 6= dim(F(e)) simply by stability. If dim(F(v)) =dim(F(e)) + 1 then F˜ has maximum excess 1 and by the previous lemmahtw1 (F˜) = 2 contradicting that F is minimally gapped.61Chapter 10Homotopy Simplificationsand Vector BundlesIn Lemma 2.4 we gave an alternate definition of the abelian girth usingcertain subgraphs with no leaves. Pruning a graph, or more generally takingsubdivisions can be seen as examples of “homotopy preserving operations”and this view will allow us to define many different ways of transforminga sheaf on a graph while preserving maximum excess and twisted Bettinumbers. This will be useful in our proof of Theorem 7.18.Homotopy operations are also intrinsically interesting, as each sheaf in ahomotopy equivalence class has similar properties. In this section we will notbe extremely formal in discussing homotopy; rather, we shall define someoperations on sheaves and show that they preserve certain sheaf invariants.Later we will describe in rough terms what one might mean by homotopyequivalence and briefly quote theorems in [19] to justify certain theorems.10.1 Some Homotopy OperationsThe following operations are examples of homotopy operations; we will jus-tify the terms later.Definition 10.1. Let F be a sheaf on a graph, G, and let e ∈ EG. Ifu ⊂ F(e) with F(e, h)u = 0 and F(e, t)u 6= 0, we say that u is tail retractible.By the tail retract (at e) of F along u we mean the sheaf F ′ on G such that1. the values of F ′ equal those of F except that F ′(e) = F(e)/U , andF ′(te) = F(te)/W , where U is the span of u, and W is the span ofF(e, t)u;2. the restriction maps of F ′ are inherited from those of F in the naturalway.We similarly define a head retract.6210.1. Some Homotopy OperationsNote that in the above definition, the edge e may be a self-loop.Here we introduce particular notion for the standard notion of a graphcontraction.Definition 10.2. Let G be a graph and let e be an edge. We define thesubdivision of e (in G) to be the graph, se(G), where e is discarded andreplaced with a new vertex and two new edges incident to it; formally se(G)has1. edge set {e1, e2} q EG \ {e};2. vertex set VG q {e}, i.e., VG with a new vertex with the label e;3. the head/tail maps of G along with new maps te1 = te2 = e, he1 = heand he2 = te.We caution the reader that while e is an edge in G, e becomes a vertex inse(G); this (perhaps unusual) convention for the “new vertex” makes edgecontraction in a sheaf quite simple.Definition 10.3. Let F be a sheaf on a graph, G, and let e ∈ EG be anedge for. We define the subdivision of e (in F), also called se(F) to be thesheaf of se(G) (with notation as in Definition 10.2) given by1. the edge and vertex spaces are the same as in F except se(F)(e) =F(e) (note e is an edge in G and a vertex in se(G)) and se(F)(e1) =se(F)(e2) = se(F)(e),2. the restriction maps of se(F) are the same as those in F , except tailmaps of the new edges e1, e2 are both the identity, se(F)(e1, h) =F(e, h) and se(F)(e2, h) = F(e, t).Now we note that the above defined homotopy operations do not changemany of the fundamental invariants of a sheaf.Definition 10.4. We say that two sheaves have isomorphic homology ifthey have isomorphic homology groups and twisted homology groups, andthe same maximum excess.Any such two sheaves also, therefore, have the same Euler characteristicand dual maximum excess. In Subsection 10.4 we show that it is enoughto check that the homology groups are the same, when the two sheaves arerelated by a “functorial procedure,” in a certain sense.6310.1. Some Homotopy OperationsTheorem 10.5. Two sheaves have isomorphic homology if one is obtainedfrom the other by a head or tail retract. (Definition 10.1).Proof. Let F be a sheaf on a graph G with F ′ being a tail or head retracton some edge e. The natural map from F to F ′ also maps subsheaves ofF to subsheaves of F ′ with the same excess. Any member of H1(F) orHtw1 (F) under the same map would also be a member of H1(F ′) or Htw1 (F ′)respectively. Let v ∈ G be the vertex affected the by head or tail retract,and let W be defined as they are in Definition 10.1. Any member of H1(F ′)or Htw1 (F ′) can be mapped to some subspace S of F(E) in a natural way.Then d or dFψ on that subspace must be zero on all vertices except F(v)where it is some element of W (ψ). Thus adding some element of V to theedge space over e in S creates an element of H1(F) or Htw1 (F) respectively.Similarly, given any S subsheaf of F ′ we can create a subsheaf of cf. withthe same excess by adding W to S(v), adding U to S(e) and letting all othervertex and edge spaces remain the same.Theorem 10.6. If F is a sheaf on a graph G and e ∈ EG then F and se(F)have isomorphic homology.Proof. First we note thatdim (se(F)(V )) = dim (F(V )) + dim (F(e))anddim (se(F)(E)) = dim (F(E)) + dim (F(e))and so subdividing a sheaf preserves the excess of the sheaf. Since subdi-vision maps subsheaves of F to subsheaves of se(F), we have m.e.(F) ≤m.e.(se(F)). Let K be a maximizer of se(F). Then K(e) = K(e1) + K(e2)since if not we could restrict K(e) to that subspace and have a sheaf withlarger excess. Thusdim(K(e)) = dim(K(e1)) + dim(K(ee))− dim(K(e1) ∩ K(e2)).Define K′ to be the same as K exceptK′(e1) = K′(e2) = K′(v) = K(e1) ∩ K(e2).The excess of K′ is the same as K and K′ is a subdivision of some sheaf onG, implying m.e.(F) = m.e.(se(F)).We now define a map m : Htw1 (F)→ Htw1 (se(F)). Given α ∈ Htw1 (F) let(c1, . . . , ct) be a representation of α with respect to (b1, . . . bt) where the bi6410.2. A Twisted Homotopy Operationare a basis for F(E) with b1, . . . , br a basis for F(e) for some r < t. Here wemay assume that ci ∈ F[ψG] by multiplying out denominators. We define c′ifor 1 ≤ i ≤ t to be the same as ci except we substitute every occurrence of ψewith ψe1ψ−1e2 . We also define m(α) restricted to the sum of all the edge spacesin Ese(G) \ {e1, e2} has the representation c′r+1, c′r+2, . . . c′t. Let g1, . . . , gtand h1, . . . , ht be the bases for e1 and e2 respectively with gi = hi = bi.The representation of m(α) restricted to e1 is (c′1, . . . , c′t) with respect to(g1, . . . , gt) and the representation of m(α)|e2 is (ψe1ψ−1e2 c′1, . . . , ψe1ψ−1e2 c′t)with respect to (h1, . . . hr). All of this gives a representation for m(α). Forany β ∈ Htw1 (se(F)), we must haveβ|e1 = ψe1ψ−1e2 β|e2or else the twisted differential map would sent β to something nonzero onthe vertex e. Thus m is invertible and a bijection between Htw1 (F) andHtw1 (se(F)).10.2 A Twisted Homotopy OperationHere we define an example of what we will call a “twisted homotopy oper-ation;” this will be formally explained in Subsection 10.4. For now we justdefine the opearation.Definition 10.7. Let F be a sheaf of F-vector spaces on a graph, G. Lete ∈ EG be a self-loop such that if I is the sum of the images of F(e, h) andF(e, t), then for some ψ ∈ F we have that F(e, h) + ψF(e, t) has no kernel.We define the contraction of e (in F), denoted F//e, to be the sheaf in Ggiven by1. the values of F//e agree with those of F , except that (F//e)(he) =F(e)/I and (F//e)(e) = 0;2. the restriction maps of F//e are the same as those in F , except thatthe restrictions taken to F(he) are set to zero.Example 10.8. Let G be the sheaf with a single vertex and a single selfloop. Let F1 be the sturcture sheaf of G, and let F2 be the sheaf whichis the same as the structure sheaf except that the tail restriction (at thesingle edge) is minus the identity. Then the Betti numbers of F1 both equalone; those of F2 are both zero, provided that the underlying field, F, has6510.3. Example: Vector Bundlescharacteristic different than two. (Morally, F2 is essentially the Mo¨biusstrip.) Hence self-loop contraction does not preserve Betti numbers. (Thetwisted Betti numbers of F1,F2 are all zero.)Definition 10.9. We say that two sheaves have isomorphic twisted invari-ants if they have isomorphic twisted homology groups, and the same maxi-mum excess.Any such two sheaves also, therefore, have the same Euler characteristicand dual maximum excess. Similarly to Definition 10.4, in Subsection 10.4we will explain that it suffices to check equality of twisted homology groupswhen one sheaf is obtained from another by a “sufficiently functorial oper-ation.”For completeness we mention the following theorem.Theorem 10.10. Let F be a sheaf on a graph, G. Assume that for someself-loop e ∈ EG we have that F(e, h) and F(e, t) are isomophisms. Then Fand the contraction of F at e have isomorphic twisted invariants.Proof. Easy, using the fact that any square matrix has finitely many eigen-values.10.3 Example: Vector BundlesVector bundles, which we now define, provide an illustrative application ofedge contraction.Definition 10.11. A sheaf, F , on a connected graph, G, is a vector bundleif all its restriction maps are isomorphisms. In this case, all of F ’s valueshave the same dimension, we which call the dimension of the vector bundle.Theorem 10.12. Let F be a vector bundle of dimension d on a connectedgraph, G. Thenhtw1 (G,F) = m.e.(F) = d m.e.(G) = d htw1 (G),htw0 (G,F) = d.m.e.(F) = d d.m.e.(G) = d htw0 (G),andχ(F) = dχ(G).Proof. Any vector bundle remains so after an edge contraction, and a vectorbundle can be contracted along every edge. Hence it suffices to prove thetheorem when G has exactly one vertex. If G has no edges, then the theoremis immediate, and if G has more than one edge we contract along any self-loop.6610.4. A High Road to Homotopy10.4 A High Road to HomotopyThe goal of this subsection is to describe homotopy in simple and fairlygeneral terms. However, some of the theory we will use (the L2 Betti numbercomputation implicit in [18], for example), is not self-contained here. Thissubsection is not essential to the rest of this paper; rather, it unifies andsimplifies the ad hoc constructions of the previous subsections in this section.In topology one defines a notion of homotopic spaces; among otherthings, homotopy preserves certain invariants. Regarding homology groups,topological homotopies usually give “chain homotopies” of the chains fromwhich the homology groups are computed.Ideally we would define a topological notion of homotopy for sheaves,say based on the Zariski topology or e´tale topology, and then show thatthey result in the appropriate chain homotopies. However, we will contentourselves here to view the notion of a homotopy in terms of chains alone.Definition 10.13. Let F be a field, and let u : F → F be an morphism ofa sheaf of F-vector spaces, F , on a graph, G, to itself. We say that u is nullhomotopic if there is a linear map k : F(V )→ F(E) for whichuE = kdF , uV = dFk,where, as usual, dF = dF ,h − dF ,t is the differential map of F . We say thatu is weakly null homotopic if for a full twist, ψ, on G there is a linear mapK : F(V )(ψ)→ F(E)(ψ) for whichuE = KdF ,ψ, uV = dF ,ψK,where, as usual, dF ,ψ = dF ,h − ψdF ,t is the twisted differential map of F(with respect to the full twist ψ).Definition 10.14. Let F ,G be sheaves on a graph, G. Given maps u : F →G and w : G → F , we say that (u,w) is a homotopy pair (respectively,weak homotopy pair) for (F ,G) if uw − 1 and wu − 1 are null homotopic(respectively, weakly null homotopic), where 1 denotes the identity map.We shall use (as is typical) the term “homotopy” and “weak homotopy”in diverse ways; for example, we refer to a morphism u : F → G alone asa (weak) homotopy, provided there exists a w for which (u,w) is a (weak)homotopy pair; we say F and G are (weakly) homotopic if there exists aweakly homotopy pair for (F ,G).As an example we show that if F is a sheaf on a graph G then se(F)and F are homotopic. Let e1 and e2 be the new edges of se(F) as described6710.4. A High Road to Homotopyin Definition 10.3) and let v1 and v2 be the head and tail respectively of ein G. We define the map u : F → se(F) as the following collection of linearmaps1. for any f ∈ EG other than e uf : F(f)→ se(F)(f) is the identity map,2. ue : F(e) → se(F)(e1) ⊕ se(F)(e2) is given by ue(x) = (x,−x) for allx ∈ F(e),3. uv : F(v) → se(F)(v) is the identity map for any v ∈ VG other thanv1 or v2,4. uvi : F(vi)→ se(F)(vi) is the zero map for i ∈ {1, 2}.We now define another map w : se(F) → F as the following collection oflinear maps1. wf : se(F)(f) → F(f) is the identity map for any f ∈ Ese(G) otherthan e1 or e2,2. we1 : se(F)(e1)→ F(e) is also the identity map,3. we2 : se(F)(e2)→ F(e) is the zero map,4. wv : se(F)(v)→ F(v) is the identity map for any v ∈ Vse(G) other thane ,5. we : se(F)(e)→ F(v2) is F(e, t).Checking each of the vertex and edge spaces shows wu is the identity mapon F , implying wu− 1 is null homotopic by setting k from Definition 10.13to be the zero map. The map (uw−1)E is the zero map on each of the edgespaces except (uw − 1)e1⊕e2(x, y) = (0,−x− y). For (uw − 1)V we find thezero map on all vertex spaces except (uw − 1)e⊕v2(x, y) = (−x,F(e, t)(x)).If we let ke : e→ e2 be the identity and define k : se(F)(V )→ se(F)(E) bethe zero map elsewhere, then k satisfies the conditions of null homotopy.Theorem 10.15. Homotopic sheaves have naturally isomorphic homologygroups. Weakly homotopic sheaves have isomorphic twisted homology groups.Recall from [18] that if F is a sheaf on a graph, G, and u : G′ → Gis a morphism of graphs, then the pullback of F via u, denoted u∗F , isthe naturally arising sheaf on G′, i.e., the sheaf whose value at any P ∈VG′ q EG′ equal is just F(u(P )), and whose restriction maps are given by(u∗F)(e, h) = F(u(e), h), and similarly with h replacing t.6810.5. Contracting and Subdividing Gapped SheavesDefinition 10.16. We say that sheaves F ,G on a graph, G, are universallyhomotopic (respectively, weakly universally homotopic) if for every coveringmap u : G′ → G we have that u∗F and u∗G are homotopic (respectively,weakly homotopic).(The notion of a covering map is the usual one, also given in [18].)The operations of retracting and edge contraction (and other such “gen-eral” operations) have a sort of “functoriality” or “commuting with pull-backs” in a way that makes the universality almost immediate from thebasic notion. For example, contracting a sheaf along an edge, e, and pullingit back via a covering map is the same as first pulling back and then con-tracting along all the edges in the preimage of e.Theorem 10.17. Universally homotopic sheaves have isomorphic twistedhomology groups and the same maximum excess.Proof. The twisted homology groups arise from the the homology groups ofabelian covers of the graph. Let F be a sheaf on a graph G. Take a randomGalois cover µ : G′ → G with group Z/qZ with q prime. Friedman shows asan immediate result of Lemma 1.17 in [18] that h1(µ∗F)/p tends to htw1 (F)in probability as p goes to infinity. Thus if F is universally homotopic to asheaf G on a graph, then they have isomorphic twisted homology groups.In [18] Friedman shows that cov(G), the set of covering maps over agraph G, is a directed set using fibre products to create a partial orderingof the covers. Friedman then shows for a sheaf F over G thatm.e.(F) = limφ∈cov(G) htw1 (φ∗F)deg(φ).Hence universally homotopic sheaves have equal maximum excess.10.5 Contracting and Subdividing GappedSheavesThe inverse operation of subdivision is called contraction. Instead of beingdefined for a given edge like subdivision, contraction is defined for a givendegree 2 vertex with two distinct incident edges. Contraction simply replacesthe degree 2 vertex v and the incident edges, e1 and e2, with a single edge.Contraction of a vertex v on a sheaf F is well-defined when v has degree2, and if e1 and e2 are incident upon v, then they are distinct and therestriction maps from F(e1) and F(e2) are both the identity map.6910.5. Contracting and Subdividing Gapped SheavesCorollary 10.18. Let G be a graph and let W be a beaded path or beadedcycle in G. If F is a minimally gapped sheaf on G from a sheaf collectionclosed under quotients then for each vertex v of W that is not the starting orterminating vertex, s−1v (F) is a well defined sheaf and if F ′ is the sheaf pro-duced by contracting every vertex of W besides the starting and terminatingvertices then F ′ is gapped and stable.Proof. Let e1 and e2 be the edges incident upon a degree 2 vertex v in Gand without loss of generality, assume the tail map sends both edges tov. By Lemma 9.6, im(F(e1, t)) = im(F(e2, t)). We may assume F(v) =im(F(e1, t)) since if not we could restrict F(v) to im(F(e1, t)) and have agapped sheaf with smaller total dimension. By a change of basis, and sincethe tail maps are all injections, we may also assume F(e1, t) and F(e2, t) areboth the identity map. Thus s−1v (F) is a well-defined sheaf for every degree2 vertex and is gapped since subdivision produces universally homotopicsheaves. This remains true after repeated contractions of the vertices in Wbesides the starting and terminating vertex. Contraction preserves stabilitysince it preserves the Euler characteristic on sheaves for which it is well-defined, and contraction is a bijection from the set of subsheaves of F forwhich contraction is well-defined to set subsheaves of s−1v (F).We now show a condition under which subdivision of a minimally gappedsheaf produces another minimally gapped sheaf. We say a gapped sheaf Ffrom C is minimal on an edge e if, for any gapped sheaf H from C we havethat dim(F(e)) ≤ (H(e)).Theorem 10.19. Let G be a graph and e an edge of G. If F is a minimallygapped sheaf on G from C, the collection of all sheaves on G, and F is min-imal on an edge e then se(F) is minimally gapped over the sheaf collectionof all sheaves on se(G). If e1 and e2 are the new edges in se(G), then se(F)is minimal on the edges e1 and e2.Proof. Let K be a minimally gapped sheaf on se(G) over the collection of allsheaves on se(G) and suppose dimT (K) < dimT (se(F)). Since e is a vertexof degree 2 in se(G) and K is minimally gapped, by Corollary 10.18 s−1e (K)is a well-defined sheaf on G. We call this sheaf K′.Since subdivision on an edge e simply adds a new edge and vertex withthe same dimension as e we have thatdimT (K′) + 2 dim(K′(e)) = dimT (K)anddimT (F) + 2 dim(F(e)) = dimT (se(F)).7010.5. Contracting and Subdividing Gapped SheavesSince dimT (K) < dimT (se(F)) and dimT (F) ≤ dimT (K′) since F is min-imally gapped, we have that dim(K(e)) < dim(F(e)), contradicting ourassumption.Let H be a gapped sheaf on se(G). By Lemma 9.6 and arguments fromCorollary 10.18, there exists a sheaf I that has the same dimension as Hor less on every edge and dim(I(e1)) = dim(I(e2)) and I(e1, t) and I(e2, t)are both the identity map. Thus s−1e (I) is a well-defined sheaf on G whichwe will call I ′. Thendim(I ′(e)) = dim(I ′(e1)) = dim(I ′(e2))and since dim(cF (e)) ≤ dim(I ′(e)) we have that dim(se(F)(e1)) ≤ dim(I(e1))and dim(se(F)(e2)) ≤ dim(I(e2)).In other words, if a minimally gapped sheaf from the collection of allsheaves results is minimal on all edges, any sequence of subdivisions on thatsheaf also results in minimally gapped sheaf from the collection of all sheavesresults is minimal on all edges.Theorem 10.20. Subdivision and contraction map full sheaves to full sheavesand stable sheaves to stable sheaves.Proof. First we show subdivision can’t map a full sheaf to a sheaf that isn’tfull. Let F be a full sheaf on a graph G with an edge e. Let b1, . . . , brbe a basis for F(e) and b1, . . . , br, . . . , bs a basis for F(E). Let H = se(F)be a sheaf on the graph H = se(G) and let e1 and e2 be the new edgesproduced by the subdivision. Since F(e1) and F(e2) are identical to F(e),let bi1, . . . , bir be the basis the for H(ei) for i = 1, 2 where we identify bi1 = bi.If α ∈ Htw1 (F) has representation (d1, . . . , ds) with respect to (b1, . . . , bs),then(ψe1ψ−1e2 d1, . . . , ψe1ψ−1e2 dr, d1, . . . , dr, dr+1, . . . ds)is a representation of an β ∈ Htw1 (H) with respect to(b11, . . . , b1r , b21, . . . , b2r , br+1, . . . , bs).All elements of the representation are nonzero since the di are all nonzero,and that is true no matter our original choice of basis. If contraction maps afull sheaf to a sheaf that isn’t full, then subdivision maps a sheaf that isn’tfull to a sheaf that is. But from our previous arguments, if any of the di arezero in our representation of α then there is also a zero in our representationof β.7110.5. Contracting and Subdividing Gapped SheavesSubdivision on any subsheaf of F does not change it’s Euler characteristicbut it does not map to all subsheaves ofH. Let v1 be the vertex in H incidentto e1 but not e2 if e is not a self loop in G, and define v2 similarly. Let G bea subsheaf H and let G′ be defined the same of G except G′(e1) = G′(e2) =G(e1) + G(e2) and, if e is not a self loop in G, G′(vi) = G(vi) + imG′(ei, h).We also set G′(e) = G(e1) + G(e2), and we note G′(e) must be a subspace ofG(e). For e a self loop in G, we do not need to change the vertex spaces forthe subsheaf G′ to be well defined. The excess of G′ is at least as large asthe excess of G, since the amount we add to the total edge dimension is atleast as large as the amount we add to the total vertex dimension. G′ musthave excess at most zero though if F is stable, since it can be mapped to bya subdivision of a subsheaf of F .Contraction also doesn’t change the Euler characteristic on any subsheafof a sheaf, and contraction on the subsheaves of H for which contraction iswell-defined maps to all the subsheaves of F .We finish this section by remarking that if F is the reals or complexnumbers, then there is a natural way of viewing a sheaf on a graph as a CW-complex, much in the way that a graph can be viewed as a CW-complex;in this case, retracting and contracting are clearly topological homotopies.However, we imagine that one could do this, say for any algebraically closedfield, say for the Zariski topology (or, perhaps, the e´tale topology if needbe). We shall leave this for future work.72Chapter 11Proofs of Theorems 7.17 and7.18In this section we give the proofs of the main theorems of our paper.11.1 Three Minimal Gapped SheavesWe will now describe three gapped sheaves that will be necessary for themain proofs in this paper. The first sheaf known as the unhappy bundle isgiven by Friedman in [19]. This sheaf is over the minimal figure-eight graphon vertex v with two directed self-loops, e1 and e2. The sheaf U is definedasU(v) = F4, U(ei) = F2 for i = 1, 2withdh =1 0 1 00 1 0 00 0 0 10 0 0 0 , dt =0 0 0 00 0 1 01 0 0 00 1 0 1where these matrices multiply the coordinates of U(E) as a column vectorto the right of the matrix with U(E)’s coordinates ordered as U(e1)⊕U(e2).Friedman also gives Htw1 (U) and shows that maximum excess is zero. Corol-lary 9.7 clearly shows that U is a T-minimal gapped sheaf over the figure-eight graph, B2.We now introduce a T-minimal gapped sheaf over the minimal barbellgraph, though we will not prove its minimality until our proof of Theorem7.18. Consider B, the barbell graph labelled in the following way. Vertex v1has a self loop e1 and vertex v2 has a self loop e2. The edge e0 is directedfrom v1 to v2. The sheaf V which we will call the small barbell hasV(vi) = F4, V(ei) = F2 for i = 1, 2, V(e0) = F4.7311.1. Three Minimal Gapped SheavesBoth restriction maps of V(e0) are the identity map. For i = 1, 2, the re-striction maps for V(ei) are the same as the restriction maps for U(ei) exceptthey map to the F4 over vi. A quick computation shows that Htw1 (V) = 1.Let V ′ be a subsheaf of V with excess equal to the maximum excess of V.The excess of V ′ is at most that of the subsheaf V ′′ of V where V ′′ is definedby V ′′(ei) = V ′(ei) for i = 1, 2 andV ′′(v1) = V ′′(v2) = V ′′(e0) = V ′(v1) + V ′(v2).This can be seen by noting that any increase in vertex dimension is compen-sated for by an increase in the dimension of the edge space of e0. Let thesubsheaf U ′ of U be the same as V ′′ over e1 and e2 and set U ′(v) = V ′′(v1).This subsheaf has the same excess as V ′′. Thusm.e.(U) = m.e.(V) = 0.Given an element of α of Htwi (U) we create an element of Htwi (V) inorder to show that V is a gapped sheaf. The element α is a collection ofvectors, α(ei) ∈ U(ei), such thatdUψ(α(e1)) + dUψ(α(e2)) = 0.Define β as the collection of vectors from the edge spaces of V withβ(e1) = ψe0α(e1), β(e2) = α(e2) and β(e0) = dUψ(α(e1)).It is now easy to verify that β is then a member of Htwi (V).Now we describe W, the T-minimal sheaf over the minimal theta graphT with vertices v1, v2 and edges e1, e2 and e3. Let W = F6 have basisα, β, γ, δ, , ζ. ThenW(e1) = Span < α, δ >, W(e2) = Span < β, >, W(e3) = Span < γ, ζ >,andW(v1) = W/Span < β−γ, δ−, ζ−α >, W(v2) = W/Span < α−β, γ−δ, −ζ > .The restriction maps for any edge are the canonical quotient maps. Com-puting the kernel of the twisted difference map shows that htw1 (V) = 1.To show that m.e.(W) = 0, we describe a degree 2 cover u of T suchthat htw1 (u ∗ W) = 0. Given a graph G and a map a : E(G) → {−1, 1},we construct a degree 2 covering map u : G′ → G in the following way.For any vertex v ∈ V (G), there exists exactly two vertices v−1, v1 ∈ V (G′)7411.2. Proof of Theorem 7.17such that u(v−1) = u(v1) = v. If t, h ∈ V (G) are the tail and head verticesrespectively of an edge e ∈ E(G) then u−1(e) consists of two edges, one fromt1 to ha(e) and the other from t−1 to h−a(e). Now our covering map u on Tcorresponds to the map a defined by a(e1) = 1, a(e2) = 1 and a(e3) = −1.By computation, we have that htw1 (u∗W) = 0. Since htw1 (F) ≥ m.e.(F) forany sheaf F , m.e.(u∗W) = 0. Equation 7.1 implies m.e.(W) = 0 as well.Thus the sheaf is gapped and, since every edge has dimension 2, Corollary 9.7shows it is in fact a gapped T-minimal sheaf.11.2 Proof of Theorem 7.17We can now quickly prove one of the main results of this dissertation, whichwe restate first.Theorem 7.17. If G is a graph on two vertices, no self loops, and at leastfive edges, then there exists a gapped subconstant sheaf on G with maximumexcess 0.Proof. Let R be the graph that is composed of the subgraph T as well astwo new edges, e4 and e5 both from v1 to v2. The sheaf R on R is identicalto V except R(v1) = R(v2) = W ,R(e4) = Span < β − γ, δ − , ζ − α >andR(e5) = Span < α− β, γ − δ, − ζ > .The, by computation, we can find that htw1 (R) = 1. Let a : T (G)→ {−1, 1}be the map defined bya(e1) = a(e2) = a(e3) = 1anda(e4) = a(e5) = −1.Let u be the covering map of T corresponding to a. Then we also have viacomputation that htw1 (u∗R) = 0, showing that R is a gapped sheaf.11.3 Proof of Theorem 7.18Theorem 7.18. For any graph G we haveAbl(G) = min{dim(F(E))|F is a gapped sheaf on G}.7511.3. Proof of Theorem 7.18Proof. First, we prove that there does not exist gapped sheaves supportedon only a cycle or a tree. Then we show that if a graph has Euler charac-teristic −1 than the edge dimension of a minimally gapped sheaf is derivedreadily from the three examples of minimally gapped sheaves discussed ear-lier. Finally we consider the case of a minimally gapped sheaf supported ona graph G of Euler characteristic less than −1. Since the figure-eight graphand theta graph have dimension 2 on all edges, it will be easy to show thatminimality implies the G cannot contain either as a subgraph. We thenargue about the structure of G and use the twist trick on loops to show thatthere exists a smaller gapped sheaf on a barbell subgraph of G.Let F be a sheaf on a graph G and pi : G[Z] → G be the universalabelian covering. Lemma 1.30 from [18] states that Htw1 (F) is non-trivialiff H1(pi∗F) non-trivial. If G is a tree or cycle then G[Z] is a tree and soH1(pi∗F) and Htw1 (F) must both be trivial. Thus any sheaf supported ononly a cycle or graph is not gapped.Now we argue that the previously defined gapped sheaf V on the minimalbarbell graph is T-minimal. Corollary 9.7 implies this so long as V is minimalon the edge e0. By Corollary 9.22, if F ′ is identical to F except F ′(e0) = 0then χ(F ′) ≥ 4 as it is just two self loops. So by stability, dim (F(e0)) ≥ 4,showing V is minimally gapped.As mentioned before, U andW are minimal gapped sheaves on the figure-eight graph and theta graph respectively since each edge on those sheaves hasdimension 2, the minimal dimension possible. By Lemma 9.6, any minimalgapped sheaf is supported on a pruned graph. So Theorem 10.19 impliesTheorem 7.18 in the case the graph has Euler characteristic −1, as any suchgraph is either a figure-eight, theta or barbell graph.Let F be a minimally gapped sheaf from the collection of all sheaves ona graph G and now suppose F is supported on a graph G′ with χ(G′) < −1.If G′ contains a subgraph S that is homeomorphic to a figure-eight graph ortheta graph then 2|ES | < 2|EG′ | ≤ |F(EG)|, but 2|ES | is the edge dimensionof a gapped sheaf on S when S is a figure-eight graph or a theta graphcontradicting the minimality of F .Thus we may assume G′ contains no figure-eight graph or theta graphas a subgraph. So any pruned subgraph of G′ with Euler characteristic −1is a barbell graph. Let B be a barbell graph that is a subgraph of G′ withminimal bar length out of all the barbell graphs that are subgraphs of G′.Let R be the bar of B and let r be the number of edges of R. Let C1 andC2 be the two cycles in B. We also set c1 and c2 to be the number of edges7611.3. Proof of Theorem 7.18in C1 and C2 respectively. If B is the minimal gapped sheaf on B, thendim(B(E)) = 2c1 + 2c2 + 4r.Sincedim(B(E)) > dim(F(E)) > 2|EG′ |we have|EG′ | < c1 + c2 + 2r. (11.1)In other words, there are at most r edges in G′ that are not also in B.There can be no walk from C1 to C2 besides R nor a walk from eitherC1 or C2 to B in G′ else G′ would contain a theta graph. Any walk fromeither C1 or C2 to itself must begin and end with the same edge or else G′contains a theta graph or a figure-eight graph in the case the walk is closed.Suppose there exists a walk not in B but in G′ from Ci to Ci for i = 1, 2.Since, G′ contains no leaves and the only Euler characteristic −1 subgraphsare barbell graphs, this walk contains a cycle as a subgraph and this cycleis not in B. This implies there is a barbell graph in G′ that contains C1 asa subgraph but no other part of B. The bar of this barbell graph has atleast r edges, since the bar length of B is minimal, but then this violatesEquation 11.1. Hence any walk from B to itself must begin and end in R,excluding the starting and terminating vertices of R as those in C1 or C2.If a walk from R to R in G′ has different first and last edges, than G′contains a cycle with at least one vertex in R. This implies there is barbellgraph as a subgraph of G′ whose bar is only a portion of R, contradictingthe minimality of the length of R. Thus any non-backtracking walk from Rto R contains a path P from R to a cycle C3. Let v be the vertex in P andR and let Ri be the path in R from from Ci to v. Set ri to be the numberof edges in Ri, for i = 1, 2, let p be the number of edges in P and let c3 bethe number of edges in C3. By Equation 11.1, p ≤ r. Note P,C3, Ri and Ciform a barbell graph for i = 1, 2. Thus by the minimality of R, ri + p ≥ rfor i = 1, 2 and since r1 + r2 = r this means p ≥ r/2. Thus the only edge ofG′ not in B with one endpoint in B is in P , or else we’d have another pathwith at least r/2 edges and another cycle with at least 1 edge which wouldcontradict Equation 11.1.The same arguments can be repeated from earlier to show there is nowalk in G′ from P and C3 to themselves or to B. Thus G′ is the union of thevertex sets and edge sets of C1, C2, C3, R and P . So the Ci are beaded cyclesin G′ starting and terminating at a degree 3 vertex. By Corollary 10.18 wemay contract each Ci to a self loop on the degree 3 vertex, resulting in a new7711.3. Proof of Theorem 7.18gapped sheaf H supported on a graph H. Note H also contains P and R assubgraphs and the sheaf H is identical to F on P and R. It is also a full,stable gapped sheaf by Theorem 10.20 and because contraction is universallyhomotopic. If si is the self loop that results from contracting Ci then we alsohave that dim(H(si)) = dim(F(ci)) where ci is any edge in Ci. For each sidefine Si to be the cycle composed of si and the vertex vi that si is incidentto. Then by Corollary 9.22, dim(H(si)) + 1 < dim(H(vi)). Any chain onH(si) has edge dimension exactly one less than it’s vertex dimension. Thusa canonical form on H(si) contains at least two chains. Let Fi be the spanof the first elements of the chains from a canonical form on H(si) and Libe the span of the last elements of the chain from the canonical form. SoFi ∈ H(si, t) but Fi 6∈ H(si, h) and Li ∈ H(si, h) but Li 6∈ H(si, t). Let ei bethe only edge incident to si and without loss of generality assume the headmap sends ei to vi. Then Fi + Li ∈ H(ei, h) since H is a full sheaf and soany nontrivial element of the first twist homology group is nonzero on theportion of the edge space that maps to Fi and Li. The dimension of F + Lis at least 4 and so the di is also at least 4.78Chapter 12Subquotients, Submodularityand SupermodularityIn this section, we give a few results that aren’t necessary for the main the-orems of this dissertation but still are of interest. Theorem 8.9 characterizesa minimal gapped sheaf in any collection of sheaves that is closed undertaking subquotients. We now wish to show that there are many such collec-tions; the most basic such collection is the collection of all subquotients ofa given sheaf. We also prove a theorem that can simplify computations onsuch sheaves. Using that theorem, we show there are no gapped subquotientsheaves of the constant sheaf on any graph with only one vertex. After doingthis we show that although excess is a supermodular function, as proven inSection 1.6 of [18], the gap is neither supermodular nor submodular.12.1 Subquotients of a SheafWe wish to show that there are many interesting sheaf collections that aresubquotient closed.Definition 12.1. Let F be a sheaf on a graph, G. We say that a sheaf,F ′, on G is a subquotient of F if there are sheaves F1 ⊂ F2 ⊂ F such thatF ' F2/F1. We denote the set of subquotients of F by SubQuo(F).Lemma 12.2. The set of subquotients, SubQuo(F), of a sheaf F on a graphG is closed under taking subsheaves and quotient sheaves.Proof. It suffices to take F1 ⊂ F2 ⊂ F and consider subsheaves and quo-tients of F2/F1.Let F ′ be a subsheaf of F2/F1. Then it follows that for each P ∈ VGqEGwe have F ′(P ) ⊂ F2(P )/F1(P ), i.e., F ′(P ) consist of a collection of F1(P )equivalence classes in F2(P ); let F ′2(P ) be all the vectors in these classes.We easily check that F ′2, with the natural restriction maps obtained fromF2, forms a subsheaf of F2 that contains F1. Hence F ′, which is clearlyisomorphic to F ′2/F1, is a subquotient of F .7912.2. Simplifications for Stable SheavesThe case of a quotient of F2/F1 is handled analogously.12.2 Simplifications for Stable SheavesTheorem 7.17 is a statement about subconstant sheaves. The reason thatwe consider a larger collection of sheaves, namely subquotients of constantsheaves, is that there are certain theorems, such as Theorem 8.9, regardingwhat one can say about a minimal gapped sheaf (if it exists). The prob-lem with working with subquotients is the values are quotient spaces, andthis can complicate calculations. The following theorem will simplify ourcalculation.Theorem 12.3. Let F be a sheaf on a graph, G, and F ′ ∈ SubQuot(F).Then there exist F1 ⊂ F2 ⊂ F such that (1) F ′ ' F2/F1, (2) F1(e) = 0 forall e ∈ EG, and (3) F2(v) = F(v) for all e ∈ EG.Proof. By definition, F = F2/F1 for some F1 ⊂ F2 ⊂ F .For each e ∈ EG, choose a We ⊂ F2(e) that is a subspace of “representa-tives” of F2(e)/F1(e), i.e., such that We∩F1(e) = 0 and We+F1(e) = F2(e).Then replace the value F1(e) with 0 and the value F2(e) with We, and re-place the restriction maps from e to he or te with zero maps at F1(e), andwith the old restriction maps at F2(e) restricted to We. We easily see thatthis replacement does not change the isomorphism class of F2/F1.Similarly, for each v ∈ VG, we choose a subspace Wv ⊂ F(v) such thatWv+F2(v) = F(v); then we can replace F1(v) and F2(v), respectively, withF1(v) +Wv and F(v).12.3 Single Vertex Graphs and Proof ofCorollary 7.19Now we use several of our results on gapped sheaves to establish that agapped sheaf on one vertex cannot be a subquotient of a constant sheaf.Lemma 12.4. Let G be a graph with exactly one vertex. Let C be the sheafcollection of subquotient sheaves of a constant sheaf on G. Then no elementof C has a gap.Proof. Assume, to the contrary, that C contains a sheaf with a gap, and letF be a T-minimal gapped sheaf. Then Theorem 8.9 implies F satisfiesχ(F) = m.e.(F) = d.m.e.(F) = 0, htw0 (F) = htw1 (F) = 1.8012.3. Single Vertex Graphs and Proof of Corollary 7.19Let VG = {v}, and let EG = {e1, . . . , er}. Theorem 12.3 implies that ifF is a subquotient of the constant sheaf L, for a F-vector space, L, then wemay assume, by passing to an isomorphic subquotient of L, thatF(e1) = A1, . . . , F(er) = Ar, F(v) = B/Cfor some subspaces, A1, . . . , Ar, B,C, of L. Now we gather a few facts aboutthese subspaces.First, Ai ⊂ B for all i, since F is a sheaf, and, of course, C ⊂ B. Second,A1 + · · ·+ Ar + C = B, or else F would have a quotient sheaf whose valueis zero at all the edges and nonzero at v (namely B/(A1 + · · · + Ar + C)),contradicting the fact that d.m.e.(F) = 0.Third, we claim that A1, . . . , Ar, C are linearly independent, i.e., that ifai ∈ Ai for i = 1, . . . , r and c ∈ C, anda1 + · · ·+ ar + c = 0,then a1 = · · · = ar = c = 0. If not, then consider the subsheaf, F ′, of Fwhose values are F(ei) being the (one-dimensional) span of ai for all i, andF(v) = A′/(A′∩C), where A′ is the span of of the ai. Since a1+· · ·+ar ∈ C,we have that F(v) is at most r − 1 dimensional. Hence−χ(F(v)) = dim(F(E))− dim(F(V )) ≥ r − (r − 1) = 1,which contradicts the fact that m.e.(F) = 0. Hence A1, . . . , Ar, C are lin-early independent.But we will easily see that linear independence of A1, . . . , Ar, C impliesthat htw1 (F) = 0. Indeed, fixing a full twist, ψ, on G, we have that elementsof Htw1 (F) are given by tuples (a1, . . . , ar) such that ai ∈ Ai(ψ) and(1− ψ1)a1 + . . .+ (1− ψr)ar ∈ C(ψ).But the linear independence of A1, . . . , Ar, C over F implies the linear in-dependence of A1(ψ), . . . , Ar(ψ), C(ψ) over F(ψ) (this is an easy exercise),and this implies that a1 = · · · = ar = 0. Hence the only element of Htw1 (F)is the zero element; i.e. htw1 (F) = 0. But this contradicts the fact that, byTheorem 8.9, htw1 (F) = 1. Hence our assumption that C contains a sheafwith a gap is impossible.Corollary 7.19. Let G be a graph with χ(G) < 0. Then there exists asubconstant sheaf on G with positive gap. If F is a subquotient of a constantsheaf on G with positive gap then dim(F(E)) ≥ 6.8112.4. Submodularity and SupermodularityProof. By Theorem 7.18, if χ(G) < 0, there exists a gapped sheaf on G. LetF be a constant sheaf on G and let G′ be a Euler characteristic −1 subgraphof G with minimal number of edges. By Corollary 9.7 and the fact thattrees and cycles have no gapped sheaves on them (this was discussed in thebeginning of the proof of Theorem 7.18), a T -minimal sheaf in SubQuo(F)has edge dimension at least 2|E(G′)|. The only Euler characteristic −1graph with two edges is the figure-eight graph consisting of a single vertexand two edges. But Lemma 12.4 immediately implies there exists no gappedsheaves on any subquotient sheaf of a constant sheaf on this graph. Thus ifG is a T-minimal gapped sheaf in SubQuo(F), then the edge dimension ofG is at least 6. All subsheaves of F are in SubQuo(F) no gapped subsheafsheaf of F can have dimension less than 6.12.4 Submodularity and SupermodularityWe say that a function g over sheaves on graphs is supermodular if givenany A and B that are subsheaves of any sheaf F over a graph G we havethatg(A ∩ B) + g(A ∪ B) ≥ g(A) + g(B).Alternatively we say g is submodular if we haveg(A ∩ B) + g(A ∪ B) ≤ g(A) + g(B)for any subsheaves A and B. In this section we give two quick counterex-amples to show the gap is neither submodular nor supermodular.To disprove submodularity let F be the unhappy bundle on the figure-eight graph discussed in the previous section and let A be F restricted to vand e1 and let B be F restricted to v and e2. Since A ∩ B has no edges, itisn’t gapped. The sheaves A and B are only supported on single self loops,and so have no gap as well. But gap(A ∪ B) = 1 since the union is theunhappy bundle.To disprove supermodularity, let G be a single vertex v with four selfloops ei for i = 1, . . . , 4. Let F(v),F(e1) and F(e2) be the same as in theunhappy bundle and also let F(v), F(e3) and F(e4) be another copy ofthe unhappy bundle. Then define A as a the unhappy bundle over v, e1and e2 and B as the unhappy bundle over v the other two edges. Thenm.e.(A ∪ B) = 4 since A is a stable sheaf and A ∪ B has the same vertexspace as A and edge dimension that is larger by four. The sheaves A and Beach have positive gap, but by computing the first twisted Betti number of8212.4. Submodularity and Supermodularitythe union we find that it isn’t a gapped sheaf. Once again, the intersectionisn’t gapped since it is not supported on any edges.83Chapter 13ConclusionThis dissertation has shown several links between the abelian girth of a graphand the standard girth as well as between gapped sheaves and the abeliangirth. In Section 3 we proved Theorem 2.6, which can be seen as a versionof the Moore bound for abelian girth. In Section 4 we proved Theorem2.5, which implied that any multiplicative improvement on Theorem 2.6would also improve the Moore bound. Then in Section 5, we show thatthe bipartite LPS graphs do not have abelian girth so large as to precludeany possibility of improving Theorem 2.6.We also showed in Section 11 thatthe abelian girth of a graph is the minimal dimension of any gapped sheafon that graph. These results might allow for techniques that improve theMoore bound or answer other questions about the girth.Conjectures related to the HNC (see [10]) may potentially be verified byshowing that certain ρ-kernels have vanishing maximum excess, as is done inthe proof of the HNC [18]. These ρ-kernels are subconstant sheaves on twovertices and in Section 11 we demonstrated the existence of gapped subcon-stant sheaves on two vertices. Thus any attempt to prove the conjecturesrelated to the HNC using the first twisted Betti number of the ρ-kernelsshould take into account that the ρ-kernels may be gapped. Though we canstill compute the maximum excess of a gapped sheaf by finding the firsttwisted Betti number of a cover of the sheaf with sufficient degree, this maybe a computationally intensive task. It remains to be shown whether com-puting the maximum excess of a sheaf can be done in time polynomial inthe degree of the sheaf.Though it may be time-intensive to compute the maximum excess of agapped sheaf, thoughout this dissertation we have proved several results thatcan be used to verify that a sheaf is not gapped, in which case computing themaximum excess can be done quickly. Theorem 7.18 implies that any sheafwith total dimension less than the abelian girth of the underlying graph isnot gapped. Lemma 8.21 and Theorem 8.9 show that any gapped sheaf musthave a gapped, stable, faithful sheaf as a subquotient. We have shown thatany gapped sheaf must have dimension at least 2 on any edge and dimensionat least 4 on self loops. Lemma 9.6 shows that any gapped sheaf contains a84Chapter 13. Conclusiongapped subsheaf with every edge being internal.85Bibliography[1] The´orie des topos et cohomologie e´tale des sche´mas. Tome 1: The´oriedes topos. Springer-Verlag, Berlin, 1972. Se´minaire de Ge´ome´trieAlge´brique du Bois-Marie 1963–1964 (SGA 4), Dirige´ par M. Artin,A. Grothendieck, et J. L. Verdier. Avec la collaboration de N. Bour-baki, P. Deligne et B. Saint-Donat, Lecture Notes in Mathematics, Vol.269.[2] Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communications in Contempo-rary Mathematics, 9(04):585–603, 2007.[3] Alon Amit, Shlomo Hoory, and Nathan Linial. A continuous analogueof the girth problem. J. Combin. Theory Ser. B, 84(2):340–363, 2002.[4] M. F. Atiyah. Elliptic operators, discrete groups and von Neumannalgebras. In Colloque “Analyse et Topologie” en l’Honneur de HenriCartan (Orsay, 1974), pages 43–72. Aste´risque, No. 32–33. Soc. Math.France, Paris, 1976.[5] A. L. Biggs and N. G. Boshier. Note on the girth of ramanujan graphs.J. Combin. Theory Ser. B, 49(2):190–194, 1990.[6] Yair Caro and Zsolt Tuza. Improved lower bounds on k-independence.Journal of Graph Theory, 15(1):99–107, 1991.[7] Warren Dicks. Equivalence of the strengthened Hanna Neumann conjec-ture and the amalgamated graph conjecture. Invent. Math., 117(3):373–389, 1994.[8] Warren Dicks and M. J. Dunwoody. Groups acting on graphs. Cam-bridge University Press, Cambridge, 1989.[9] Warren Dicks and Sergei V Ivanov. On the intersection of free subgroupsin free products of groups. In Mathematical Proceedings of the Cam-bridge Philosophical Society, volume 144, pages 511–534. CambridgeUniv Press, 2008.86Bibliography[10] Warren Dicks, SV Ivanov, et al. On the intersection of free subgroupsin free products of groups with no 2-torsion. Illinois Journal of Math-ematics, 54(1):223–248, 2010.[11] David Ellis and Nathan Linial. On regular hypergraphs of high girth.The Electronic Journal of Combinatorics, 21(1):P1–54, 2014.[12] P Erdo˝s, A Re´nyi, and VT So´s. On a problem of graph theory. StudiaSci. Math. Hungar, 1:215–235, 1966.[13] Paul Erdo¨s and Horst Sachs. Regula¨re graphen gegebener taillen-weite mit minimaler knotenzahl. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 12:251–257, 1963.[14] Brent Everitt. Graphs, free groups and the Hanna Neumann conjecture.J. Group Theory, 11(6):885–899, 2008.[15] Joel Friedman. Cohomology of grothendieck topologies and lowerbounds in boolean complexity. 2005. http://www.math.ubc.ca/~jf,also http://arxiv.org/abs/cs/0512008, to appear.[16] Joel Friedman. Sheaves on graphs and a proof ofthe hanna neumann conjecture. April 2011. avail-able at http://arxiv.org/pdf/1105.0129v1 and athttp://www.math.ubc.ca/~jf.[17] Joel Friedman. Sheaves on graphs and their homological invariants.April 2011. available at http://arxiv.org/pdf/1104.2665v1 and athttp://www.math.ubc.ca/~jf.[18] Joel Friedman. Sheaves on graphs, their homological invariants, and aproof of the Hanna Neumann conjecture: with an appendix by WarrenDicks. Mem. Amer. Math. Soc., 233(1100):xii+106, 2015. With anappendix by Warren Dicks.[19] Joel Friedman. Sheaves on graphs, their homological invariants, and aproof of the hanna neumann conjecture: with an appendix by warrendicks. 2015.[20] S. M. Gersten. Intersections of finitely generated subgroups of freegroups and resolutions of graphs. Invent. Math., 71(3):567–591, 1983.[21] Wilfried Imrich. On finitely generated subgroups of free groups. Arch.Math. (Basel), 28(1):21–24, 1977.87Bibliography[22] Wilfried Imrich. Subgroup theorems and graphs. In Combinato-rial mathematics, V (Proc. Fifth Austral. Conf., Roy. Melbourne Inst.Tech., Melbourne, 1976), pages 1–27. Lecture Notes in Math., Vol. 622.Springer, Berlin, 1977.[23] S. V. Ivanov. On the intersection of finitely generated subgroups in freeproducts of groups. Internat. J. Algebra Comput., 9(5):521–528, 1999.[24] S. V. Ivanov. Intersecting free subgroups in free products of groups.Internat. J. Algebra Comput., 11(3):281–290, 2001.[25] Alastair D King. Moduli of representations of finite dimensional alge-bras. The Quarterly Journal of Mathematics, 45(4):515–530, 1994.[26] Nati Linial and Doron Puder. Word maps and spectra of random graphlifts. Random Structures Algorithms, 37(1):100–135, 2010.[27] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combi-natorica, 8(3):261–277, 1988.[28] David JC MacKay and Radford M Neal. Near shannon limit per-formance of low density parity check codes. Electronics letters,32(18):1645–1646, 1996.[29] J. Meakin and P. Weil. Subgroups of free groups: a contribution tothe Hanna Neumann conjecture. In Proceedings of the Conference onGeometric and Combinatorial Group Theory, Part I (Haifa, 2000), vol-ume 94, pages 33–43, 2002.[30] Brigitte Servatius. A short proof of a theorem of Burns. Math. Z.,184(1):133–137, 1983.[31] John R. Stallings. Topology of finite graphs. Invent. Math., 71(3):551–565, 1983.[32] Ga´bor Tardos. Towards the Hanna Neumann conjecture using Dicks’method. Invent. Math., 123(1):95–104, 1996.[33] Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journalof the ACM (JACM), 52(1):1–24, 2005.[34] Alexander Zakharov. On the rank of the intersection of free subgroupsin virtually free groups. Journal of Algebra, 418:29–43, 2014.88
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Abelian girth and gapped sheaves
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Abelian girth and gapped sheaves Izsak, Alice 2015
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Abelian girth and gapped sheaves |
Creator |
Izsak, Alice |
Publisher | University of British Columbia |
Date Issued | 2015 |
Description | The girth of a graph is the length of the shortest cycle in a graph, and the abelian girth of a graph is the girth of the graph's universal abelian covering graph. We denote the abelian girth of a graph G as Abl(G) and show that for d-regular graphs on n vertices with d constant and n growing we have Abl(G) ≤ 6 log_{d-1} n plus a vanishing term. This can be seen as a version of the Moore bound for abelian girth. We also prove Girth(G) ≤ Abl(G)/3, which implies that any multiplicative improvement to the abelian girth Moore bound would also improve the standard Moore bound. Sheaves on graphs and two of their homological invariants, the maximum excess and the first twisted Betti number, were used in the proof of the Hanna Neumann Conjecture from algebra and may be of use in proving several related unresolved conjectures. These conjectures can be proven if certain sheaves called ρ-kernels have vanishing maximum excess. Ungapped sheaves have maximum excess equal to the first twisted Betti number, and it is easy to compute the maximum excess of a given sheaf in the case that the sheaf is not gapped. For general sheaves though, there is no known way of computing the maximum excess in polynomial time. We give several conditions that gapped sheaves must satisfy. These conditions include that a gapped sheaf must have edge dimension at least as large as the abelian girth of the underlying graph. The ρ-kernels are subsheaves of constant sheaves. We prove that gapped subsheaves of constant sheaves exist, implying that finding maximum excess of some ρ-kernels may be computationally difficult. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2016-01-08 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0223486 |
URI | http://hdl.handle.net/2429/56299 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2016-02 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2016_february_izsak_alice.pdf [ 545.08kB ]
- Metadata
- JSON: 24-1.0223486.json
- JSON-LD: 24-1.0223486-ld.json
- RDF/XML (Pretty): 24-1.0223486-rdf.xml
- RDF/JSON: 24-1.0223486-rdf.json
- Turtle: 24-1.0223486-turtle.txt
- N-Triples: 24-1.0223486-rdf-ntriples.txt
- Original Record: 24-1.0223486-source.json
- Full Text
- 24-1.0223486-fulltext.txt
- Citation
- 24-1.0223486.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0223486/manifest