AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks
About this Title
Joel Friedman, Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, CANADA, and Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, CANADA.
Publication: Memoirs of the American Mathematical Society
Publication Year:
2015; Volume 233, Number 1100
ISBNs: 978-1-4704-0988-3 (print); 978-1-4704-1968-4 (online)
DOI: https://doi.org/10.1090/memo/1100
Published electronically: May 19, 2014
Keywords: Graphs,
sheaves,
Hanna Neumann Conjecture,
homology,
Galois theory.,
Intersection of free subgroups,
graphs,
skew group ring,
sheaves,
Hanna Neumann conjecture,
homology,
Galois theory.
MSC: Primary 20E05, 05C10, 55N30, 18F20; Secondary 20E08, 05C05, 05C50, 18F10, 18F20, 14F20
Table of Contents
Chapters
- Preface
- Introduction
- 1. Foundations of Sheaves on Graphs and Their Homological Invariants
- 2. The Hanna Neumann Conjecture
- A. A Direct View of $\rho$-Kernels
- B. Joel Friedman’s Proof of the strengthened Hanna Neumann conjecture by Warren Dicks
Abstract
Abstract for Chapters 1,2, and Appendix A. In this paper we establish some foundations regarding sheaves of vector spaces on graphs and their invariants, such as homology groups and their limits. We then use these ideas to prove the Hanna Neumann Conjecture of the 1950’s; in fact, we prove a strengthened form of the conjecture.
We introduce a notion of a sheaf of vector spaces on a graph, and develop the foundations of homology theories for such sheaves. One sheaf invariant, its “maximum excess,” has a number of remarkable properties. It has a simple definition, with no reference to homology theory, that resembles graph expansion. Yet it is a “limit” of Betti numbers, and hence has a short/long exact sequence theory and resembles the $L^2$ Betti numbers of Atiyah. Also, the maximum excess is defined via a supermodular function, which gives the maximum excess much stronger properties than one has of a typical Betti number.
Our sheaf theory can be viewed as a vast generalization of algebraic graph theory: each sheaf has invariants associated to it—such as Betti numbers and Laplacian matrices—that generalize those in classical graph theory.
We shall use “Galois graph theory” to reduce the Strengthened Hanna Neumann Conjecture to showing that certain sheaves, that we call $\rho$-kernels, have zero maximum excess. We use the symmetry in Galois theory to argue that if the Strengthened Hanna Neumann Conjecture is false, then the maximum excess of “most of” these $\rho$-kernels must be large. We then give an inductive argument to show that this is impossible.
Abstract for Appendix B. For a finite graph $Z$, $\bar {\mathrm {r}}(Z) := e-v+t$, where $e$, $v$, and $t$ denote the number of edges, vertices, and tree components of $Z$, respectively. Let $G$ be a finite group, $Z$ be a finite $G$-free $G$-graph, and $X$ and $Y$ be subgraphs of $Z$. Using linear algebra and algebraic geometry over a sufficiently large field, Joel Friedman proved that $\sum \limits _{g \in G} \bar {\mathrm {r}}(X\,{\cap }\,\,gY) \leqslant \bar {\mathrm {r}}(X) \bar {\mathrm {r}}(Y)$. He showed that this inequality implies the strengthened Hanna Neumann conjecture. We simplify Friedman’s proof of the foregoing inequality by replacing the sufficiently large field with a field $\mathbb {F}$ on which $G$ acts faithfully and then replacing all the arguments involving algebraic geometry with shorter arguments about the left ideals of the skew group ring $\mathbb {F}G$.
- Alon Amit and Nathan Linial, Random graph coverings. I. General theory and graph connectivity, Combinatorica 22 (2002), no. 1, 1–18. MR 1883559, DOI 10.1007/s004930200000
- M. F. Atiyah and I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0242802
- G. N. Arzhantseva, A property of subgroups of infinite index in a free group, Proc. Amer. Math. Soc. 128 (2000), no. 11, 3205–3210. MR 1694447, DOI 10.1090/S0002-9939-00-05508-8
- M. F. Atiyah, Elliptic operators, discrete groups and von Neumann algebras, Colloque “Analyse et Topologie” en l’Honneur de Henri Cartan (Orsay, 1974) Soc. Math. France, Paris, 1976, pp. 43–72. Astérisque, No. 32-33. MR 0420729
- Robert G. Burns, On the intersection of finitely generated subgroups of a free group, Math. Z. 119 (1971), 121–130. MR 279166, DOI 10.1007/BF01109964
- Warren Dicks and M. J. Dunwoody, Groups acting on graphs, Cambridge Studies in Advanced Mathematics, vol. 17, Cambridge University Press, Cambridge, 1989. MR 1001965
- P. Deligne, Cohomologie étale, Lecture Notes in Mathematics, vol. 569, Springer-Verlag, Berlin, 1977 (French). Séminaire de géométrie algébrique du Bois-Marie SGA $4\frac {1}{2}$. MR 463174
- Warren Dicks and Edward Formanek, The rank three case of the Hanna Neumann conjecture, J. Group Theory 4 (2001), no. 2, 113–151. MR 1812321, DOI 10.1515/jgth.2001.012
- Warren Dicks, Equivalence of the strengthened Hanna Neumann conjecture and the amalgamated graph conjecture, Invent. Math. 117 (1994), no. 3, 373–389. MR 1283723, DOI 10.1007/BF01232249
- Warren Dicks, Untitled email, preprint, 1 page. Available at http://mat.uab.es/~dicks/pub.html, specifically http://mat.uab.es/~dicks/two\%20corrections.pdf.
- Warren Dicks, Joel Friedman’s proof of the strengthened Hanna Neumann conjecture, preprint, 13 pages. Available at http://mat.uab.es/~dicks/pub.html, specifically http://mat.uab.es/~dicks/SimplifiedFriedman.pdf.
- Warren Dicks, Simplified Mineyev, preprint, 2 pages. Available at http://mat.uab.es/~dicks/pub.html, specifically http://mat.uab.es/~dicks/SimplifiedMineyev.pdf.
- Brent Everitt, Graphs, free groups and the Hanna Neumann conjecture, J. Group Theory 11 (2008), no. 6, 885–899. MR 2466915, DOI 10.1515/JGT.2008.057
- Joel Friedman, Ram Murty, and Jean-Pierre Tillich, Spectral estimates for abelian Cayley graphs, J. Combin. Theory Ser. B 96 (2006), no. 1, 111–121. MR 2185982, DOI 10.1016/j.jctb.2005.06.012
- Joel Friedman, Cohomology of Grothendieck topologies and lower bounds in Boolean complexity, preprint, 70 pages. Available at http://arxiv.org/abs/cs/0512008 and http://www.math.ubc.ca/jf, specifically http://www.math.ubc.ca/~jf/pubs/web_stuff/groth1.pdf.
- Joel Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Math. J. 69 (1993), no. 3, 487–525. MR 1208809, DOI 10.1215/S0012-7094-93-06921-9
- Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (2003), no. 1, 19–35. MR 1978881, DOI 10.1215/S0012-7094-03-11812-8
- Joel Friedman, Cohomology of Grothendieck topologies and lower bounds in Boolean complexity ii, preprint, 8 pages. Available at http://arxiv.org/abs/cs/0604024 and http://www.math.ubc.ca/jf, specifically http://www.math.ubc.ca/~jf/pubs/web_stuff/groth2.pdf.
- Joel Friedman, Linear transformations in Boolean complexity theory, CiE ’07: Proceedings of the 3rd conference on Computability in Europe (Berlin, Heidelberg), Springer-Verlag, 2007, pp. 307–315.
- Joel Friedman, A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100. MR 2437174, DOI 10.1090/memo/0910
- Joel Friedman (ed.), Expanding graphs, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 10, American Mathematical Society, Providence, RI, 1993. MR 1235562
- —, Sheaves on graphs and their homological invariants, Available at http://arxiv.org/pdf/1104.2665v1 and http://www.math.ubc.ca/jf, specifically http://www.math.ubc.ca/~jf/pubs/web_stuff/short_lim.pdf.
- —, Sheaves on graphs, their homological invariants, and a proof of the Hanna Neumann conjecture, preprint, 100 pages. Available at http://arxiv.org/pdf/1105.0129v2 and http://www.math.ubc.ca/jf, specifically http://www.math.ubc.ca/~jf/pubs/web_stuff/shnc_memoirs.pdf.
- Joel Friedman and Jean-Pierre Tillich, Generalized Alon-Boppana theorems and error-correcting codes, SIAM J. Discrete Math. 19 (2005), no. 3, 700–718. MR 2191289, DOI 10.1137/S0895480102408353
- S. M. Gersten, Intersections of finitely generated subgroups of free groups and resolutions of graphs, Invent. Math. 71 (1983), no. 3, 567–591. MR 695907, DOI 10.1007/BF02095994
- Sergei I. Gelfand and Yuri I. Manin, Methods of homological algebra, 2nd ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. MR 1950475
- Jonathan L. Gross, Every connected regular graph of even degree is a Schreier coset graph, J. Combinatorial Theory Ser. B 22 (1977), no. 3, 227–232. MR 450121, DOI 10.1016/0095-8956(77)90068-5
- Robin Hartshorne, Algebraic geometry, Springer-Verlag, New York-Heidelberg, 1977. Graduate Texts in Mathematics, No. 52. MR 0463157
- Joe Harris, Algebraic geometry, Graduate Texts in Mathematics, vol. 133, Springer-Verlag, New York, 1992. A first course. MR 1182558
- A. G. Howson, On the intersection of finitely generated free groups, J. London Math. Soc. 29 (1954), 428–434. MR 65557, DOI 10.1112/jlms/s1-29.4.428
- Peter John Hilton and Urs Stammbach, A course in homological algebra, Springer-Verlag, New York-Berlin, 1971. Graduate Texts in Mathematics, Vol. 4. MR 0346025
- Wilfried Imrich, On finitely generated subgroups of free groups, Arch. Math. (Basel) 28 (1977), no. 1, 21–24. MR 439941, DOI 10.1007/BF01223883
- Wilfried Imrich, Subgroup theorems and graphs, Combinatorial mathematics, V (Proc. Fifth Austral. Conf., Roy. Melbourne Inst. Tech., Melbourne, 1976) Springer, Berlin, 1977, pp. 1–27. Lecture Notes in Math., Vol. 622. MR 0463016
- S. V. Ivanov, On the intersection of finitely generated subgroups in free products of groups, Internat. J. Algebra Comput. 9 (1999), no. 5, 521–528. MR 1719719, DOI 10.1142/S021819679900031X
- S. V. Ivanov, Intersecting free subgroups in free products of groups, Internat. J. Algebra Comput. 11 (2001), no. 3, 281–290. MR 1847180, DOI 10.1142/S0218196701000267
- Toshiaki Jitsukawa, Bilal Khan, and Alexei G. Myasnikov, On the Hanna Neumann conjecture, 2003, Available as http://arxiv.org/abs/math/0302009.
- Bilal Khan, Positively generated subgroups of free groups and the Hanna Neumann conjecture, Combinatorial and geometric group theory (New York, 2000/Hoboken, NJ, 2001) Contemp. Math., vol. 296, Amer. Math. Soc., Providence, RI, 2002, pp. 155–170. MR 1921710, DOI 10.1090/conm/296/05072
- Serge Lang, Algebra, 3rd ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002. MR 1878556
- Wolfgang Lück, $L^2$-invariants: theory and applications to geometry and $K$-theory, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 44, Springer-Verlag, Berlin, 2002. MR 1926649
- Igor Mineyev, The topology and analysis of the Hanna Neumann conjecture, J. Topol. Anal. 3 (2011), no. 3, 307–376. MR 2831266, DOI 10.1142/S1793525311000611
- Igor Mineyev, Submultiplicativity and the Hanna Neumann conjecture, Ann. of Math. (2) 175 (2012), no. 1, 393–414. MR 2874647, DOI 10.4007/annals.2012.175.1.11
- Igor Mineyev, Groups, graphs, and the Hanna Neumann conjecture, J. Topol. Anal. 4 (2012), no. 1, 1–12. MR 2914871, DOI 10.1142/S1793525312500045
- J. Meakin and P. Weil, Subgroups of free groups: a contribution to the Hanna Neumann conjecture, Proceedings of the Conference on Geometric and Combinatorial Group Theory, Part I (Haifa, 2000), 2002, pp. 33–43. MR 1950872, DOI 10.1023/A:1020900823482
- Hanna Neumann, On the intersection of finitely generated free groups, Publ. Math. Debrecen 4 (1956), 186–189. MR 78992
- Hanna Neumann, On the intersection of finitely generated free groups. Addendum, Publ. Math. Debrecen 5 (1957), 128. MR 93537
- Walter D. Neumann, On intersections of finitely generated subgroups of free groups, Groups—Canberra 1989, Lecture Notes in Math., vol. 1456, Springer, Berlin, 1990, pp. 161–170. MR 1092229, DOI 10.1007/BFb0100737
- Walter D. Neumann, A short proof that positive generation implies the Hanna Neumann Conjecture, 2007, Available as http://arxiv.org/abs/math/0702395, to appear.
- Jakob Nielsen, Om Regning med ikke-kommutative Faktorer og dens Anvendelse i Gruppenteorien (in danish), Math. Tidsskrift B (1921), 78–94.
- Brigitte Servatius, A short proof of a theorem of Burns, Math. Z. 184 (1983), no. 1, 133–137. MR 711734, DOI 10.1007/BF01162012
- Théorie des topos et cohomologie étale des schémas. Tome 1: Théorie des topos, Lecture Notes in Mathematics, Vol. 269, Springer-Verlag, Berlin-New York, 1972 (French). Séminaire de Géométrie Algébrique du Bois-Marie 1963–1964 (SGA 4); Dirigé par M. Artin, A. Grothendieck, et J. L. Verdier. Avec la collaboration de N. Bourbaki, P. Deligne et B. Saint-Donat. MR 0354652
- Théorie des topos et cohomologie étale des schémas. Tome 2, Lecture Notes in Mathematics, Vol. 270, Springer-Verlag, Berlin-New York, 1972 (French). Séminaire de Géométrie Algébrique du Bois-Marie 1963–1964 (SGA 4); Dirigé par M. Artin, A. Grothendieck et J. L. Verdier. Avec la collaboration de N. Bourbaki, P. Deligne et B. Saint-Donat. MR 0354653
- Théorie des topos et cohomologie étale des schémas. Tome 3, Lecture Notes in Mathematics, Vol. 305, Springer-Verlag, Berlin-New York, 1973 (French). Séminaire de Géométrie Algébrique du Bois-Marie 1963–1964 (SGA 4); Dirigé par M. Artin, A. Grothendieck et J. L. Verdier. Avec la collaboration de P. Deligne et B. Saint-Donat. MR 0354654
- Cohomologie $l$-adique et fonctions $L$, Lecture Notes in Mathematics, Vol. 589, Springer-Verlag, Berlin-New York, 1977 (French). Séminaire de Géometrie Algébrique du Bois-Marie 1965–1966 (SGA 5); Edité par Luc Illusie. MR 0491704
- H. M. Stark and A. A. Terras, Zeta functions of finite graphs and coverings, Adv. Math. 121 (1996), no. 1, 124–165. MR 1399606, DOI 10.1006/aima.1996.0050
- John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551–565. MR 695906, DOI 10.1007/BF02095993
- Gábor Tardos, On the intersection of subgroups of a free group, Invent. Math. 108 (1992), no. 1, 29–36. MR 1156384, DOI 10.1007/BF02100597
- Gábor Tardos, Towards the Hanna Neumann conjecture using Dicks’ method, Invent. Math. 123 (1996), no. 1, 95–104. MR 1376247, DOI 10.1007/BF01232368
- Daniel T. Wise, The coherence of one-relator groups with torsion and the Hanna Neumann conjecture, Bull. London Math. Soc. 37 (2005), no. 5, 697–705. MR 2164831, DOI 10.1112/S0024609305004376