Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

The geometry of profinite graphs with applications to free groups and finite monoids


Authors: K. Auinger and B. Steinberg
Journal: Trans. Amer. Math. Soc. 356 (2004), 805-851
MSC (2000): Primary 20E18, 20E08, 20M07, 20M18
DOI: https://doi.org/10.1090/S0002-9947-03-03358-0
Published electronically: August 21, 2003
MathSciNet review: 2022720
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We initiate the study of the class of profinite graphs $\Gamma$ defined by the following geometric property: for any two vertices $v$ and $w$ of $\Gamma$, there is a (unique) smallest connected profinite subgraph of $\Gamma$ containing them; such graphs are called tree-like. Profinite trees in the sense of Gildenhuys and Ribes are tree-like, but the converse is not true. A profinite group is then said to be dendral if it has a tree-like Cayley graph with respect to some generating set; a Bass-Serre type characterization of dendral groups is provided. Also, such groups (including free profinite groups) are shown to enjoy a certain small cancellation condition.

We define a pseudovariety of groups $\mathbf{H}$ to be arboreous if all finitely generated free pro- $\mathbf{H}$ groups are dendral (with respect to a free generating set). Our motivation for studying such pseudovarieties of groups is to answer several open questions in the theory of profinite topologies and the theory of finite monoids. We prove, for arboreous pseudovarieties $\mathbf{H}$, a pro- $\mathbf{H}$ analog of the Ribes and Zalesski{\u{\i}}\kern.15em product theorem for the profinite topology on a free group. Also, arboreous pseudovarieties are characterized as precisely the solutions $\mathbf{H}$ to the much studied pseudovariety equation $\mathbf{J}\ast\mathbf{H}= \mathbf{J}\mathrel{{\mbox{\textcircled{\petite m}}}}\mathbf{H}$.


