New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Krystal Hintz
Krystal Hintz
GPA 4.0


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Fine arts

This 34 page Class Notes was uploaded by Krystal Hintz on Monday September 7, 2015. The Class Notes belongs to F A 1 at University of Texas at Austin taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/181894/f-a-1-university-of-texas-at-austin in Fine arts at University of Texas at Austin.


Reviews for FIRST


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/07/15
Introduction In 1954 the mathematician AiGi Howson proved that the intersection of two nitely gen erated subgroups H and K of a free group F is nitely generated and has at most 2mn 7 m 7 n 1 free generatorsi His proof involved the topological properties of the Dehn dia grams of groups which like Cayley graphs are diagrams that encode the structure of the generators and relations of a group He wondered whether his bound could be improved and left the question open with the suggestion that an improved bound may be obtained by considering the free generators of the group generated by the two subgroups together 13 Two years later his question was answered when Hanna Neumann improved his bound with the following theoremi Theorem 001 18 Let U and V be nitely generated subgroups of a free group Let N rank U Vranh U m and rank V n ThenN S 2mn72m72n3 2 n and neither U nor V is cyclic She also conjectured that the inequality would still be true without the coefficient of two Henceforth this conjecture has come to be known as the Hanna Neumann Conjecture Her theorem is usually rephrased for convenience in the following form Theorem 002 10 Let H and K be nitely generated subgroups of afree group such that H N K is nontrivial Let d rank H N Kranh H h and rank K h Then d71S2h71k71 Despite the considerable efforts of other mathematicians signi cant improvements on the bound and a rich I t of quot theory uuouudiu the problem the con jecture has remained open for fty years A student of Neumann s Robert Burns used similar methods to improve her result with the bound d S Zhh 7 3h 7 2h 4 for h S h 4 For many years Burnsls bound remained the best numerical bound on the rank of the intersection In 1982 John R1 Stallings developed the notion of locally injective maps called immer sions while teaching a course in group theory at Berkeley His ideas about immersions opened the door to simple efficient proofs of Howson7s theorem that H N K is nitely gen erated and to some theorems of Marshall Hall about nitely generated subgroupsi During this time one of his students SiMi Gersten devised a clever proof of Hanna Neumann7s original inequality using Stallings s new technology Shortly thereafter Stallings and Ger sten published simultaneous papers detailing the new material about the topology of nite graphs and applied to the Hanna Neumann Conjecture Although they failed to prove the Hanna Neumann Conjecture the pair of papers are regarded as in uential contributions to topology and geometric group theory for the extensive material they have spawned 26 Several years later interest in the conjecture was sparked again this time with one of Hanna Neumann s children the mathematician Walter Neumanni Using ideas similar to those of Stallings and Gersten he proved a strengthened version of his mother7s resulti His improve ment stated that the sum of the ranks of all intersections of conjugates for z indexed by dou ble cosets 2 rank H sz 171 maintains the same bound of 2 rank H71 rank K71i He also posed the Strengthened Hanna Neumann Conjecture that the coef cient of two is similarly unecessarily for the sum of conjugates Our aim is to provide a detailed account of the collective body of knowledge required to prove the main results of Howson Stallings Gersten and the Neumannsi But before we can prove these more complicated theorems we must describe a substantial number of de nitions propositions lemmas constructions and conventions that give mathematical structure to the new ideas that arose from the topology of nite graphsi In particular we emphasize the general theory of algebraic topology and geometric group theory which pro vide foundation for the specialized advances accomplished by the theorems abovei Research journals omit prerequisite material however we include such material in the hope that this i 1 i article may serve as an appropriate 39 for pp 1 1 under iaduate interested in the topology of nite graphs and the Hanna Neumann Conjecture Figure l The pullback of covering maps f and g 1 StallingsGersten machinery and the proof of the in equality The main point of this chapter is to understand how the original Hanna Neumann Inequality is proved with the technology of the topology of nite graphs developed by JR Stallings and SM Gersten As we follow the path to the proof of the Hanna Neumann Inequality we will reprove and redevelop some important theory which has broadreaching results above and beyond the proof of the inequality In Chapter 37 these same methods will be used to strengthen the conjecture and in Chapter 4 we state several theorems which have been proved or reproved by others using the Stallings Gersten technology 11 Basic de nitions for graphs The following de nition is modi ed for simplicity from the conventional way to de ne a graph from Serre 23 De nition 111 A graph F consists of a set V vertices of F and a set E edges of T where each edge is associated with either one or two vertices of V called its endpoints The association of an edge with its endpoints is given by a map E a V X V7 e gt gt L 7Te The map de nes the initial and terminal vertices7 Le and te7 of an edge e The distinction between initial and terminal vertices is meaningless until the edge incident to those vertices is given a direction The direction of an edge is its association with an ordered pair of vertices vhvg For each direction7 there exists an opposite direction7 v27v1 For a directed edge e7 let e denote the same edge with opposite direction Note that e and e obey the rule that Le Te and Le 7a A graph in which the edge set consists of directed edges is called a directed graph The notion of directed graphs is a combinatorial idea that is similar to the topological notion of orientation7 which we will de ne in the next subsection De nition 112 24 A map of graphs or a graph morphism is apair offunctions sending edges to edges and vertices to vertices which preserves structure If f F A A is a map of graphs7 then structure preserving means that a speci ed direction of the target graph A induces a direction on lquot7 which f preserves Direction is not an inherent property of a graph7 but if a map is de ned between two graphs7 a direction of the range will determine the direction of the domain Example Structure preserving map Let a1 and 121 be adjacent edges sharing a vertex v1 in lquot7 and let f lquot A A Suppose fa1 a and fb1 12 Suppose further that A is directed in the following way Structure preserving means that if 7a v 71 then for a17 b1 and v1 mapping to a7 b7 and v7 7a1 v1 7121 so that f preserves the linearity of the edges a and b When we say that the domain F inherits a direction from the range A7 we mean that the structure of A pulls back to T such that f is structure preserving We would also like to Figure 2 f lquot A A is a structure preserving map clarify the use of the term label A label refers to a name which is assigned to an edge or a vertex and the label is distinct from the direction of which there are only two choices However when we work with maps of graphs labelling must be consistent with the idea of a structure preserving map Thus we adopt that convention that if f lquot A A is a structure preserving map and A is a graph with labels then T inherits its labelling from A in the manner that it inherits its direction ie if an edge in F maps by f to an edge labelled with an a in A then we pull back the labelling to F and label the edge by a We might have several edges labelled a in lquot This forms a consistent labelling of F as long as all edges labelled a in F are mapped to the edge labelled a in A De nition 113 24 A path p in F is an ntuple of edges e1 en such that 7ei L i1 Lp Le1 and Tp 7en A path is a circuit when Lp 7p We say a path has length n it has n edges Ifrp1 Lp2 two paths p1 and p2 may be concatenated to farm the path 103 101102 where was 4101 and 7103 7102 It is natural to impose an equivalence relation on the set of all paths in lquot Two paths p1 and p2 are called equivalent if they can both be transformed into a smallest reduced path 4 by a nite series of elementary reductions Elementary reduction is the process of deleting a pair of edges of the form e from a path in lquot In a group G rather than a graph this process is equivalent to deleting parts of a word that are of the form a a l for some a in G We can verify that an equivalence relation is generated by elementary reduction of paths with a simple check of re exivity symmetry and transitivity Because each path p consists of nitely many edges p can be transformed in nitely many reductions to a path with no repeated pairs e A path in this form is called reduced It is true that for each equivalence class of paths there is one unique reduced path but that is a lot easier to prove with a little topology 12 Graphs as topological spaces It would be easier to talk about equivalence classes of paths or groups generated by path components if we had a notion of F as a topological space Above we mentioned that the notion of direction had a topological analogue in the notion of orientation To commit to the convention that a graph is a topological object with an orientation we need to rst describe the realization of a graph Realization 10 12 This construction explicitly establishes an abstract graph as a topological object which we will subsequently assume is oriented Construction 121 Let F be a graph and assume that the vertex set V and edge set Ed have the discrete topology Let T be the disjoint union of V and Ed gtlt 01 Now we de ne an equivalence relation m on T e t m e l 7 t 67 0 N 06 67 1 N 75 for all e 6 Ed and t 6 01 Then the realization of F is the quotient space under N D The de nition above may be interpreted as follows The vertex set V is a discrete set of zero cells 00 0dimensional disks and the edge set Ed also has the discrete topologyl Taking the product of the discrete edge set Ed and a closed interval gives a disjoint set of closed onecells 01 ldimensional disksi This creates a set of edges E as we would usually expect 0 and a set them as a disjoint set of closed intervalsl Now that we have a set of zerocells a of onecells 01 we de ne the map 45 which performs the same function as the equivalence relation above For every onecell a in E there is a continuous function 45 which attaches the onecell along its boundary to the set of zerocells 415a 801 A V 45040 L 040 76 since Wail 071 Together the family of functions 4150 make up the entire function 45 aEHV where 8e Kai 01 get sent to the vertices in Vi Then the quotient space formed by the disjoint union of E and V over the identi cations Le m 0 and Te m 1 gives the graph as a topological space namely a l dimensional complex This construction is equiv alent to the realization above just in the terminology of cells and gluing maps rather than strictly via quotient spaces of equivalence classes If we consider the graph F as a cellular or simplicial lcomplex then we may speak of its orientation rather than its direction As with direction the orientation of an edge is determined by a speci c ordering of its verticesl Each edge may be given one of two orientations therefore an orientation of the graph F refers to a speci c choice of orientation on each edge in the edge set The orientation of a graph is consistent with the notion of an orientation of a lcomplexl Note that the orientation of graph is a local property meaning that the choice of orientation for an edge e does not in uence the choice of orientation for any other edge In higher dimensional simplices this is not necessarily true If we replace direction with orientation in the discussion of maps of graphs and paths above the statements are still true We will assume any independent graph F is an ori ented graph and that given any map f lquot A A A is an oriented graph and F inherits its orientation from A We switch from direction to orientation because orientation has a well de ned meaning in topology and henceforth we will regard graphs as topological spaces De nition 122 24 The star of a vertex v E F is the set consisting of all edges incident at v starv e E F Le v or Te v Note that in this de nition all edges are counted whether they are oriented towards or away from v because we are assuming F is oriented However if we do not assume F is oriented then we may write starv e E F Le v These de nitions are equivalent due to the rule ie Te and Le 7a The number of edges in the star of a vertex nu is its valence A vertex v is called isolated if nv 0 and is called a branch point if nv 2 3 24 Homotopy 1 Now as a topological space we may better phrase the equivalences of paths in terms of homotopy We may consider a path p as a map from the interval 0 1 into the graph F p z 0 1 A T where we can partition the interval 0 1 into nitely many subintervals 0 a1 12 an1 such that the image of each subinterval is an edge in the path p0 1 and the image of each ai is a vertex in the path Figure 2 illustrates a path p0 1 mapped into a graph 1quot Consider the set of all continuous path functions p z 0 1 A T where p0 v0 101 These paths which originate and terminate at the vertex v0 are called loops in the topo logical space with basepoint v0 and are equivalent to circuits in the graph based at v0 Since we would like to regard equivalence classes of paths as homotopy classes we de ne the fundamental group of a graph De nition 123 I Let F be a graph and let v0 be any vertex in V De ne the group 7r1Fv0 to be the group whose set of elements consists of all homotopy classes of loops based at v0 7r1Fv0 homotopy classes of loops based at v0 In a topological sense two loops p and q are said to be homotopic denoted p N q if there exists a continuous function f z 0 1 X 0 1 A X such that for all t 6 01 ft0 pt ft 1 qt and f0t v0 f1t The identity element of the group is the constant loop at v0 de ned by pt v0 for all t 6 01 The inverse of an element de ned by the map pt is given by the map p1 7 t I 10 F 1 0 00 0 IV39N as NM a4 fasfa539 NM 7155 0 3 10012 11 a f 11 ql o 0 100 I Figure 3 p 01 A F is a path The dashed line segments indicated the image p0 1 which is not a loop In the case of graphs the notion of homotopic equivalence is analogous to equivalence via elementary reductionl lf In W p2 by using elementary reduction then there exists a nite series of reductions of pairs 61 6 1 1 l l en 63 which reduces p1 and p2 to the same reduced path qr For each of these reductions de ne the map by f 01 gtlt 01 A F 101128 PM 8 where pi is the part of the path associated to the subinterval mapping to 61 6139 and de ne the map by the identity map elsewhere Then fit 1 p1 and fit0 pl 7 61 6 The family of all such maps for all the elementary reductions 6139 61 forms the homotopy F 01 gtlt 01 8 F between p1 and q Then p1 N L N p2 p1 N p21 It should also be noted that because equivalent paths have the same initial and terminal vertices concatena tion of paths is well de ned on the homotopy equivalence classes Homology 121 In addition to homotopy in any graph T we can also talk about its chain complexes and homological structure The free abelian group generated by the zerocells and the oriented onecells of the 1complex F are COOquot Z and C1FZl Another way to denote the free abelian group generated by zerocells77 is ZW for the vertex set and ZEe E 0 for the edge setl An element of the chain group is called a qchain in CI HZ and is a linear combination of oriented qsimplexes with integer coef cients A101A202 nan where Mia 70x0 The symbol 0 just means the simplex a with its orientation reversedl Between the chain groups C1 1 Z and C0 1 Z we de ne the boundary homomorphism 8 C11 Z 7gt C01 Z by 86 76 7 L6 for all 6 E 1 and by extending linearly to the entire free abelian group Since 86 76 7 L6 L 7 76 776 7 L 786 then 86 6 0 86 86 so the boundary map is well de ned Since a graph 1 is a 1complex we may de ne the gymhomology group of 1 as usual by an vZ KeraqImaq1 o q gt 1 Since 1 consists only of zero and onecells Hq1 Z 0 for q gt 1 o q 1 1m8q1 0 H1GZ Ker81 The kernel of the boundary map from C1 1 Z 7gt C0 1 Z consists of1chains with boundary evaluating to zero ie the 1cycles 1n particular if 1 is a tree or a forest disjoint union of trees H11 Z 0 1f 1 is a con nected graph then H11 Z Z Z Z the free abelian group with n generators Note that abelianizing the fundamental group of 1 gives its rst homology group 0 q 0 H0G Z is the free abelian group with rank equal to the number of connected components of the graph 1n particular if 1 is connected H01 Z Z This formal description of the homology of a graph solidi es our description of 1 as a 1complex The boundary homomorphism given by 86 76 7 L makes it possible to smoothly transition from the combinatorial notion of associating edges with an ordered pair of vertices to the notion of gluing edges to vertices along their boundaries By describing the kernel of the boundary map from C1 1 Z 7gt C0 1 Z we have a precise notion of what types of paths are considered circuits The environment of homology re nes the idea that some reduced circuits in a graph can be used to generate other circuits Sometimes the homology of a graph is de ned by the exact sequence 0 i H11 7zli1 01mm 00FZ E H0FZ 0 This is an equivalent de nition of the homology of the graph 1 As an exercise we verify the second de nition using the rst ie that homology implies the sequence above is exact1 1t will suf ce to check exactness at H1 C1 C0 and H0 0 H1 Since C2 0 there are no bounding 1cycles so Ker61 0 Then 61 is injec tive and 1ma 0 Ker61 which implies exactness at H1 0 C1 By de nition H1 Ker811m82 But since C2 0 1m82 0 which implies H1 Ker81 Z1 But since 61 is injective H1 1m61 Now we have 1m61 H1 Ker81 which veri es exactness at C1 0 C0 The image of 81 is the bounding Ocycles But by de nition of H0 the kernel of 1By abusive notion we allow Ci to represent Ci1 Z and Hi to represent Hi1 Z etc 60 is the Ochains evaluating to zero ie the bounding Ocycles Thus lm81 Ker60 which veri es exactness at C0 0 H0 Clearly Ker is all of H0 We must verify that lm80 is also all of H1 ie that 80 is surjective This follows from the de nition of homology The sequence is exact at Ho This completes the exercise Euler Characteristic 1 Another topological invariant of a graph worth mentioning is its Euler Characteristic In later proofs computing the Euler Characteristic will be used as an intermediary step so we state some facts about the Euler Characteristic of a nite graph here for later use xlquot the alternating sum of simplices 0simples 7 lsimplices V 7 E Tank C0 T Z 7 Tank C1F Z m 27lkCk T Z The EulerPoincare formula 27lkHk FZ The alternating sum of Betti numbers Tank Hg T Z 7 Tank H1F Z Since m l in a lcomplex2 Lemma 124 10 FoT a nite gTaph F the following Tesults fTom the above de nitions of the EuleT ChaTacteTistic 1 l M g 0 7 nu UEV 2 Iflquot is connected such that n1 2 0T 3 foT all veTtices then TkH1F Z of bTanch points2 1 Proof 1 Evevl V and Evev n1 2E since edges are counted at the stars of both the initial and terminal vertices then xlquot V 7 E Evevl 7 Evevnv Ev6V2 7 12 2 Tank H1FZ Tank H0FZ 7 xlquot l7 xlquot l7 Evev2 7 nv Evan1 7 2 1 And if n1 2 or 3 for all 1 the summation only counts branch points Hence TankH1F Z of branch points2 l D This little lemma pertaining to Euler Characteristic and branch points will be employed later in the proof of the Hanna Neumann Inequality 2For a discussion of the Euler Characteristic Eulerepoincare formula Betti numbers and a proof of the equality of their alternating sums please see Armstrong Basic Topology p 200 Maps of Graphs Recall that a map of graphs is a structure preserving pair of functions sending edges to edges and vertices to vertices The most important type of map for our purposes is a map which is injective on the star of each vertex This means that if we restrict a map of graphs f F A A to the star of a single vertex v E F then f maps distinct edges originating at v to distinct edges originating at E A Such maps of graphs are important because they yield well de ned preimages of paths in the target graphs Thus we have the following de nition De nition 125 Let f be a map of graphs f lquot A A and let f1 starv A starfv be f restricted to the star of any vertex v E F We call f an immersion f1 starv A starfv is injective for all 1 E F If f1 starv A starfv is also surjective for all 1 E F then the map is a covering map Not every map of graphs is an immersion What happens in the case that f is not an immer sion We restrict our attention to the star of a single vertex v E lquot lnjectivity fails under the condition that two edges e1e2 E starv are mapped to the same edge e E starfv The image fe will have either two distinct vertices a linear edge or one vertex a loop a Suppose that the image of el and eg is a linear edge Without loss of generality ei ther Te1 v L 2 or el and eg both originate at v This is illustrated in Fig ure 3 below Note that the former case does not yield a map of graphs at v For if Tlte1gt v Lei then Mei fv fltilte2gtgt implies that 7fei fv Lfe2i But fa fe2 implies that Lfei iltflte2gtgt men andiltflte1gtgt ii 7feii This is not a structure preserving map on 1 However in the orientation illustrated by F2 the map is indeed structure preserving This is because Le1 v L 2 and fe1 fe2 implies fLe1 fL 2 which implies that Lfe1 Lf 2 Similarly we check that for the terminal edges fe1 fe2 implies f739e1 f739e2 which implies Tf 1 Tf 2 where w v This map is structure preserving b Now consider the case that el and eg map to an edge e with Le Te 6 F1 a loop In either orientation of el and eg this map is structure preserving Consider the case that 7e1 v L 2 as in F1 Because fe1 fe2 this implies Lfe1 Lf 2 and Tf 2 Tfe1 But because Lfe1 Le Te Tf 1 and Lf 2 Le Te Tf 2 there is no discrepancy The case that el and eg both originate at v as ian proceeds similarly Thus for all 1 E F any edge in starv which does not map injectively into starfv is folded onto another edge ie every map of graphs is either an immersion or factors through a folding map The conditions under which a map of graphs which is a fold remains struc ture preserving at a vertex may be summed up more succinctly with the following de nition and lemma De nition 126 A pair of edges e1e2 E T such that Le1 L 2 and e1 e is called admissible This includes pairs with Te1 7e2 If a map f identi es e1 to eg and maps their terminal vertices together then f is called a folding map For f lquot A A with Le1 L 2 and fe1 fe2 f is said to fold the admissible pair e1e2 10 P1 P2 62 61 62 e1 quot v I v z k 7a 2462 461 2a 1 I l 1 V l 7 f f 1 2 f Figure 4 f F1 A A is not map of graphs whereas f F2 A A is an immersion Lemma 127 A map of graphs is either an immersion or folds an admissible pair of edges Proof This lemma is veri ed by the discussion above D The condition 61 f 62 is required because otherwise a map which folds the admissible pair 61 62 introduces a torsion element into the fundamental group of the graph which is free For if 61 62 then gIFHIH Fel 62l Fle e2l which implies that in the fundamental group of the graph F1 the element 62 is its own inverse and therefore has order 2 We may consider the folding map 1quot A Fel 62 as a surjective map Since 61 62 and their terminal vertices are the only parts which are identi ed the folding map is the identity on all other edges and vertices thus clearly surjecting Since a map which is not an immersion must fold some admissible pair then equivalently we may say that a map which is not an immersion must factor through one or more intermediate folding maps 1quot A F 61 62 for an admissible pair 61 62 More formally we have Corollary 128 Given a nite graph F and a surjective map f lquot A A which is not an immersion then f must factor through a folding map gZFHF1F 1 2 11 Proof Since f is not an immersion then at the star of a vertex v E F there exists edges 61 f 62 such that f61 f62i By Lemma 127 f folds the admissible pair 6162 Thus f factors through a folding map 9 and another map h g is the map 1quot A F1 Fel 62 such that for all edges 6 E P not equal to 61 or 62 and all vertices 1 not equal to 761 or 762 96 6 and 91 vi h is a map F1 A A such that f h on all parts other than 61 62 and their terminal verticesi So f k 0 g D Lemma 129 If F0 is a nite graph and f To A A is a map of graphs there exists a nite sequence offoldinq maps FOHF1HF2HHrnr and an immersion h lquot A A such that the composition of sequence offolds and the immer sion is equal to Moreover F and h are unique I 0 f FCLA k2 I 1 x Tn Proof Existence Because f is a map Which is not an immersion by Corollary 128 f must factor through a surjective folding map 91 To A F1 Fel 62 and a map kl F1 A A Where F1 is the image of the surjection 91 and g In o 91 If In is an immersion we are done If In is not an immersion then by again Corollary 128 In folds an admissible pair and must factor through a folding map 92 F1 A F2 and a map 162 F2 A A Where F2 is the image of the surjection 92 k2 o 92 In and 162 o 92 o 91 By induction on the number of edges in To we produce a nite sequence of folding maps and a map kn Which 12 folds no admissible pairsi By Corollary 1 28 kn is an immersioni Thus there exists a nite sequence of folding maps To A F1 A A Tn F and an immersion kn h F A A such that the composition of sequence of folds and the immersion is equal to Uniqueness If f is an immersion then To F and the statement is automatically truer Suppose that f is not an immersion and that there exist two graphs Tn a F2 and two immersions h f h such that h o a f h o M Here a and M indicate the nite sequence of folding maps undergone in an arbitrary orderi Assume that the folding maps 91 and 91 identify distinct admissible pairs in To otherwise we fold and proceed to F1 In particular 91 folds the pair ajak and 91 is the identity on the pair ajaki Denote the identi ed image of aj ak in F1 by amk 92 9272 9171 9 Hail FlawHrplariaHHF 91 A4 92 9272 9271 g gnil FQHHHl gilal gaHHF Yet ajak constitute an admissible pair in F0 so for some folding map 9 F271 A F2 aj and ak are identi ed with image ajkxyi z and y indicate any previous edges that may have been identi ed with either aj or aki Consider the folding of some admissible pair alamthat preceeded 9 Because the two folding maps g il ande are the identity everywhere except at alam and aha16 we may as well assume that the pair aha16 was folded rst and then followed by alami Then by induction on the number of folds preceeding aj ak we assume that aj ak is the rst admissible pair to be folded rede n ing the map 93 To A l39Vli Yet this means 91 and 93 fold the same admissible pair which implies F1 l39Vli Thus we fold the pair aha16 and start over at I ll By induction on the number of edges we continue to match up admissible pairs in the upper and lower halfs of the commutative diagram eventually arriving at Tn lquot D Covering spaces immersions and the paths therein Here we catalogue some properties about paths to be referenced in later proofsi Most of the statements about paths and immersions are completely analogous to the theory that exists for paths and injective maps from one connected topological space to another Proposition 1210 a Each path is equivalent to a unique reduced path Let p e1uien be a path in a connected graph 1quot Suppose p is equivalent to two reduced paths p1 pgi Because p1 p2 there is an edge e in p1 that is not in pgi Because p1 is reduced e 6 p1 implies that e occurs in p since p m In by elementary reductioni Yet p m p2 so by elementary reduction from p to p2 we lose the edge e which does not occur in pgi However if e may be removed by elementary reduction then e cannot occur in p1 which is reduced But e 6 p1 a contradiction b If composition is de ned then the composition of equivalent paths is equivalent Let p m In and g m ql with composition de ned iiei Tp 7p1 Lq Lqli Then poquloquolh WPIOQL For c 7 let f lquot 7gt A be an immersioni c pr and q are paths in F with Lp Lq and fq then p 4 Let p a1 i i i an and let 4 121 i i 12m Since f is an immersion f is injective on the star of each vertex v 6 Ci Consider v Lp Lqi The star of v contains both a1 and 21 Yet because this implies and fa1 fb1i By the injectivity of f on the star of v a1 121 Since a1 b1 7a1 Tbli We proceed by induction on the number of edges in p d fp is a reduced path in F then is a reduced path in A Assume is not reduced Then there exists a pair of consecutive edges 121122 in such that 7 121122 m Since 121 and 122 are consecutive edges in the image of fp and f is an immersion their preimages a1 and a are consecutive in p However p is reduced so the edge pair a1 a2 cannot be consecutive in p otherwise they constitute a pair which contradicts that p is reduced Thus fa1 b1 and ag 122 do not share a vertex because f is a structure preserving mapi But this contradicts that 121 and 122 are consecutivei e f induces an injective map fquot 7r1Fv 7gt 7r1A for each vertex v E F Pick a and 6 7r1Fv such that fquot a fX a and B are represented by two circuits p and q originating at v in Fl Without loss of generality by a we may assume p and q are reduced By d and are reduced Since m by uniqueness By c p 4 so p W q Thus m gt p m g which means f a gt a 5 ie fquot 7r1Fv gt 7r1Afv is injectivei 3 The Path Lifting Property for Immersions Let g 121 i i 127 be the reduced circuit in A originating at representing an equivalence class in fquot n1Fv Then there exists a circuit p a1 i i i an E F originating at v which f maps to 4 Since 4 E f7r1lquotv there is a path pl 6 F originating at v and mapping to 4 Because the induced map is injective p1 is also a reduced pathi Now fX just maps equivalence classes to equivalence classes so all we can say is that fp1 m 4 But by d fp1 is also reduced and by uniqueness of reduced paths fp1 q so p1 yields the p we sought g Let f F 7gt A be afolding map Then f induces a surjective map on fquot 7r1I v 7gt 7r1Afv for each vertex v in G Pick a basepoint v If f folds an admissible pair e1e2 where 7e1 a 7e2 then f does not change 7r1F v and induces an isomorphism of fundamental groups If e1 eg and 7e1 7e2 then f kills precisely the basis element represented by the reduced circuit formed by el and egi All other circuits are preserved and no other elements are introduced so f induces a surjective mapi De nition 1211 The minimal deformation retract of a connected graph F is called its core A contractible subgraph F1 C T which intersects F 7 F1 at only a single vertex is called a branch 3By abusive notation we will occasionally omit the subscript when speaking of induced maps on fundamental group lntuitively7 any connected graph has an important part7 where all the circuits comprising the fundamental group are located If one were to pluck off all the extraneous trees clinging onto the circuits ie7 the branches7 then the graph remaining would be the core Given a base point contained in this core7 its fundamental group would be identical to the fundamental group of the original graph up to conjugacy via choice of basepoint Proposition 1212 For a nite connected graph F the core oflquot has no vertices of valence Proof Suppose not Then the core of F contains a vertex v with valence 1 There is a unique edge e7 such that Te v The path Teeie deformation retracts to the vertex L This contradicts that F is a minimal deformation retract D Proposition 1213 Any connected graph F with basepoint v has a core graph F0 with 7r1lquot7 v a conjugate of 7r1 F0410 where v0 is a vertex in F0 Proof F may be considered the union of two subgraphs7 F1 and F2 where F2 is the union of all branches and F1 is everything else Since F is connected7 any connected component of F2 meets F1 at a single vertex Obtain the core by deformationretracting all components of F2 to the vertex at which they meet F1 This gives the core of 1quot Suppose F has fundamental group 7r1lquotv There exists a nite path p originating at v and terminating at some vertex v0 in the core This path p represents a word w in the free group Conjugating any circuit 4 in F by the path p is the same as conjugating any element a E 7r1lquotv0 by the word w to get w law Hence7 7r1lquotv is conjugate to w 1 o 7T1F U0 o w Furthermore7 any loop based at v0 in the core is not necessar ily reduced Pairs of the form ee occur incident at 1 Hence by elementary reduction7 7r1lquot7 v 7r1lquot07 v0 D The Utility of Immersions and a Few Words About Free Groups and Graphs Until now7 we have only mentioned groups in the context of the fundamental group of a graph with basepoint Yet the Hanna Neumann Conjecture and much of the related material are concerned with nitely generated subgroups of a free group There is no mention of graphs7 graph morphisms7 or even any indication that the best approach to study subgroups of a free group would involve topological spaces at all Although it would be difficult to explain the ingenuity of the mathematicians who developed this theory7 it is a general fact of algebraic topology that the fundamental group of any nite connected graph a lcomplex is free group with nitely many generators In these problems7 it is natural to express any free group as a graph with nitely many closed circuits7 thereby gaining a vast amount of knowledge pertaining to the topology of the space In particular7 we may express any free group on n generators7 F lt a1a2 an gt7 as the fundamental group of the wedge of n circles7 as in Figure 4 below It is also a general fact from topology that the wedge of n circles covers the wedge of 2 circles We shall always call the wedge of two circles A so that 7r1Av0 F2 lt ab gt the free group generated by a and 12 If the covering map is p Ru A Av then the induced map on fundamental groups is injective pi 7r1F u A 7r1 A v and the image p7r1lquotu is a subgroup of 7r1 A 1 Hence any nitely generated sub group of an arbitrary free group may as well be considered as a subgroup of F From here on unless otherwise stated it is useful to assume subgroups of a free group are actually subgroups of F2 a2 b a1 a3 a U0 a4 v0 a5 An A Figure 5 7r1Anv0 Fn and 7r1Av0 F2 The main classi cation theorem for covering spaces gives a onetoone correspondence be tween all the connected covers of a topological space X and all the conjugacy classes of subgroups of 7r1X or even all the speci c subgroups if basepoints are considered How ever when X is a connected graph we can relax the de nition of covering map and instead use the notion of an immersion which only requires injectivity on the stars of each vertex rather than a local homeomorphismi The bene t of using immersions is that the pullback of a diagram of graph immersions represents the intersection of groups which will become an important fact in the next chapter Although this fact is also true for covers which are immersions there is no need to check the condition of surjectivity on the star of each vertex From 1210 e and f we already know that immersions induce injective maps on the fundamental groups of graphs and that there is a version of the pathlifting property which applies to graph immersionsi Now we only need explicit instructions for how to apply these properties The following useful algorithm explains how to write any nitely generated subgroup of a free group as a graph immersing into another graphi Construction 1214 24 Given any nite set of elements in afree group we can represent the subgroup generated by these elements as a graph F and an immersion f lquot A A where A is a graph with 7r1A v F2 for some 1 E A We assume that our free group is the free group on two generators F2 lt a b gt and is represented as the fundamental group of a nite graph A If 11 a2 i i an is a nite set of 16 elements in 7r1 A 1 then each ai is a word in a and b and may be represented by a reduced circuit pi originating and terminating at a vertex v 6 Al Let F1 be a graph consisting of the disjoint union of n arcs 6152 i i i n where each has length equal to the length of pin Recall here that the length of a reduced path is the number of edges it contains The union of these arcs is a forest of trees where each tree has only one branch We form the graph F2 from the identi cation space of F1 with all the initial and terminal vertices of the identi ed at a single vertex ui De ne the map fiFQHA by mapping each i h subdivided arc to pi and by sending u to vi It is clear that edges map to edges and vertices map to vertices because each arc is subdivided appropriately to map to the circuits p E A by construction The image of 7r1F2u in A is the subgroup of 7r1A 1 generated by 11 12 i i i an Although we have produced a map of graphs whose image is the appropriate subgroup we need derive from f an immersion whose image still represents the subgroup f7r1lquot2ui By Lemma 129 we can write f as a nite sequence of folding maps and an immersion h fh09k0quot390940931 FZ rgir4igrklirkri A where each gi is surjective on the star of the vertex u and h is injective on the star of u Recall from li2i10g that folding maps induce a surjection on fundamental group given a basepointi Thus the fundamental group of Pk is the surjective image of gk 0 o 94 o 93 with basepoint gk 0 o 94 o ggui Pk is a nite graph whose image is contained in f7r1lquot2 Thus h7r1lquotk f7r1lquot2 u the desired subgroupi D With this construction we have a method for associating nitely generated subgroups of a free group with actual graphsi Because we always assume that our nitely generated groups are subgroups F2 the generators of our subgroup are written as words in a and 12 Consider as an example the nitely generated subgroup H C F2 given by H lt abab 1b2ab 2 gti Here H has three generators The algorithm in 1214 constructs a graph and an immersion which is structure preserving directly from these words and it is implicitly assumed that the subsequent labelling and orientation of the graph constructed will be consistent with our previous notions of orientation and labelling Now instead of arbitrarily labelling the target graph A and pulling back these labels to TH we have a particular labelling of A namely the labels a and b on either edge The labels that we pull back are precisely the words in a and b with which we have chosen to generate our subgroup Hi By moving along a circuit in T we see that the labels spell out a word that generates Hi For visual examples see Figure 6 or Figure 7 several pages belowi 13 Commutative Diagrams There are several constructions of commutative diagrams involving H and K which are immensely useful toward proving that the intersection of H and K is nitely generated 17 The objects which we will construct in order to make these diagrams commute can be realized as the categorical constructions known as pushouts and pullbacks Although a discussion of category theory is beyond the scope of this paper the reader may check the appendix for the categorical de nitions of pushouts and pullbacks and is advised to visit the book Categories for the Working Mathematician 16 for a thorough discussion of relevant category theory De nition 131 Fullback 10 Let H and K be nitely generated subgroups of a free group Let f and g be graph immersions f z X A Z and g Y A Z which represent these subgroups so that 7r1X u H 7r1Y w K and 7r1Z F2 De ne the pullback ofX and Y to be the set P 9 6 X X Y l f1 yy along with two maps f1 P A Y and g1 P A X such that f1z y y for all z y E P g1zy z for all zy 6 P Note that gy takes place in the target graph Z lntuitively the pullback is con structed of the parts of X and Y which are mapped to the same thing in Z We label X and Y by the names of the edges are vertices to which they are sent in Z by the structure preserving maps f and g Since Z has only a single vertex then every Cartesian pair of vertices zy occurs in the pullback A labelled directed edge connecting two Cartesian pairs 11 yl and 12 yg occurs in the pullback P only if 11 and 12 are connected with the same labelled directed edge e E X as yl and yg are in Y for only under these conditions will the edges in X and Y be mapped to the same image in Z It is clear that the pullback graph is a subset of the Cartesian product of X X Y We may rephrase this condition in terms of two different constructions which result in an object similar to the pullback De nition 132 Product Graph 10 Let X and Y be nite connected graphs The product Q X Y is formed according to the following o The set of vertices of Q is the set of all Cartesian pairs of vertices z 0 Connect a pair of vertices rhyl and 12y2 in the product graph if 1 11 is connected to 12 and y1 is connected to yg 2 11 12 and y1 is connected to yg 5 11 is connected to 12 and y1 yg The product graph is a subset of the Cartesian product De nition 133 Labeled Directed Product Graph Let X and Y be nite connected graphs Assume that the edge sets and vertex sets of X and Y have a labels assigned by mapping X and Y to a common graph Z The labelled directed product Qp ofX and Y is a subgraph of the product graph Q X Y formed according to the following o The set of vertices of Q is the set of all Cartesian pairs of vertices zy such that z and y share the same label 0 Connect a pair of vertices rhyl and zgy2 in the product graph with a labelled directed edge e if 11 is connected to 12 and y1 is connected to yg with the same labelled directed edge e This includes the case that 11 is connected to itself with a labelled directed loop The labelled directed product graph is a subgraph of the product graph and a subset of the Cartesian product Proposition 134 Let XY Z fg f1 and g1 be as in De nition 131 Then the pullback P is a subgraph of the labelled directed product graph Qp Proof It is clear from the de nitions of pullback product graph and labelled directed product graph that the vertex set is identical for P and Q when Z has a single vertexl Pick an edge e in the pullback such that g1e 1 f1e y and e is incident at the vertices u1w1 and u2w2 E P where u1u2z E X and w1w2y E Yl The vertices need not be distinct The images of these four vertices in Z are fu1 fu2gw1gw2 and the images of z and y are and By de nition of pullback gy E Z Thus I and y are connected by the same labelled directed edge as ul and u2 and as wl and wgl Thus e is in the labelled directed product graphl D Figure 6 below demonstrates the difference between the Cartesian product the product graph and the labelled directed product graphl Letls examine a few examples of the pull back In Figure 7 below H1 H2 K1 and K2 are subgroups of the free group on two generators F2 lt ab gtl Therefore the generators of H1 H2 K1 and K2 are words in a and b The graphs PH PHZ PK and PK2 are depicted as immersing in a structure pre serving way into A the graph of F2 The labels and directions of the graphs are determined according to the immersions f and g Because the graphs are labelled and directed we see that the labelled directed product contains the pullbackl In fact the labelled directed prod uct contains all the possible pullbacks we would obtain from choosing different basepointsl Proposition 135 Let the graphs XY Z and P and the maps f f1g and g1 be as in De nition 131 Then the diagram formed by X Y Z and P with maps f f1g and g1 is commutative P L1 Y 91l l9 X A Z Proof Pick any point zy in P such that g1zy z and f1zy yl By de nition of pullback 2 gy in the target graph Zl Pick any point z E X such that gy for some y E Yl Then by de nition of pullback the point z y is in P Since f1 and g1 are projection maps7 f1zy y E Y and g1z y z E X with zy E g1zl Therefore g 0 f1 0 gf1r E Z Similarly if y is a point in Y with gy then the point zy is in P and f o gl 0 gy E Z and the diagram is commutative D F1 A nine1 immersion 101 v17 027 Figure 6 The gure illustrates the Cartesian product of F1 and F2 in pink The dashed lines and solid lines represent the edge set of the graph product of F1 and lquot The solid lines With White arrows represent the edge set of the strong product iiei7 the pullback of F1 and are pictured as verticesi and lquot The vertex set of the labelled directed product graph and the pullback are identical a a a a a FH2 a b 9 K9 A b b b b a a Figure 7 The curly arrow indicates an immersioni H1 lt a7bab 17b2ab 27b3ab 37b4a3b 4 gt and K1 lt a7bab 17b2ab 2 gt i The graph of the pullback is a disjoint union of seven components H2 lt a halfl7 anb 2 lzgab g7 b4a3b 4 gt and K2 lt 127 aba l aQba Q agba g a4ba 4 gti The graph of the pullback has one connected component Proposition 136 Assume the condition of Proposition 135 and suppose that f and g are immersions Then f1 and 91 are immersions Proof Pick a vertex uw E P and two edges 61 and 62 in the star of 61 7 rhyl N P and 62 I2y2 N P Where 11 and 12 are edges in X and y1 and y2 are edges in Y in the stars of u and u7 respectively Assume to the contrary that 61 f 62 and f1 1 16152 Because fl is a Projectiony then f1 1 91 and f1 2 92 91 y2 Consider the images of y1y2 E Z Since 11 yl N P and I2y2 N P are sets of points in the pullback7 then as edges in X and Y f11 9y1 9y2 WW and since f is an immersion7 then 11 I2 Rename 11 and 12 by I so that 61 z y1 P and 62 z y2 N P Since 61 f 62 yl y27 this is a contradiction fl is injective on the star of u7 Similarly7 91 is injective on the star of u7 Thus f1 and 91 are immersions D Proposition 137 Assume the conditions of Proposition 136 and suppose that f and g are surjective on the star of each vertex Then so are f1 and 91 Proof Pick a vertex u E X With image 2 E Z Let I E staru Consider its image E starz E Z Since 9 is surjective at the star of each vertex7 there exists an edge y E starw E Y Where gw 2 and gy By de nition7 this constitutes an edge e in the pullback in the star of u7 Since 91 is a projection 916 I Which implies that there exists an edge in staruw7 namely 67 such that 916 1 Thus 91 is surjective on the star of each vertex u E X Similarly7 fl is also surjective on the star of each vertex w E Y D Propositions 136 and 137 together imply that if f and g are covering maps bijective on the star of each vertex7 then f1 and 91 are also covering maps We introduced the notion of injective maps7 pullbacks7 and product graphs speci cally because of the next theorem 14 Two proofs toward the Hanna Neumann Inequality Theorem 141 10 The pullback of immersions represents intersection That is let the following be a commutative diagram where f and g are immersions P L1 Y all to X A Z Then ifv is a vertex in P 7r1Pv 7r1Xglv 7r1Y7 f1v 22 Proof By Proposition 136 we know that f1 and 91 are also immersionsi We prove the statement by double inclusion Pick an element in 7r1Pvi This element is represented by a circuit p based at v E P 1 y E X X Y l We assume that p is reduced Therefore by li2i10d 91p is reduced in X and f1p is reduced in Yr By de nition of P for all z y E p fltglltz7ygtgt mum fltglltpgtgt amp Therefore fltglltpgtgt is a reduced circuit in based at fglv and is a reduced circuit in gY based at gf1 These are contained in the set of circuits based at a vertex fglv 2 gf1 E Z Therefore p represents an element of 7r1Xglv 7r1 Pick an element in 7r1X 911 7r1f1Y This element is represented by a reduced circuit p based at 2 E Z Because f and g are immersions we apply the PathLifting Property for immersions 12106 to nd circuits 4 E X and T E Y mapping to p by f and g respectively 4 and T are based at the vertices 911 6 X and f1v E Y where fglv 2 gf1vi For every point z in 4 there is a sister point y in T with Thus by de nition of pullback there exists a circuit 8 based at v E P such that f1s T and 918 4 There may be other such circuits mapping to 4 andor T but in any event the circuit 8 represents an element of 7r1Pvi B One of the things to notice about the pullback representing 7r1Xgl 7r1f1 Y f1 is the importance of keeping track of the basepointi Observe the following example Figure 8 Assume that H and K are subgroups of the free group F2 lt ab gti Then we write group elements as words in the generators a and b and we depict their graphs immersing into the graph of the wedge of two circles Note that if we take the basepoint of P to be ul 112 we get a different fundamental group than what we would get from choosing the basepoint ul mg The fundamental groups do not even have the same ranki Moving the basepoint in Y from wl to 112 corresponds to conjugation by the letter 12 Although Tank 7r1Yw1 Tank 7r1 112 we have chosen a different generating set as its basis and as a result its intersection with 7r1X ul may vary wildlyi The pullback graph is especially useful because it simultaneously represents the in tersection 7r1X ul and 7r1 Y wl for any possibly basepoint thus exhibiting all conjugates of the intersection How does one apply TheoTem 141 to nitely geneTated subgToups of a fTee gToup Suppose H is a nitely generated subgroup of a free group From Construction 1214 we know that we may represent the subgroup H as a graph morphism f PH A A with f7r1lquotHu H and 7r1Afu F f can be decomposed into a nite sequence 9 of folding maps and an immersion h F H A A such that h7r1lquot Hgu Hi Since H is nitely generated 1quot is nite Similarly K is represented by an immersion k F K H Al Almost immediately we get a concise proof of Howson7s niteness theoremi Corollary 142 IfH and K aTe nitely geneTated subgToups 0f afTee gToup F then H K 23 f 13 F a K g a ZS gt12 A 101be Figure 8 Let H lt a bab l7 Ingab 3 gt and let K lt a bab l gtl is nitely generated Proof H and K may be represented by nite graphs TH and PK rnapping into A Via irnrnersions f and 97 With 7r1lquotHu H and 7r1lquotKw Kl Construct the pullback P With basepoint u7w for u 6 TH w E FKl Since P 6 TH gtlt Ty l gy7 P is a nite graphl Apply Theorem 1 41 7r1P7 u7 is nitely generated gt 7r1lquotH7 u N 7r1lquotKw is nitely generated gt H N K is nitely generated D 2 The Hanna Neumann Inequality 21 Main result Now we state a main result and prove it in the manner of Gersten7 using some of the de nitions and propositions above Theorem 211 10 Let H and K be nitely geneTated subgToups 0f afTee gToup such that H N K is nontn39vz39al Let Tank H h Tank K k and Tank H N K d Then dilg2h71k71 Proof Although we would like to continue with the assumption that the free groups H and K are subgroups of the free group on two generators7 we will use a graph other than the wedge of two circles to represent F2 Let 9 denote the following graph with basepoint v0 Figure 9 Figure 9 The fundamental group of the graph 9 still has two generators7 narnely7 n1 v0 lt a7 half1 gt Next7 let H and K be the subgroups generated by any nite collection of elements in 7r1Qv0 By Construction 12147 we can represent H and K each as a graph and an immersion f1 PH A 9 1FH7uo H7 WhETE ue 110 g PK A Q 7r1lquotKw0 K7 wheTe gw0 v0 Since f and g are irnrnersions7 and TH and PK share the same target graph 9 construct the pullback P h7 k 6 TH gtlt PK gk such that f1 and 91 are projections and the following diagram commutes P L1 FK all 19 PH L 9 Let P1 be the connected component of P which contains the preimage of the basepoints 1quot u07w0 By Theorem 1417 pullback represents intersection7 so given the basepoint 1quot uo7 we W1P1717 1FH79117 1FK7f117 7V1FH7UO 7V1FK77U0 P1 is not necessarily a core graph Thus let P0 be the core of P1 its minimal deformation retract and let v0 E For By Prop 121 7r1P0 170 is a conjugate of 7r1P1 Therefore rank 7r1P0 170 rank 7r1P1 i1 rank n1H u N 7r1K Also by Prop 1213 f1 n1 130170 is a conjugate subgroup of f17r1P1i in K and like wise 917r1P0 170 is a conjugate subgroup of 917r1P1i 6 Hi Now apply a counting argumenti Because P0 is the minimal deformation retract of P1 either P0 is a single vertex of P0 or by Prop 121 every star in P0 contains at least two vertices By Proposition 136 f1gl f and g are all immersions and so every star in P0 contains no more than 3 vertices Since H N K is nontrivial 2 S nv S 3 for all vertices in For Now we count the number of branch points bri brP0 C brP so brP0 S brPi Also brP C brH X K since the pullback is a subgraph of the product PH gtlt PKi Thus brP0 S brPH brlquotKi We restate an earlier lemma Lemma 124 10 For a nite graph P the following result from the above de nitions of the Euler Characteristic 1 M g 0 7 nu vEV 2 If P is connected such that no 2 or 3 for all vertices then rank H1PZ of branch points2 1 Since the rank of H N K equals the rank of H1 H N K Z and the pullback graph rep resents this intersection by De nition 1 22 rank H N K rank of 7r1P1i rank 7r1P0 170 brP0i021 S bTFH gtlt bTFK2 1 And since rank of H 71 brPH2 and rank of K 71 brPK2 ranhH K7l lt 2ranhH71 rankKil D What makes Gersten7s proof so satisfying is its use of the Euler characteristic The idea of summing the edges vertices and faces of polyhedron dates back to the early 1700s when Leonhard Euler developed some of the fundamentals of early topology The relationship between the Euler Characteristic of a simplicial complex and the alternating sum of the ranks of chain complexes the EulerPoincare formula is also a well understood concept in 26 homology theory The bound 2 ranhHil ranhKil essentially results from constructing a product graph Where the Euler Characteristic is multiplied in the product exactly What one would expect This is also Why Hanna Neumann s conjecture is so unexpectedi Without the coef cient of 2 the clean multiplication of Euler Characteristic is no longer applicable Thus the Hanna Neumann Conjecture became the following Conjecture 212 1910 Let H and K be nitely generated subgroups of a free group such that H K 239s nontrivial Let rank H K d let rank H h and let rank K h Then d71 h71k71 3 Walter Neumann s Strengthened Inequality and Con jecture 31 Another proof of the Hanna Neumann Inequality Walter Neumann strengthened both the inequality and the conjecture In doing so he provided an alternate yet still similar proof of the inequality We Will give his proof of the inequality his proof of the strengthened inequality and his statement of the strengthened conjecture We reprove the Hanna Neumann Inequality in the method of Walter Neumann because it elucidates his proof of the strengthened inequality Interestingly Walter Neumann also provided a probabilistic argument to support the claim that the conjecture is most likely true We Will also describe this argument Lemma 311 21 For any nitely generated subgroup H of a free group let I H denote the graph with 7r1I Hv H Then if I H has core I HO 2ranh H 71 Z starv 7 2 Proof rank H71 xI H 7 E7V 1 1 E Z27E Z2 26quot DEFH l E 11starv 7 2 And since xI H xI HO the same is true as 1 runs through only the vertices of the core The sum is restricted to vertices in the core to ensure niteness D We now reprove the Hanna Neumann Inequality Theorem 312 21 Let H and K be nitely generated subgroups of afree group such that H N K is nontrivial Let rank H h and rank K h rank H N K d Then 4719071 k71 Lemma 313 Let H C F let the graph An of Fn be the wedge of n circles and let f PH 7 An be a covering map of graphs representing H Then the vertex set of F is in a one to one correspondence with the set of right cosets of H Hg l g E Fn Proof Lemma 313 Let u be a vertex in TH and suppose F has basepoint uo Then the path p uo u projects to a closed circuit in An Which corresponds to a word w E Fn Thus for any element h E H Which is represented by a circuit a 6 TH a p has image fa p Which corresponds to the word hw E Fn This gives the coset Hw Let Hw be a coset of H For any element h E H h is represented by a circuit a 6 TH and the word w lifts to the path u0u originating at uo and terminating at some vertex u Thus there exists a vertex 1 corresponding to the coset Hw 28 D Proof Theorem 3 12 Assume H and K are subgroups of F2 Let F denote the wedge of two circles with basepoint v0 such that 7r1Fv0 ng Let TH and PK denote the topological covers of T such that f PH 7 F 7r1FHu0 H where fu0 v0 9 PK 7 F 7r1FKw0 K whereg uo v0 and such that f and g are locally bijective covering mapsi Let P H Ki Then the cover of F corresponding with the subgroup P C F2 is also a cover of TH and FKi Denote this space by Pp and equip it with the projection maps 91 FF 7 TH and f1 Pp 7 PK which may be written together as the projection p FF 7 TH gtlt FKi For FHlquotK and Pp denote their cores by THO TKO and FPO We claim that 91 and f1 are injective on the vertex set That is if 7r f1gl then 7r Pp 7 TH gtlt PK 7r FPO 7gt THO gtlt TKO are both injectivei For the time being assume this is true Because of injectivity for any vertex 1 such that 7rv uw in F170 3ta rv S 3ta ru for the smaller of H and K since no edges are folded in the map Thus 3ta rv 7 2 S sta39r 7 2sta39rw 7 2 since in the core of a nite graph all vertices have valence of at least 2 Now we apply Lemma 4ilili 3ta rv 7 2 S sta39ru 7 2 3ta rw 7 2 gt 2 Tank P 7 l Z staMU 7 2 verpo S E stmquot 7 2sta39rw 7 2 uEFHOwEFKO Z staru 7 2 Z starw 7 2 uEFHO WEFKO S E staru 7 2 Z starw 7 2 ueFH wEFK 2TankH 712TankK7l And dividing by two gives Tank H N K 7 1 S 2TankH 7 1TankK 7 1 To see why 7r is injective on the vertex sets assume the contrary Then 7ru1 7ru2 and ul ug for some vertices ul ug 6 Pp Since TH and PK are covers then by the lemma there exists cosets Pul Pug which are subsets of H with u1u2 E H corresponding to these verticesi If 7ru1 7ru2 u E H then this vertex u also corresponds with a coset Hu however this coset is a subset of F2 with u 6 F2 Just as the vertices ul and ug are sent to u with the map 7r the cosets image is also de ned by a map TrIHui7gtHuKu il2 However the images of ul and ug both represent the same coset of H and 1K Thus they represent the same coset of H N Ki This contradicts noninjectivityi But this means that Pul and Pug are in the same coset of F2 and are hence the same coseti 29 The following example Figure 10 illustrates the proof Example The path terminating at the vertex ui corresponds with the coset Hula The image of ug and ug under fl is the vertex u in TH and u corresponds with the coset Hut The other vertex in TH corresponds with the identity coset Hi We assume that the ver tices ug and ug in the schematic are mapped noninjectively to u However they are both representatives of the same coset of Hui Likewise they represent the same coset of K and therefore of H N Ki Thus in this example we see how assumed noninjectivity actu ally implies that ug and ug are in the same coset of P H K contradicting noninjectivityi Schematic of coset decomposition c F2 Figure 10 Illustration of subgroups and cosets This proof is very similar to the one given by Gersteni The difference is that Walter Neumann chose to represent the graphs of H and K as topological covers of the wedge of two circles whereas Gersten chose to represent them as graphs which immerse into a particular blowup of the wedge of two circles the graph A As a result Neumann employed a different counting argument than Gersten but with the similar idea of summing valences to bound the rank Neumann s proof is slightly more convenient because his use of covering spaces rather than immersions removes the need to prove that the pullback of immersions represents intersectioni However this idea can7t be sidestepped in the proof of the strengthened inequalityi 32 Walter Neumann7s Strengthened Inequality Let H and K be nitely generated subgroups of a free group such that H N K is nontriviali Walter Neumann suggested that not only can we bound the rank of the intersection H N K from a particular basepoint we can bound the total rank of all intersections y lHy N 30 2 1K2 21 Although conjugates are only identical for normal subgroups conjugacy is an automorphism which preserves rank so it is more convenient to x H and consider instead the total rank of the intersections H N 2 1K2i To see that y lHy 2 1K2 N H N I le 1 conjugate by y Thus when I zy l Tanky 1Hy N 27le Tank H N I IKI for z zy The practical method we7ve developed for determining the rank of an intersection of sub groups is to compute the pullback of the immersions andor covering maps which represent these subgroupsi We seek to use this same method however there are several questions which require attention 1 Does every possible intersection of the form H N I le occur as a component of the pullback If so what is the most ef cient way to count the rank of all components in the pullback Counting intersections of the form y lHy I le or H 11 le will not suf ce We will answer the second question rsti Consider the example of Figure 11 TH Figure 11 The pullback of covering maps f and g In the example changing the basepoint in TH or PK corresponds with the conjugating the subgroup H or Ki The conjugate subgroup a lHa is distinct from the subgroup H and similarly the conjugate subgroup a lKa is distinct from the subgroup Ki However notice that in the pullback graph the intersections H K and a lHa a lKa represent the same component with different choice of basepointi Distinct conjugates intersect to form identi cal subgroupsi This means that if we sum the ranks of the intersections y lHy I le 31 as I and y run through distinct conjugates of H and K some components in the pullback will be counted more than once Summing intersections of the form H N 1 K1 as 1 runs through distinct conjugates of K is similarly problematic In order to correctly compute the rank of the entire pullback we seek a summation technique that will count the conjugates of the intersections rather than the intersections of the conjugates Proposition 321 21 If 1 runs through a set of double coset representatives then each component in the pullback without regard to basepoint is counted exactly once Proof If y E KIH7 then H N I le and H N y le are conjugates Since y hzh this implies z h lyh l7 so H zile H h 1yh 1 1Khilyhil H hy 1kKk 1yh 1 H m hy l yh l which is a conjugate of h 1H hyileh 1h H h 1hy 1Kyh 1h H yile If we let I run through a set of double coset representatives KIH7 then H N I le N H N y le means that only one conjugate representative will be counted7 resolving the problem above D Now we have an ef cient and precise way to compute the total rank of all components in the pullback We answer question 2 Proposition 322 21 The pullback Pp contains precisely the disjoint union of the con jugates H N I IKI as 1 runs through the set of double coset representatives KIH Proof The vertex set of TH represents the set of right cosets Hy7 y E F27 and similarly for K Recall that Walter Neumann s technique of producing TH and PK is to take the appropriate covering maps f TH A lquot7 f7r1lquotHu0 H7 where fu0 v0 g PK A lquot7 f7r1lquotKw0 K where gw0 v0 This is important That TH and PK are covers means f and g surject at the star of each vertex This guarantees that if e E starv then e E starv We can translate this to the language of groups and cosets Because the vertex set of the graph represents the right cosets Hy for y 6 F2 then the component of the pullback containing the cosetvertices HyKz also contains the cosetvertex Hsz 1 Thus any component of the pullback contains a cosetvertex of the form H7 We claim that all basepoints of this component are indexed by the same double coset HIK Consider any component of Pp with basepoint the cosetvertex HKz 6 Pp The fundamental group of this component consists of all loops originating at H7 As elements of F2 these loops are the words 2 such that 32 H2 H and K12 Kzi These are precisely the words 2 such that 2 E H and 2 I lhz for some 16 ie when 2 E H N I lei Take any other basepoint H Ky in the same component of Ppi It is connected to H K1 in Pp if and only if there exists a 2 in F2 such that H2 2 and Ky K12 for some h This happens only if y hzz for some 16 which happens when y E KzH since 2 6 Hi Thus the components of the pullback represent the disjoint union of the conjugates H N I le which are indexed by I as 1 runs through the set of double coset representatives KzHi D We now state Walter Neumann s main result Theorem 323 21 Let H and K be nitely generated subgroups of afree group such that H N K is nontrivial Then ranhH zile 7 l S 2ranhH 7 lranhK 71 KrHe KF2 H Proof Let PHPKPpfgp etc be as in Theorem 312 We recall the following from Section 2 7MB 1X791v WHO71611 which under the conditions of the theorem becomes 7V1FP739U 7r11 H79139U 1FK7 f1v We now cite Proposition 322 Given the proposition we have that Pp is the disjoint union of all the conjugates H N I le as 1 runs through the set of double coset representatives KzHi We can further restrict our attention to just the core of Pp which is the disjoint union of all the cores of the noncontractible components of PK gtlt PHi For if a path in PK deformation retracts to its core then by the path lifting property of covering spaces this path lifts to path in Pp which also deformation retracts to its core meaning the contractible paths do not contribute anythingi Now we apply Lemma Silil to the core of this disjoint union PpO and proceed exactly as in the previous theorem 2 rank H nK 71 Z starv 7 2 S E staru 7 2 starw 7 2 uEFHOw61quotKO Z staru 7 2 Z starw 7 2 uEFHO WEPKO S E staru 7 2 Z starw 7 2 ueFH wEFK 2ranhH 7 l2ranhK 71 And again dividing by two gives rank H N K 7 l S 2ranh H 7 lranh K 7 1 Now we have a strengthened version of the Hanna Neumann Inequality 33


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.