Detecting Fully Irreducible Automorphisms: A Polynomial Time Algorithm

References

• [Algom-Kfir and Rafi 15] Y. Algom-Kfir and K. Rafi. “Mapping Tori of Small Dilatation Expanding Train-Track Maps.” Topol. Appl. 180 (2015), 44–63.
   Web of Science ®Google Scholar
• [Bestvina and Feighn 92] M. Bestvina and M. Feighn. “A Combination Theorem for Negatively Curved Groups.” J. Differ. Geom. 35:1 (1992), 85–101.
   Web of Science ®Google Scholar
• [Bestvina and Handel 92] M. Bestvina and M. Handel. “Train Tracks and Automorphisms of Free Groups.” Ann. Math. (2) 135:1 (1992), 1–51.
   Web of Science ®Google Scholar
• [Bestvina and Handel 95] M. Bestvina and M. Handel. “Train-Tracks for Surface Homeomorphisms.” Topology 34:1 (1995), 109–140.
   Web of Science ®Google Scholar
• [Bestvina and Feighn 14] M. Bestvina and M. Feighn. “Hyperbolicity of the Complex of Free Factors.” Adv. Math. 256 (2014), 104–155.
   Web of Science ®Google Scholar
• [Bestvina et al. 97] M. Bestvina, M. Feighn, and M. Handel. “Laminations, Trees, and Irreducible Automorphisms of Free Groups.” Geom. Funct. Anal. 7:2 (1997), 215–244.
   Web of Science ®Google Scholar
• [Bestvina et al. 00] M. Bestvina, M. Feighn, and M. Handel. “The Tits Alternative for Out(Fn). I. Dynamics of Exponentially-Growing Automorphisms.” Ann. Math. (2) 151:2 (2000), 517–623.
   Web of Science ®Google Scholar
• [Bestvina et al. 05] M. Bestvina, M. Feighn, and M. Handel. “The Tits Alternative for Out(Fn). II. A Kolchin Type Theorem.” Ann. Math. (2) 161:1 (2005), 1–59.
   Web of Science ®Google Scholar
• [Bogopolski 08] O. Bogopolski. Introduction to Group Theory. EMS Textbooks in Mathematics. Zürich: European Mathematical Society (EMS), 2008.
   Google Scholar
• [Bridson and Groves 10] M. R. Bridson and D. Groves. “The Quadratic Isoperimetric Inequality for Mapping Tori of Free Group Automorphisms.” Mem. Am. Math. Soc. 203:955 (2010).
   Web of Science ®Google Scholar
• [Clay and Pettet 10] M. Clay and A. Pettet. “Twisting Out Fully Irreducible Automorphisms.” Geom. Funct. Anal. 20:3 (2010), 657–689.
   Web of Science ®Google Scholar
• [Clay et al. 15] M. Clay, J. Mangahas, and A. Pettet. “An Algorithm to Detect Full Irreducibility by Bounding the Volume of Periodic Free Factors.” Michigan Math. J. 64:2 (2015), 279–292.
   Web of Science ®Google Scholar
• [Clifford and Goldstein 10] A. Clifford and R. Goldstein. “Subgroups of Free Groups and Primitive Elements.” J. Group Theory 13 (2010), 601–611.
   Web of Science ®Google Scholar
• [Cooper 87] D. Cooper. “Automorphisms of Free Groups Have Finitely Generated Fixed Point Sets.” J. Algebra 111:2 (1987), 453–456.
   Web of Science ®Google Scholar