References [Enhancements On Off] (What's this?)

  • 1. J. Almeida, Finite Semigroups and Universal Algebra, World Scientific, Singapore, 1995. MR 96b:20069
  • 2. J. Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products, Internat. J. Algebra Comput. 9 (1999), 241-261. MR 2001a:20102
  • 3. J. Almeida and B. Steinberg, Iterated semidirect products with applications to complexity, Proc. London Math. Soc. 80 (2000), 50-74. MR 2000j:20109
  • 4. J. Almeida and B. Steinberg, Syntactic and global semigroup theory, a synthesis approach, pp. 1-23 in: Algorithmic Problems in Groups and Semigroups, J.-C. Birget, S. Margolis, J. Meakin, M. Sapir, eds., Birkhäuser, Basel, 2000. MR 2001c:20120
  • 5. J. Almeida and P. Weil, Reduced factorizations in free profinite groups and join decompositions of pseudovarieties, Internat. J. Algebra Comput. 3 (1994), 375-403. MR 95m:20066
  • 6. J. Almeida and P. Weil, Relatively free profinite monoids: An introduction and examples, pp. 73-117 in: Semigroups, Formal Languages and Groups, J. B. Fountain, ed., Kluwer, Dordrecht, 1995. MR 2000f:20095
  • 7. J. Almeida and P. Weil, Free profinite semigroups over semidirect products, Russian Math. (Iz. VUZ) 39 (1995), 1-27. MR 97e:20078
  • 8. C. J. Ash, Inevitable graphs: A proof of the type II conjecture and some related decision procedures, Internat. J. Algebra Comput. 1 (1991), 127-146. MR 92k:20114
  • 9. K. Auinger, Semigroups with central idempotents, pp. 25-33 in: Algorithmic Problems in Groups and Semigroups, J.-C. Birget, S. Margolis, J. Meakin, M. Sapir, eds., Birkhäuser, Basel, 2000. MR 2001c:20125
  • 10. K. Auinger, Join decompositions of pseudovarieties involving semigroups with commuting idempotents, J. Pure Appl. Algebra 170 (2002), 115-129. MR 2003d:20082
  • 11. K. Auinger, T. E. Hall, N. R. Reilly and S. Zhang, Congruences on the lattice of pseudovarieties of finite semigroups, Internat. J. Algebra Comput. 7 (1997), 433-455. MR 98h:20100
  • 12. A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Amer. Math. Soc., Providence, 1961. MR 24:A2627
  • 13. M. Delgado, S. W. Margolis, and B. Steinberg, Combinatorial group theory, inverse monoids, automata, and global semigroup theory, Internat. J. Algebra Comput. 12 (2002), 179-211. MR 2003b:20061
  • 14. S. Eilenberg, Automata, Languages and Machines, Academic Press, New York, Vol A, 1974; Vol B, 1976. MR 58:26604a; MR 58:26604b
  • 15. G. Elston, Semigroup expansions using the derived category, kernel, and Malcev products, J. Pure Appl. Algebra 136 (1999), 231-265. MR 2000a:20128
  • 16. R. Gitik and E. Rips, On separability properties of groups, Internat. J. Algebra Comput. 5 (1995), 703-717. MR 97e:20059
  • 17. D. Gildenhuys and L. Ribes, Profinite groups and Boolean graphs, J. Pure Appl. Algebra 12 (1978), 21-47. MR 81g:20059
  • 18. M. Hall Jr., A topology for free groups and related groups, Ann. of Math. 52 (1950), 127-139. MR 12:158b
  • 19. B. Herwig and D. Lascar, Extending partial automorphisms and the profinite topology on free groups, Trans. Amer. Math. Soc. 352 (2000), 1985-2021. MR 2000j:20036
  • 20. K. Henckell, S. W. Margolis, J.-E. Pin, and J. Rhodes, Ash's type II theorem, profinite topology and Mal'cev products, Part I, Internat. J. Algebra Comput. 1 (1991), 411-436. MR 93h:20064
  • 21. P. M. Higgins, Techniques of Semigroup Theory, Oxford University Press, Oxford, 1992. MR 93d:20101
  • 22. J. M. Howie, Fundamentals of Semigroup Theory, Clarendon Press, Oxford, 1995. MR 98e:20059
  • 23. K. Krohn and J. Rhodes, Algebraic theory of machines, I, Trans. Amer. Math. Soc. 116 (1965), 450-464. MR 32:5755
  • 24. K. Krohn and J. Rhodes, Complexity of finite semigroups, Ann. of Math. 88 (1968), 128-160. MR 38:4591
  • 25. M. V. Lawson, Inverse Semigroups: The Theory of Partial Symmetries, World Scientific, Singapore, 1998. MR 2000g:20123
  • 26. S. W. Margolis and J. C. Meakin, E-unitary inverse monoids and the Cayley graph of a group presentation, J. Pure Appl. Algebra 58 (1989), 45-76. MR 90f:20096
  • 27. S. W. Margolis and J. C. Meakin, Free inverse monoids and graph immersions, Internat. J. Algebra Comput. 3 (1993), 79-99. MR 94c:20105
  • 28. S. W. Margolis and J.-E. Pin, Varieties of finite monoids and topology for the free monoid, pp 113-130 in: Proceedings of the 1984 Marquette Conference on Semigroups, K. Byleen, P. Jones and F. Pastijn, eds., Marquette University, Milwaukee, 1984.
  • 29. S. W. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro- $\mathbf{ V}$ topologies and the extension problem for inverse automata, Internat. J. Algebra Comput. 11 (2001), 405-445. MR 2002g:20097
  • 30. D. B. McAlister, Groups, semilattices and inverse semigroups, Trans. Amer. Math. Soc. 68 (1974), 227-244. MR 50:10128
  • 31. J. McCammond and J. Rhodes, Geometric semigroup theory, Internat. J. Algebra Comput.
    (to appear).
  • 32. W. D. Munn, Free inverse semigroups, Proc. London Math. Soc. 30 (1974), 385-404. MR 50:13328
  • 33. H. Neumann, Varieties of Groups, Springer, Berlin, Heidelberg, New York, 1967. MR 35:6734
  • 34. G. Niblo, Separability properties of free groups and surface groups, J. Pure Appl. Algebra 78 (1992), 77-84. MR 92m:20019
  • 35. J.-E. Pin, $\mathbf{BG} = \mathbf{PG}$, a success story, pp. 33-47 in: Semigroups, Formal Languages and Groups, J. B. Fountain, ed., Kluwer, Dordrecht, 1995. MR 99e:20072
  • 36. J.-E. Pin and C. Reutenauer, A conjecture on the Hall topology for the free group, Bull. London Math. Soc. 23 (1991), 356-362. MR 92g:20035
  • 37. J. Rhodes and B. Steinberg, Pointlike sets, hyperdecidability and the identity problem for finite semigroups, Internat. J. Algebra Comput. 9 (1999), 475-481. MR 2000k:20075
  • 38. J. Rhodes and B. Steinberg, Profinite semigroups, varieties, expansions and the structure of relatively free profinite semigroups, Internat. J. Algebra Comput. 11 (2002), 627-672. MR 2002j:20114
  • 39. L. Ribes and P. A. Zalesski{\u{\i}}\kern.15em, On the profinite topology on a free group, Bull. London Math. Soc. 25 (1993), 37-43. MR 93j:20062
  • 40. L. Ribes and P. A. Zalesski{\u{\i}}\kern.15em, The pro-$p$ topology of a free group and algorithmic problems in semigroups, Internat. J. Algebra Comput. 4 (1994), 359-374. MR 96e:20046
  • 41. L. Ribes and P. A. Zalesski{\u{\i}}\kern.15em, Pro-$p$ Trees and Applications, pp. 75-119 in: New Horizons in pro-$p$ Groups, M. Du Sautoy, D. Segal, A. Shalev, eds., Birkhäuser, Boston, 2000. MR 2001f:20057
  • 42. L. Ribes and P. A. Zalesski{\u{\i}}\kern.15em, Profinite Groups, Springer, Berlin, 2000. MR 2001k:20060
  • 43. L. Ribes and P. A. Zalesski{\u{\i}}\kern.15em, Profinite Trees, Springer
    (to appear).
  • 44. J.-P. Serre, Trees, Springer-Verlag, Berlin Heidelberg New York, 1980. MR 82c:20083
  • 45. J. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), 551-565. MR 85m:05037a
  • 46. B. Steinberg, On pointlike sets and joins of pseudovarieties, Internat. J. Algebra Comput. 8 (1998), 203-231. MR 99g:20104
  • 47. B. Steinberg, On algorithmic problems for joins of pseudovarieties, Semigroup Forum 62 (2001), 1-40. MR 2002e:20124
  • 48. B. Steinberg, Inevitable graphs and profinite topologies: Some solutions to algorithmic problems in monoid and automata theory stemming from group theory, Internat. J. Algebra Comput. 11 (2001), 25-71. MR 2002a:68074
  • 49. B. Steinberg, A delay theorem for pointlikes, Semigroup Forum 63 (2001), 281-304. MR 2002m:20094
  • 50. B. Steinberg, Finite state automata: A geometric approach, Trans. Amer. Math. Soc. 353 (2001), 3409-3464. MR 2002c:20106
  • 51. B. Steinberg, Polynomial closure and topology, Internat. J. Algebra Comput. 10 (2000), 603-624. MR 2001m:20102
  • 52. B. Steinberg, Inverse automata and profinite topologies on a free group, J. Pure Appl. Algebra 167 (2002), 341-359. MR 2002i:20037
  • 53. B. Steinberg, $\mathbf{PG} = \mathbf{BG}$: Redux, pp. 181-190 in: Proceedings of the International Conference on Semigroups, P. Smith, E. Giraldes, P. Martins, eds., World Scientific, Singapore, 2000. MR 2003b:20083
  • 54. B. Steinberg, The uniform word problem for groups and finite Rees quotients of $E$-unitary inverse semigroups, J. Algebra 266 (2003), 1-13.
  • 55. J. B. Stephen, Presentations of inverse monoids, J. Pure Appl. Algebra 63 (1990), 81-112. MR 91g:20083
  • 56. B. Tilson, Categories as algebra: An essential ingredient in the theory of monoids, J. Pure Appl. Algebra 48 (1987), 83-198. MR 90e:20061
  • 57. P. Weil, Computing closures of finitely generated subgroups of the free group, pp. 289-307 in: Algorithmic Problems in Groups and Semigroups, J.-C. Birget, S. Margolis, J. Meakin, M. Sapir, eds., Birkhäuser, Basel, 2000. MR 2001c:20049
  • 58. P. A. Zalesski{\u{\i}}\kern.15em, A geometric characterization of free constructions of profinite groups, Siber. Math. J. 30 (1989), 73-84. MR 90e:20025
  • 59. P. A. Zalesski{\u{\i}}\kern.15emand O. Mel'nikov, Subgroups of profinite groups acting on trees, Math. USSR Sbornik 63 (1989), 405-424. MR 90f:20041

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 20E18, 20E08, 20M07, 20M18

Retrieve articles in all journals with MSC (2000): 20E18, 20E08, 20M07, 20M18


Additional Information

K. Auinger
Affiliation: Institut für Mathematik, Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria
Email: karl.auinger@univie.ac.at

B. Steinberg
Affiliation: School of Mathematics and Statistics, Carleton University, Herzberg Laboratories, Ottawa, Ontario, Canada K1S 5B6
Email: bsteinbg@math.carleton.ca

DOI: https://doi.org/10.1090/S0002-9947-03-03358-0
Received by editor(s): September 28, 2002
Received by editor(s) in revised form: March 13, 2003
Published electronically: August 21, 2003
Additional Notes: The authors gratefully acknowledge support from INTAS project 99–1224 Combinatorial and geometric theory of groups and semigroups and its applications to computer science. The second author was supported in part by NSF-NATO postdoctoral fellowship DGE-9972697, as well as by Praxis XXI scholarship BPD 16306 98, FCT through the Centro de Matemática da Universidade do Porto, and by the FCT and POCTI approved project POCTI/32817/MAT/2000 in participation with the European Community Fund FEDER. He was at the University of Porto when this work was performed.
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society