Combinatorial and Geometric Group Theory: Dortmund and Ottawa-Montreal conferences (Trends in Mathematics)

The Paper By O. Bogopolski And A. Vikentiev Describes Some Particularly Useful?niteindexsubgroupsoftheautomorphismgroupofa?nitelygeneratedfree Group. One Of Their Uses May Be To Attack The Problem On The Kazhdan Property (t) For These Groups. The Paper Of A. Juhasz Contains A Solution Of The Di?cult Membership Problem In A Subclass Of One-relator Groups. Papers Of F. Matucci, D. Savchuk And R. Zarzycki Will Attract The Attention Of Those Who Want To Know More About Groups Of Transformations Of The Unit Interval [0,1], In Particular About The Famous Thompson’s Group F And Its Limit Properties. The Paper By A.j. Duncan, V. Dieckert And A.g. Myasnikov Contains A Very Thoroughsurveyonrewritingsystemswithnewissuesonin?niterewritingsystems. The Paper By L. Frenkel, A.g. Myasnikov And V.n. Remeslennikov Is Devoted To Theproblemofhowto Measuresomesubsets Infreegroupsbyusingrandomwalks. The Results Of This Paper May Be Used For Designing Algorithms That Run Fast On Almost All Inputs. This Paper As Well As The Paper By M. Hock And B. Tsaban Are Highly Recommended To Specialists In Cryptography. Finally, The Paper By D. Goncalves And P. Wong Is Devoted To The Twisted Conjugacy In 2-dimensional Crystallographic Groups. We Are Very Grateful To The Organizations That Supported These Two Conferences: • Theconferenceindortmundwasorganizedbyo.bogopolski,m.-t.bochnig, G.rosenberger,v.shpilrainand E.ventura.thisconferencewas?nancially Supported By Daad (deutscher Akademischer Austauschdienst), By Dfg (deutsche Forschungsgemeinschaft), And By The Universit¨ At Dortmund. The Url Address For Its Homepage Is Http://www.mathematik.uni-dortmund.de/?gcgta/. Subgroups Of Small Index In Aut(fn) And Kazhdan's Property (t) / O. Bogopolski / R. Vikentiev -- Dynamics Of Free Group Automorphisms / P. Brinkmann -- Geodesic Rewriting Systems And Pregroups / V. Diekert / A.j. Duncan / A.g. Myasnikov -- Regular Sets And Counting In Free Groups / E. Frenkel / A.g. Myasnikov / V.n. Remeslennikov -- Twisted Conjugacy For Virtually Cyclic Groups And Crystallographic Groups / D. Goncalves / P. Wong -- Solving Random Equations In Garside Groups Using Length Functions / M. Hock / B. Tsaban -- An Application Of Word Combinatorics To Decision Problems In Group Theory / A. Juhasz -- Equations And Fully Residually Free Groups / O. Kharlampovich / A.g. Myasnikov -- The Fn-action On The Product Of The Two Limit Trees For An Iwip Automorphism / M. Lustig -- Mather Invariants In Groups Of Piecewise-linear Homeomorphisms / F. Matucci -- Algebraic Geometry Over The Additive Monoid Of Natural Numbers: Systems Of Coefficient Free Equations / P.v. Morar / A.n. Shevlyakov -- Some Graphs Related To Thompson's Group F / D. Svachuk -- Generating Typles Of Virtually Free Groups / R. Weidmann -- Limits Of Thompson's Group F / R. Zarzycki. Oleg Bogopolski ... [et Al.]. Selected Papers From The Conferences: Combinatorial And Geometric Group Theory With Applications (gagta), Held Aug. 27-31, 2007 At The University Of Dortmund; Fields Workshop In Asymptotic Group Theory And Cryptography, Held Dec. 14-16, 2007 At Carlton University, Ottawa, Canada; Workshop On Actions On Trees, Non-archimedian Words, And Asymptotic Cones, Held Dec. 17-21, 2007 At Saint Sauveur, Montreal. Includes Bibliographical References. Title page Copyright page Table of contents Preface Subgroups of Small Index in Aut(Fn) and Kazhdan’s Property (T) 1. Definitions, problems and motivations 2. A sketch of the proof of F. Grunewald and A. Lubotzky that Aut(F3) has no Kazhdan’s property (T) 3. Some notations and useful automorphisms 4. Finite index subgroups of Aut(Fn) containing IA(Fn) 5. Congruence subgroups SCong(n, k) in SAut(Fn) 6. A subgroup K(n) of index 2 in SCong(n, 2) 7. K(3) and some its overgroups with infinite abelianization 8. The group K(n) for n  4 References Dynamics of Free Group Automorphisms Introduction 1. Improved relative train track maps 2. More on train tracks 3. Terminology and examples 4. Strata of superlinear growth 5. Polynomially growing automorphisms 6. Proof of the main result Glossary References Geodesic Rewriting Systems and Pregroups 1. Introduction 2. Rewriting techniques 2.1. Basics 2.2. Rewriting in monoids 2.3. Convergent rewriting systems 2.4. Computing with infinite systems 3. Length-reducing and Dehn systems 3.1. Finite length-reducing systems 3.2. Infinite length-reducing systems 3.3. Weight-reducing systems 4. Preperfect systems 4.1. General results 5. Geodesically perfect rewriting systems 5.1. Geodesic systems 5.2. Geodesically perfect systems 6. Knuth-Bendix completion for geodesically perfect systems 7. Examples of preperfect systems in groups 7.1. Graph groups 7.2. Coxeter groups 7.3. HNN-extensions 7.4. Free products with amalgamation 8. Stallings’ pregroups and their universal groups 8.1. Rewriting systems for universal groups 8.2. Characterisation of pregroups in terms of geodesic systems References Regular Sets and Counting in Free Groups 1. Introduction 2. Preliminaries 2.1. Asymptotic densities 2.2. Generating random elements and multiplicative measures 2.3. The frequency measure 2.4. Asymptotic classification of subsets 2.5. Context-free and regular languages as a measuring tool 3. Schreier systems of representatives 3.1. Subgroup and coset graphs 3.2. Schreier transversals 4. Measuring subsets of F 5. Comparing sets at infinity 5.1. Comparing Schreier representatives 5.2. Comparing regular sets References Twisted Conjugacy for Virtually Cyclic Groups and Crystallographic Groups 1. Preliminaries 2. Elementary groups 3. Crystallographic groups 4. Cases 1–5 4.1. Case 1. 4.2. Case 4. 4.3. Case 2. 4.4. Case 3. 4.5. Case 5. 5. Cases 6–9 5.1. Case 7. 5.2. Case 8. 5.3. Case 6. 5.4. Case 9. 6. Cases 10, 13, 16 6.1. Case 13. 6.2. Case 10. 6.3. Case 16. 7. Cases 11, 12, 14, 15, and 17 7.1. Case 14. 7.2. Case 15. 7.3. Case 11. 7.4. Case 12. 7.5. Case 17. 8. Concluding remarks References Solving Random Equations in Garside Groups Using Length Functions 1. Solving random equations 1.1. Making the problems meaningful 1.2. The probabilistic model 1.3. Decision problems 2. The memory-length approach 2.1. The memory-length algorithm 2.2. Sufficiency for the general problem 2.3. Improvements 3. Excursion: Garside groups 3.1. Garside monoids and groups 3.2. Greedy normal form 3.3. Rational normal form 4. Several length functions on Garside groups 4.1. Quasi-geodesics in Garside groups 4.2. Quasi-geodesics in embedded Garside groups 4.3. The case of the braid group 5. Experimental results 5.1. Initial experiments 5.2. A detailed comparison 5.3. When the sentence length varies 5.4. When the word length varies 5.5. When the number of generators varies 5.6. When the number of strings varies 6. Concluding remarks and proposed future research References An Application of Word Combinatorics to Decision Problems in Group Theory Introduction 1. Preliminaries on small cancellation theory 1.1. Diagrams 1.2. Diagrams with small cancellation conditions 1.3. Transversals in diagrams with Small Cancellation Conditions 1.4. The Main Theorem for almost σ-complete presentations 2. Word combinatorics 2.1. Words 3. Piece configurations of 1-corner regions and 2-corner regions 3.1. 1-corner regions 3.2. 2-corner regions 3.3. Proof of the Main Theorem Appendix Acknowledgement References Equations and Fully Residually Free Groups 1. Introduction 1.1. Motivation 1.2. Milestones of the theory of equations in free groups 1.3. New age 2. Basic notions of algebraic geometry over groups 3. Fully residually free groups 3.1. Definitions and elementary properties 3.2. Lyndon’s completion FZ[t] 4. Main results in [38] 4.1. Structure and embeddings 4.2. Triangular quasi-quadratic systems 5. Elimination process 5.1. Generalized equations 5.2. Elementary transformations 5.3. Derived transformations and auxiliary transformations 5.4. Rewriting process for Ω 5.4.1. Tietze cleaning and entire transformation. 5.4.2. Solution tree. 5.4.3. Quadratic case. 5.4.4. Entire transformation goes infinitely. 6. Elementary free groups 7. Stallings foldings and algorithmic problems 8. Residually free groups References The FN-action on the Product of the Two Limit Trees for an Iwip Automorphism 1. Introduction 2. The set-up 3. The proof of Proposition 1.2 4. A little history and some references References Mather Invariants in Groups of Piecewise-linear Homeomorphisms 1. Introduction 2. The stair algorithm for functions in PL +(I) 4. Equivalence of the two points of view 5. Applications: centralizers and generalizations References Algebraic Geometry over the Additive Monoid of Natural Numbers: Systems of Coefficient Free Equations 1. Introduction 2. A-monoids 2.1. Logical preliminaries 3. Introduction to algebraic geometry 3.1. Systems of equations 3.2. Algebraic sets 3.3. Radicals 3.4. Coordinate monoids 3.5. Equationally Noetherian monoids 4. Commutative monoids with cancellation 5. Coefficient free algebraic geometry over N 5.1. Properties of finitely generated commutative positive monoids with cancellation 5.2. Ordering of submonoids of Zn 5.3. Proof of Theorem A 6. Geometric and universal equivalence 7. Dimension theory References Some Graphs Related to Thompson’s Group F Introduction 1. Thompson’s group 2. The Schreier graph of the action of F on the set of dyadic rational numbers 3. Coamenability of stabilizers of several dyadic rationals 4. The Schreier graph of the action of F on L2([0, 1]) 5. Parts of the Cayley graph of F References Generating Tuples of Virtually Free Groups 1. Introduction 2. Virtually free groups 3. The reduced core of a graph of groups 4. The proof of the theorem 5. The rank problem 6. Nielsen equivalence and T-systems References Limits of Thompson’s Group F 1. Preliminaries 2. Free products 3. HNN-extensions References Subgroups of small index in aut(fn) and kazhdan's property (t) -- O. Bogopolski / -- R. Vikentiev Dynamics of free group automorphisms -- P. Brinkmann Geodesic rewriting systems and pregroups -- V. Diekert / -- A.J. Duncan / -- A.G. Myasnikov Regular sets and counting in free groups -- E. Frenkel / -- A.G. Myasnikov / -- V.N. Remeslennikov Twisted conjugacy for virtually cyclic groups and crystallographic groups -- D. Goncalves / -- P. Wong Solving random equations in Garside groups using length functions -- M. Hock / -- B. Tsaban An application of word combinatorics to decision problems in group theory -- A. Juhasz Equations and fully residually free groups -- O. Kharlampovich / -- A. G. Myasnikov The fn-action on the product of the two limit trees for an iwip automorphism -- M. Lustig Mather invariants in groups of piecewise-linear homeomorphisms -- F. Matucci Algebraic geometry over the additive monoid of natural numbers: systems of coefficient free equations -- P.V. Morar / -- A.N. Shevlyakov Some graphs related to Thompson's group f -- D. Svachuk Generating typles of virtually free groups -- R. Weidmann Limits of Thompson's group f -- R. Zarzycki . This volume assembles several research papers in all areas of geometric and combinatorial group theory originated in the recent conferences in Dortmund and Ottawa in 2007. It contains high quality refereed articles developing new aspects of these modern and active fields in mathematics. It is also appropriate to advanced students interested in recent results at a research level