Transactions of the American Mathematical Society

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

Author(s): K. Auinger; B. Steinberg
Journal: Trans. Amer. Math. Soc. 356 (2004), 805-851.
MSC (2000): Primary 20E18, 20E08, 20M07, 20M18
Posted: August 21, 2003
Retrieve article in: PDF DVI PostScript

Abstract: We initiate the study of the class of profinite graphs $\Gamma$ defined by the following geometric property: for any two vertices

and

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}$ .

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- 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- Trees and Applications, pp. 75-119 in: New Horizons in pro- 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 -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.15em$ and O. Mel'nikov, Subgroups of profinite groups acting on trees, Math. USSR Sbornik 63 (1989), 405-424. MR 90f:20041

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

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: 10.1090/S0002-9947-03-03358-0
PII: S 0002-9947(03)03358-0
Received by editor(s): September 28, 2002
Received by editor(s) in revised form: March 13, 2003
Posted: August 21, 2003
Additional Notes: The authors gratefully acknowledge support from INTAS project 99--1224 \textit{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 \emph{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.
Copyright of article: Copyright 2003, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS