Geometries associated with Von Dick Groups

Abstract

This thesis contains a theoretical result in the eld of group actions on combinatorial structures, which is an important area of research, bringing forth some thirty publications per year. Besides its applications, mostly found in cryptography and image{recognition, such a discipline casts interesting bridges between the abstract theory of groups and more \visible" objects, like the graphs. On the theoretical side, in the last three decades, the deepest contributions have been given, among others, by M. D. E. Conder and his collaborators (see, e.g., [1] and references therein). But what is the advantage of associating a geometric structure to a given group G? If G is of a \tamed" kind, i.e., it is either nite, Abelian, solvable, or equipped with some additional structure like, e.g., that of a Lie group, then there are no advantages at all. In this thesis I will rather consider a class of groups, which is rather \wild", in the sense that it comprises in nite, discrete and solvable groups and it was allegedly introduced by W. von Dyck at the turn of the eighteenth century [10], and I will study some natural combinatorial geometric structures they act upon. My purpose is to show that even extremely elementary structures can play a nontrivial role in the understanding of such groups. I would like to stress, from the very beginning, that all the theoretical reasonings in this thesis are carried out in terms of abstract groups. By an \abstract group" I mean a group without any additional structure whatsoever which is not, a priori, realised as the transformation groups of some other mathematical entity. Such kind of groups are classically introduced through a presentation. In symbols, a presentation looks like G = hS j Ri, and it means that G can be obtained from the free group over the set S, i.e., the \largest"|so to speak|group admitting S as a set of generators, by factoring out the elements belonging to the normal subgroup generated by R. In spite of its rather formal and abstract avour, the notion of a presentation is heavy with geometrical implications. At the end of the eighteen century, A. Cayley introduced a combinatorial geometric structure, which nowadays is known to be a coloured graph, associated, in a functorial way, to a given presentation G = hS j Ri of the group G. Such a graph, which I will denote by ð€€€(G; S), goes under the name of Cayley graph, and it has the remarkable property of being regular (or homogeneous) with respect to G, i.e., the original group G act freely and transitively on it. It is a true marvel that such a rudimentary construction can be put at the foundations of some straightforward yet far{reaching observations: the so{called word problem (a still open problem) for a group G = hS j Ri is equivalent to the constructability (i.e., the possibility of de ning it through a recursive function) of ð€€€(G; S) [4]; if ð€€€(G; S) can be embedded into a surface, then it makes sense to attach to the group G a typical geometric property, namely, that of the genus [11]; the geometric properties of the surface (e.g., its compactness) ð€€€(G; S) is embedded into may be used to check the niteness of G [9, 2]. In this thesis, I basically discovered a link|a duality, to be more precise|between such a classical construction as the Cayley graph and another interesting (though perhaps less known) way of linking a graph to a group, which is the incidence graph [5] associated with the so{called coset geometry. Its main result stems from a subtle yet unfairly forgotten theorem, formulated by G. Sabidussi in 1958, establishing that ð€€€(G; S) is the unique, up to isomorphisms, edge{coloured graph on which the original group G acts vertex{transitively [7]. So, since the incidence graph of the coset geometry of G carries a natural edge{transitive G{action, and it is naturally vertex{coloured, I was led to suspect that the incidence graph of the coset geometry is, in fact, the same thing as the Cayley graph, provided that|roughly speaking|\vertices are replaced with edges". This thesis contains a rigorous proof of such a result, complemented by all the necessary preliminaries, and some (envisaged) applications and perspectives. The role played herewith by the von Dyck group D(n; n; n) is that of a tool to better explain such a vertex{to{edge duality. Indeed, for n > 3 the von Dyck groups D(n; n; n) belong to a class of (in nite, discrete and not solvable) groups known as Fuchsian groups, which are the discrete and nitely generated subgroup of the three{dimensional Lie group PSL (2;R) of the isometries of the hyperbolic plane H. The Fuchsian groups naturally act on a tangible geometric entity such as H. Moreover, D(n; n; n) is generated by the orientation{preserving transformations of a regular{triangular tessel- lation Tn, which, once again, is a rather elementary structure of combinatorial character, being essentially a triangulation by regular triangles. ABSTRACT (EN) 3 The vertex{to{edge duality, which is a quite general result, admits a nice transparent geometric formulation: in the case of von Dyck groups D(n; n; n) both the Cayley graph and the incidence graph of the coset geometry of D(n; n; n) are inscribed into Tn. More precisely, the latter is the 1{skeleton of Tn, while the former is the 1{skeleton of the so{called derived tessellation of Tn. In other words, the groups of von Dyck allow to visualise the vertex{to{edge duality in terms of the most elementary geometric shapes: triangles on a surface. Let me describe some of the applications and perspectives of the vertex{to{edge duality. First of all, it makes it evident that the Cayley graph of the von Dyck group is a planar one, which, to my best knowledge, has never been observed before, though a very similar result can be found in [9]. Then, the vertex{to{edge duality immediately allows to recast, in a transparent geometric way, a result proved in 1983 by T.W. Tucker [8], concerning the genus of the factors of D(n; n; n). I must mention that among the factors of D(n; n; n) there are the famous free Burnisde groups with two generators B(2; n), whose importance also pushed me to look for a recursive way to enumerate the elements of D(n; n; n). This is probably the most important consequence of the vertex{to{edge duality I have managed to discover so far: it allows to recursively enumerate the edges (called cliques, as in the theory of coloured graphs) of the incidence graph of the coset geometry and, hence, the elements of D(n; n; n). I dubbed this procedure \cliques enumeration algorithm", and there are indications that it may be useful for attacking the celebrated Burnside problem in the still unsolved cases with two generators. Indeed, in view of the natural surjection between D(n; n; n) and B(2; n), which makes it possible to associate to the latter some of the geometric features of the former, the niteness of B(2; n) can be a consequence of the niteness of a suitable \quotient tessellation" of Tn, with respect to the kernel of the projection D(n; n; n) ! B(2; n). Incidentally, this solves the word problem for the Burnisde groups with two generators. I must stress that, in one form or another, any existing algorithm to check the niteness of B(2; n) implements a mechanism to enumerate words, and, due to the presence of relations, the lexicographic way is not necessarily the cheapest one (see [3] and references therein). On the other hand, the cliques enumeration algorithm I proposed allows to \avoid" relations and to produce exactly once each element of the group, so that it may be computationally more advantageous. I have written the cliques enumeration algorithm by using the Wolfram MathematicaTMcomputer algebra software, but, due to the unavoidable computational complexity, I have managed to test it only for n 4. Nevertheless, it seems that, especially in comparison with the existing techniques, the cliques enumeration algorithm has the \aesthetic" merit of providing an uni ed approach to the problem of the niteness of B(2; n), for arbitrary n, in sharp contrast with the methods applied so far to each particular situation. [edited by author]