• [Coulbois 16] Th. Coulbois. Free Group Automorphisms and Train-Tracks with Sage User’s Guide. Available online (https://github.com/coulbois/sage-train-track/blob/master/sage-train-track-users-guide.pdf), March 17, 2016.
   Google Scholar
• [Coulbois and Hilion 12] T. Coulbois and A. Hilion. “Botany of Irreducible Automorphisms of Free Groups.” Pacific J. Math. 256:2 (2012), 291–307.
   Web of Science ®Google Scholar
• [Dicks 14] W. Dicks. “On Free-Group Algorithms That Sandwich a Subgroup between Free-Product Factors.” J. Group Theory 17 (2014), 13–28.
   Web of Science ®Google Scholar
• [Dicks and Ventura 96] W. Dicks and E. Ventura. “The Group Fixed by a Family of Injective Endomorphisms of a Free Group.” Contemp. Math. 195. Am. Math. Soc. 1996.
   Google Scholar
• [Dowdall et al. 15] S. Dowdall, I. Kapovich, and C. Leininger. “Dynamics on Free-by-Cyclic Groups.” Geom. Topol. 19:5 (2015), 2801–2899.
   Web of Science ®Google Scholar
• [Dowdall et al. a] S. Dowdall, I. Kapovich, and C. Leininger. “McMullen Polynomials and Lipschitz Flows for Free-by-Cyclic Groups.” J. Eur. Math. Soc. to appear, arXiv:1310.7481.
   Web of Science ®Google Scholar
• [Dowdall et al. b] S. Dowdall, I. Kapovich, and C. Leininger. “Endomorphisms, Train Track Maps, and Fully Irreducible Monodromies.” preprint, arXiv:1507.03028.
   Google Scholar
• [Dowdall and Taylor] S. Dowdall and S. Taylor. “The Co-Surface Graph and the Geometry of Hyperbolic Free Group Extensions.” preprint, arXiv:1601.00101.
   Google Scholar
• [Feighn and Handel] M. Feighn and M. Handel. “Algorithmic Constructions of Relative Train Track Maps and CTs, Groups, Geometry, and Dynamics.” to appear, arXiv:1411.6302v3.
   Google Scholar
• [Gaboriau et al. 98] D. Gaboriau, A. Jaeger, G. Levitt, and M. Lustig. “An Index for Counting Fixed Points of Automorphisms of Free Groups.” Duke Math. J. 93:3 (1998), 425– 452.
   Web of Science ®Google Scholar
• [Geršgorin 31] S. Geršgorin (S. Gerschgorin). “Über die abgrenzung der eigenwerte einer matrix.” Bulletin de l’Académie des Sciences de l’URSS. Classe des Sci. mathématiques et na 6 (1931), 749–754. (http://mi.mathnet.ru/izv5235).
   Google Scholar
• [Guirardel 00] V. Guirardel. “Dynamics of Out(Fn) on the Boundary of Outer Space.” Ann. Sci. École Norm. Sup. (4) 33:4 (2000), 433–465.
   Web of Science ®Google Scholar
• [Handel and Mosher] M. Handel and L. Mosher. “Subgroup Classification in Out(Fn).” preprint, arXiv:0908.1255.
   Google Scholar
• [Horbez 16] C. Horbez. “A Short Proof of Handel and Mosher’s Alternative for Subgroups of Out(FN).” Groups Geom. Dyn. 10:2 (2016), 709–721.
   Web of Science ®Google Scholar
• [Jäger and Lustig 08] A. Jäger and M. Lustig. “Free Group Automorphisms with Many Fixed Points at Infinity. The Zieschang Gedenkschrift, 321–333.” Geom. Topol. Monogr. 14 (2008).
   Google Scholar
• [Kapovich 14] I. Kapovich. “Algorithmic Detectability of Iwip Automorphisms.” Bull. Lond. Math. Soc. 46:2 (2014), 279–290.
   Web of Science ®Google Scholar
• [Kapovich and Lustig 10] I. Kapovich and M. Lustig. “Ping-Pong and Outer Space.” J. Topol. Anal. 2 (2010), 173–201.
   Web of Science ®Google Scholar
• [Kapovich and Myasnikov 02] I. Kapovich and A. Myasnikov. “Stallings Foldings and the Subgroup Structure of Free Groups.” J. Algebra 248:2 (2002), 608–668.
   Web of Science ®Google Scholar
• [Kapovich and Pfaff 15] I. Kapovich and C. Pfaff. “A Train Track Directed Random Walk on Out(Fr).” Int. J. Algebra Comput. 25:5 (2015), 745–798.
   Web of Science ®Google Scholar
• [Levitt and Lustig 03] G. Levitt and M. Lustig. “Irreducible Automorphisms of Fn Have North-South Dynamics on Compactified Outer Space.” J. Inst. Math. Jussieu 2:1 (2003), 59–72.
   Web of Science ®Google Scholar
• [Lyndon and Schupp 77] R. Lyndon and P. Schupp. Combinatorial Group Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. Berlin-New York: Springer-Verlag, 1977.
   Google Scholar
• [Maher and Tiozzo] J. Maher and G. Tiozzo. “Random Walks on Weakly Hyperbolic Groups.” J. für die reine und angewandte Mathematik to appear, arXiv:1410.4173.
   Web of Science ®Google Scholar
• [Martin 95] R. Martin. “Non-Uniquely Ergodic Foliations of Thin-Type, Measured Currents and Automorphisms of Free Groups.” PhD thesis, UCLA, 1995.
   Google Scholar
• [Meyer 00] C. Meyer. Matrix Analysis and Applied Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2000. With 1 CD-ROM (Windows, Macintosh and UNIX) and a solutions manual (iv+171 pp.).
   Google Scholar
• [Pfaff 12] C. Pfaff. “Constructing and Classifying Fully Irreducible Outer Automorphisms of Free Groups.” Preprint, arXiv:1205.5320, 2012.
   Google Scholar
• [Pfaff 15] C. Pfaff. “Ideal Whitehead Graphs in Out(Fr) II: The Complete Graph in Each Rank.” J. Homotopy Relat. Struct. 10:2 (2015), 275–301.
   Web of Science ®Google Scholar
• [Reynolds] P. Reynolds. “Dynamics of Irreducible Endomorphisms of Fn.” Preprint, arXiv:1008.3659.
   Google Scholar
• [Roig 07] A. Roig, E. Ventura, and P. Weil. “On the Complexity of the Whitehead Minimization Problem.” Int. J. Algebra Comput. 17:8 (2007), 1611–1634.
   Web of Science ®Google Scholar
• [Stallings 83] J. R. Stallings. “Topology of Finite Graphs.” Invent. Math. 71:3 (1983), 551– 565.
   Web of Science ®Google Scholar
• [Turner 93] E. C. Turner. “Finding Indivisible Nielsen Paths for a Train Track Map.” In Combinatorial and Geometric Group Theory (Edinburgh, 1993), 300–313, London Math. Soc. Lecture Note Ser., 204. Cambridge: Cambridge Univ. Press, 1995.
   Google Scholar
• [Uyanik 14] C. Uyanik. “Dynamics of Hyperbolic Iwips.” Conform. Geom. Dyn. 18 (2014), 192–216.
   Google Scholar
• [Vogtmann 02] K. Vogtmann. “Automorphisms of Free Groups and Outer Space.” Geometriae Dedicata 94 (2002), 1–31.
   Web of Science ®Google Scholar